Search Trees

Binary Search Trees (BST)
Related homework questions: h3-6
Binary Tree
A binary tree TTT
 is a set NNN
 of nodes where each node u0u_0u0​
 has two pointers, u0u_0u0​
.left and u0u_0u0​
.right.
The size of TTT
 is ∣N∣|N|∣N∣
.
Complete Binary Tree
Every level of the tree is completely filled, except possibly the last level. Moreover, the last level has to be filled from left to right.
If a complete binary tree is also complete on the last level, then it is called a perfect binary tree.
Height of binary trees
Minimum number of nodes in a binary tree of height hhh
:
μ(h)=h+1\begin{gather*} \mu(h) = h + 1 \end{gather*}μ(h)=h+1​
Maximum number of nodes in a binary tree of height hhh
:
M(h)=2h+1−1\begin{gather*} M(h) = 2^{h+1} - 1 \end{gather*}M(h)=2h+1−1​
The minimum height of binary trees with nnn
 nodes:
h≥lg⁡(n+1)−1\begin{gather*} h \ge \lg(n + 1) - 1 \end{gather*}h≥lg(n+1)−1​
Binary Search Tree
A binary tree is a binary search tree if each node u∈Tu \in Tu∈T
 has a field uuu
.key that satisfies the BST property:
uL.key<u.key≤uR.key\begin{gather*} u_L.key < u.key \le u_R.key \end{gather*}uL​.key<u.key≤uR​.key​
AVL Trees
Related homework questions: h3-7, h3-8
An AVL tree is a binary search tree where the left subtree and right subtree at each node differ by at most 1 in height.
Balance Factor
More generally, define the balance of any node uuu
 of a binary tree to be the height of the left subtree minus the height of the right subtree:
b(u)=h(u.left)−h(u.right)\begin{gather*} b(u) = h(u.left) - h(u.right) \end{gather*}b(u)=h(u.left)−h(u.right)​
Insertion and Deletion Algorithms
UPDATE PHASE: Insert or delete as we would in a binary search tree.
REBALANCE PHASE: Let xxx
 be parent of the node that was just inserted, or just cut during deletion, in the UPDATE PHASE. THe path from xxx
 to the root will be called the rebalance path. We now move up this path, rebalancing nodes along this path as necessary.
Let uuu
 be the first unbalanced node we encounter along the rebalance path from bottom to top. It is clear that uuu
 has a balance of ±2\pm 2±2
. The situation is illustrated below:
Figure 16: Node u is unbalanced after insertion or deletion
Insertion Rebalancing
CASE (I.a): hL=hh_L = hhL​=h
 and hR=h−1h_R = h - 1hR​=h−1
. This means that the inserted node is in the left subtree of vvv
. In this case, we rotate vvv
, the result would be balanced. Moreover, the height of uuu
 is now h+1h+1h+1
. We call this the "single-rotation" case.
Figure 17: AVL Insertion: CASE (I.a)
CASE (I.b): hL=h−1h_L = h - 1hL​=h−1
 and hR=hh_R = hhR​=h
. This means that the inserted node is in the right subtree of vvv
. In this case, let us expand the subtree DDD
 and let www
 be its root. The two children of www
 will have heights h−δh - \deltah−δ
 and h−δ′h - \delta'h−δ′
 where δ,δ′∈{1,2}\delta, \delta' \in \{1, 2\}δ,δ′∈{1,2}
. Now a double-rotation at www
 results in a balanced tree of height h+1h+1h+1
 rooted at www
.
Figure 17: AVL Insertion: CASE (I.b)
Deletion Rebalancing
CASE (D.a): hL=hh_L = hhL​=h
 and hR=h−1h_R = h - 1hR​=h−1
. This is like case (I.a) and treated in the same way, namely a single rotation at vvv
. Now uuu
 is replaced by vvv
 after this rotation, and the new height of vvv
 is h+1h+1h+1
. Now uuu
 is AVL balanced. However, since the original height is h+2h + 2h+2
, there may beb unbalanced node further up the rebalance path. Thus, this is a non-terminal case.
CASE (D.b): hL=h−1h_L = h - 1hL​=h−1
 and hR=hh_R = hhR​=h
