Binary Search Trees
Introduction
- a binary tree that satisfies the BST invariant: left subtree has smaller elements and right subtree has larger elements
- BST operations allow for duplicate values, but most of the time we are only interested in having unique elements inside our tree
- it is called a search tree because it can be used to search for the presence of a number in
O(log(n)) time.



Usage
- implementation of Map and Set ADTs
- Red Black Trees, AVL Trees, Splay Trees, etc.
- implementation of Binary Heaps
- Syntax Trees, used by compilers and calculators
- Treap, probabilistic DS, uses a randomized BST
- multilevel indexing in the database
- dynamic sorting
- managing virtual memory areas in Unix kernel
Implementation
Insert Operation