Search Trees

Binary Search Trees (BST)

Related homework questions: h3-6

Binary Tree

A binary tree $T$ is a set $N$ of nodes where each node $u_0$ has two pointers, $u_0$.left and $u_0$.right.

The size of $T$ is $|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 $h$:

$$\begin{gather*} \mu(h) = h + 1 \end{gather*}$$

Maximum number of nodes in a binary tree of height $h$:

$$\begin{gather*} M(h) = 2^{h+1} - 1 \end{gather*}$$

The minimum height of binary trees with $n$ nodes:

$$\begin{gather*} h \ge \lg(n + 1) - 1 \end{gather*}$$

Binary Search Tree

A binary tree is a binary search tree if each node $u \in T$ has a field $u$.key that satisfies the BST property:

$$\begin{gather*} u_L.key < u.key \le u_R.key \end{gather*}$$

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 $u$ of a binary tree to be the height of the left subtree minus the height of the right subtree:

$$\begin{gather*} b(u) = h(u.left) - h(u.right) \end{gather*}$$

Insertion and Deletion Algorithms

UPDATE PHASE: Insert or delete as we would in a binary search tree.

REBALANCE PHASE: Let $x$ be parent of the node that was just inserted, or just cut during deletion, in the UPDATE PHASE. THe path from $x$ to the root will be called the rebalance path. We now move up this path, rebalancing nodes along this path as necessary.

Let $u$ be the first unbalanced node we encounter along the rebalance path from bottom to top. It is clear that $u$ has a balance of $\pm 2$. The situation is illustrated below:

Figure 16: Node u is unbalanced after insertion or deletion

Insertion Rebalancing

CASE (I.a): $h_L = h$ and $h_R = h - 1$. This means that the inserted node is in the left subtree of $v$. In this case, we rotate $v$, the result would be balanced. Moreover, the height of $u$ is now $h+1$. We call this the "single-rotation" case.

Figure 17: AVL Insertion: CASE (I.a)

CASE (I.b): $h_L = h - 1$ and $h_R = h$. This means that the inserted node is in the right subtree of $v$. In this case, let us expand the subtree $D$ and let $w$ be its root. The two children of $w$ will have heights $h - \delta$ and $h - \delta'$ where $\delta, \delta' \in \{1, 2\}$. Now a double-rotation at $w$ results in a balanced tree of height $h+1$ rooted at $w$.

Figure 17: AVL Insertion: CASE (I.b)

Deletion Rebalancing

CASE (D.a): $h_L = h$ and $h_R = h - 1$. This is like case (I.a) and treated in the same way, namely a single rotation at $v$. Now $u$ is replaced by $v$ after this rotation, and the new height of $v$ is $h+1$. Now $u$ is AVL balanced. However, since the original height is $h + 2$, there may beb unbalanced node further up the rebalance path. Thus, this is a non-terminal case.

CASE (D.b): $h_L = h - 1$ and $h_R = h$. This is like case (I.b) and treated in the same way, namely a double rotation at $w$. Again, this is a non-terminal case.

CASE (D.c): $h_L = h_R = h$. This case is new, we simply rotate at $v$. We check that $v$ is balanced and has height $h+2$. Since $v$ is in the place of $u$ which has height $h+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:

$$\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*}$$

Ratio:

$$\begin{gather*} ratio(u) := {esize(u.left) \over {esize(u.right)}} \end{gather*}$$

ρ-ratio

$$\begin{gather*} \rho < ratio(u) < 1/\rho \end{gather*}$$

Insertion and Deletion Algorithms

Example: $ho = 1/3$

UPDATE PHASE: Insert or delete as we would in a binary search tree. In insertion, this results in a new leaf $x$ in $T$. If deletion, we will physically "cut" the leaf $x$ from $T$.

REBALANCE PHASE: Let $u$ be the parent of $x$. Clearly, every node that is not RB balanced must lie on the root-path of $u$. 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 $m$ be the number of children of an internal node $u$. This is also known as the degree of $u$. In general, we have the bounds $a \le m \le b$.

  The root is an exception, with the bound $2 \le m \le 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')$ where $1 \le a' \le b'$.

Default assumption for leaves: $a' = b' = 1$.

Reorganization of nodes

For an internal node $u$,

• $u$ is overfull if its degree is $b+1$.

• $u$ is underfull if its degree is $a-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

$$\begin{gather*} a \le {{b + 1} \over {2}} \end{gather*}$$

This is a combination of split inequality ($a \le \lfloor{{b+1}\over{2}}\rfloor$) and merge inequality ($a \le {{b + 1} \over {2}}$). Since $a$ and $b$ are integers, these two are equivalent.