. This is like case (I.b) and treated in the same way, namely a double rotation at www
. Again, this is a non-terminal case.
CASE (D.c): hL=hR=hh_L = h_R = hhL​=hR​=h
. This case is new, we simply rotate at vvv
. We check that vvv
 is balanced and has height h+2h+2h+2
. Since vvv
 is in the place of uuu
 which has height h+2h+2h+2
 originally, we can safely terminate the rebalancing process.
Figure 20: AVL Deletion: CASE (D.c) rotate(v)
Ratio/Weight Balanced Trees
Related homework questions: h4-3
Extended size:
esize(u)={1if u=nilesize(u.left)+esize(u.right)if u≠nil\begin{gather*} esize(u) = \begin{cases} 1 & \text{if } u = nil \\ esize(u.left) + esize(u.right) & \text{if } u \neq nil \end{cases} \end{gather*}esize(u)={1esize(u.left)+esize(u.right)​if u=nilif u=nil​​
Ratio:
ratio(u):=esize(u.left)esize(u.right)\begin{gather*} ratio(u) := {esize(u.left) \over {esize(u.right)}} \end{gather*}ratio(u):=esize(u.right)esize(u.left)​​
ρ-ratio
ρ<ratio(u)<1/ρ\begin{gather*} \rho < ratio(u) < 1/\rho \end{gather*}ρ<ratio(u)<1/ρ​
Insertion and Deletion Algorithms
Example: ho=1/3ho = 1/3ho=1/3
​
UPDATE PHASE: Insert or delete as we would in a binary search tree. In insertion, this results in a new leaf xxx
 in TTT
. If deletion, we will physically "cut" the leaf xxx
 from TTT
.
REBALANCE PHASE: Let uuu
 be the parent of xxx
. Clearly, every node that is not RB balanced must lie on the root-path of uuu
. We therefore move up this path, rebalancing any such node.
Rebalance(u)
  While (u != u.parent)
    u <- Rebalance-Step(u)
    u <- u.parent
Rebalance-Step(u)
  If (ratio(u) >= 3)
    v <- u.left
    If (ratio(v) >= 3/5)
      Return(rotate(v))
    Else \\ ratio(v) < 3/5
      Return(double-rotate(v.right))
  elif (ratio(u) <= 1/3)
    v <- u.right
    If (ratio(v) <= 3/5)
      Return(rotate(v))
    Else \\ ratio(v) > 3/5
      Return(double-rotate(v.left))
  else
    Return(u)
Generalized B-Trees: (2,3)-trees
Related homework questions: h4-1, h4-2
An (a,b)-tree is a rooted, ordered tree with the following structural constraints:
Depth property: All leaves are at the same depth.
Degree bound: Let mmm
 be the number of children of an internal node uuu
. This is also known as the degree of uuu
. In general, we have the bounds a≤m≤ba \le m \le ba≤m≤b
.
The root is an exception, with the bound 2≤m≤b2 \le m \le b2≤m≤b
.
(a,b)-search trees
Lecture Note 3, Page 80.
An (a,b)-search tree is an (a,b)-tree whose nodes are organized as an external search tree, which means items are only stored in leaves. Leaves are also called external nodes.
Figure 35: Organization of external and internal nodes in (a,b)-search trees
Leaves: (a′,b′)(a', b')(a′,b′)
 where 1≤a′≤b′1 \le a' \le b'1≤a′≤b′
.
Default assumption for leaves: a′=b′=1a' = b' = 1a′=b′=1
.
Reorganization of nodes
For an internal node uuu
,
​uuu
 is overfull if its degree is b+1b+1b+1
.
​uuu
 is underfull if its degree is a−1a-1a−1
.
Simple Remedy: borrow or donate children
Figure 36: Borrowing or donating as simple remedy
Strong Remedy: when simple remedy fails.
Split an overfull node
​
​
Merge an underfull node
​
​
Split-Merge Inequality
a≤b+12\begin{gather*} a \le {{b + 1} \over {2}} \end{gather*}a≤2b+1​​
This is a combination of split inequality (a≤⌊b+12⌋a \le \lfloor{{b+1}\over{2}}\rfloora≤⌊2b+1​⌋
) and merge inequality (a≤b+12a \le {{b + 1} \over {2}}a≤2b+1​
). Since aaa
 and bbb
 are integers, these two are equivalent.
Recurrences
Dynamic Programming
Last modified 1yr ago