# Binary Search Tree
###### tags: `Algorithm` `DataStructure`

<style>
.red {
color: red;
}
</style>
<style>
.blue {
color: blue;
}
</style>
<style>
.green {
color: green;
}
</style>

## With sorted array

* BST can do things that any sorted array can do plus **fast insertion and deletion**.


* Properties:
> 1. in an arbitrary node of tree all keys in left are smaller and all keys in right are larger.
> 2. hight could be anywhere from log2(n) to n

### Searching and Insertion
#### Searching
1. start at the root
2. traverse left/right child points as k<key/k>key
3. return node with key k or NULL

#### Insertion
1. search for k using algorithm above an check if it exists
2. rewire final NULL ptr(not exists) to point to new node with key k

#### Conclusion of searching and insertion
Worst-case running time of search(or insertion) operation in a binary search tree containing n keys is
$$
{\theta (height)}
$$

### Min, Max, Predecessor, Successor(**Think carefully**)
#### Min and Max
1. start at root
2. follow left(min)/right(max) child pointers until you can't anymore and return the last key
#### Predecessor(the largest key in the left subarray in an sorted array)
* easy case: if k's left subtree is not empty, return the max key in the left subtree using the algorithm above.
* left substree empty case: follow parent pointers until you got to a key less than k
#### Successor(the opposite of Predecessor)
* easy case: if k's right subtree is not empty, return the min key in the right subtree using the algorithm above.
* right substree empty case: follow parent pointers until you got to a key larger than k
#### Conclusion of Min, Max, Predecessor, Successor
Worst-case running time of Min, Max, Predecessor, Successor operation in a binary search tree containing n keys is
$$
{\theta (height)}
$$

### In-Order Traversal->to print out keys in increasing order
1. let r = root of BST, with subtree T_l, T_r
2. recurse on T_l, using In-Order Traversal
3. when the root is at the end of untraverse keys, print out r's key
4. recurse on T_r, using In-Order Traversal

#### Conclusion of In-Order Traversal
Worst-case running time of In-Order Traversal operation in a binary search tree containing n keys is
$$
{\theta (n)}
$$

### Deletion
1. search for key k using algorithm above.
2. if k is found, situation can be seperated into the following three cases
2.1 case1: k has no children
2.2 case2: k has one child
2.3 case3: k has two children

#### case1: k has no children
Just delete the node and it's done.
#### case2: k has one child
k's child should replace the k's original position after k is deleted.
#### case3: k has two children
Reduce this complicated case to case 1 or 2
1. Compute k's predecessor l using the algorithm above
2. swap k and l. When this step is finished, the rule of BST is broke temporarily.
3. Delete k which is easy to delete for matching case1 or case2.
#### Conclusion
Worst-case running time of Delete operation in a binary search tree containing n keys is
$$
{\theta (height)}
$$

# Balanced BST
**Worst-case Running time of most operations above are** $$
{\theta (height)}
$$
So it's important to ensure that height of BST is always O(log(n))

Ex: Red-Black tree

## Red-Black Invariants
1. each node is red or black
2. root is black
3. no 2 red nodes in a row.
4. every root to NULL path has same number of black nodes

These are examples of RBTree.

### Height Grarantee
* Claims: every red-black tree with n nodes has height height <= 2 log2(n+1)
* Proof: Observation: if every root-NULL path has >= k nodes, then they includes a perfectly balanced search tree of depth = k-1. Size n tree >= 2^k -1, where k = minimum of root->NULL path
Thus, in a red-black tree with n nodes, there is a root-NULL path with at most lon2(n+1) black nodes.
* By Invariant4, every root-NULL path has <= log2(n+1) black nodes.
* By Invariant3, every root-NULL path has <= 2*log2(n+1) total nodes

## Rotation(Common to all balanced BST such as red-black tree, AVL, .etc)
Idea: locally rebalance subtrees in an O(1) time
### Left rotation

### Right rotation