📘
📘
📘
📘
Notes
Fundamental Algorithms
Search
⌃K
Links

Search Trees

Binary Search Trees (BST)

Related homework questions: h3-6

Binary Tree

A binary tree
TT
is a set
NN
of nodes where each node
u0u_0
has two pointers,
u0u_0
.left and
u0u_0
.right.
The size of
TT
is
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
hh
:
μ(h)=h+1\begin{gather*} \mu(h) = h + 1 \end{gather*}
Maximum number of nodes in a binary tree of height
hh
:
M(h)=2h+11\begin{gather*} M(h) = 2^{h+1} - 1 \end{gather*}
The minimum height of binary trees with
nn
nodes:
hlg(n+1)1\begin{gather*} h \ge \lg(n + 1) - 1 \end{gather*}

Binary Search Tree

A binary tree is a binary search tree if each node
uTu \in T
has a field
uu
.key that satisfies the BST property:
uL.key<u.keyuR.key\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
uu
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*}

Insertion and Deletion Algorithms

UPDATE PHASE: Insert or delete as we would in a binary search tree.
REBALANCE PHASE: Let
xx
be parent of the node that was just inserted, or just cut during deletion, in the UPDATE PHASE. THe path from
xx
to the root will be called the rebalance path. We now move up this path, rebalancing nodes along this path as necessary.
Let
uu
be the first unbalanced node we encounter along the rebalance path from bottom to top. It is clear that
uu
has a balance of
±2\pm 2
. The situation is illustrated below:
Figure 16: Node u is unbalanced after insertion or deletion

Insertion Rebalancing

CASE (I.a):
hL=hh_L = h
and
hR=h1h_R = h - 1
. This means that the inserted node is in the left subtree of
vv
. In this case, we rotate
vv
, the result would be balanced. Moreover, the height of
uu
is now
h+1h+1
. We call this the "single-rotation" case.
Figure 17: AVL Insertion: CASE (I.a)
CASE (I.b):
hL=h1h_L = h - 1
and
hR=hh_R = h
. This means that the inserted node is in the right subtree of
vv
. In this case, let us expand the subtree
DD
and let
ww
be its root. The two children of
ww
will have heights
hδh - \delta
and
hδh - \delta'
where
δ,δ{1,2}\delta, \delta' \in \{1, 2\}
. Now a double-rotation at
ww
results in a balanced tree of height
h+1h+1
rooted at
ww
.
Figure 17: AVL Insertion: CASE (I.b)

Deletion Rebalancing

CASE (D.a):
hL=hh_L = h
and
hR=h1h_R = h - 1
. This is like case (I.a) and treated in the same way, namely a single rotation at
vv
. Now
uu
is replaced by
vv
after this rotation, and the new height of
vv
is
h+1h+1
. Now
uu
is AVL balanced. However, since the original height is
h+2h + 2
, there may beb unbalanced node further up the rebalance path. Thus, this is a non-terminal case.
CASE (D.b):
hL=h1h_L = h - 1
and
hR=hh_R = h
. This is like case (I.b) and treated in the same way, namely a double rotation at
ww
. Again, this is a non-terminal case.
CASE (D.c):
hL=hR=hh_L = h_R = h
. This case is new, we simply rotate at
vv
. We check that
vv
is balanced and has height
h+2h+2
. Since
vv
is in the place of
uu
which has height
h+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 unil\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:
ratio(u):=esize(u.left)esize(u.right)\begin{gather*} ratio(u) := {esize(u.left) \over {esize(u.right)}} \end{gather*}

ρ-ratio

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

Insertion and Deletion Algorithms

Example:
ho=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
xx
in
TT
. If deletion, we will physically "cut" the leaf
xx
from
TT
.
REBALANCE PHASE: Let
uu
be the parent of
xx
. Clearly, every node that is not RB balanced must lie on the root-path of
uu
. 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
    mm
    be the number of children of an internal node
    uu
    . This is also known as the degree of
    uu
    . In general, we have the bounds
    amba \le m \le b
    .
    The root is an exception, with the bound
    2mb2 \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)(a', b')
where
1ab1 \le a' \le b'
.
Default assumption for leaves:
a=b=1a' = b' = 1
.

Reorganization of nodes

For an internal node
uu
,
  • uu
    is overfull if its degree is
    b+1b+1
    .
  • uu
    is underfull if its degree is
    a1a-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
    Figure 35: Splitting an overfull node
  • Merge an underfull node
    Figure 37: Merging an underfull node

Split-Merge Inequality

ab+12\begin{gather*} a \le {{b + 1} \over {2}} \end{gather*}
This is a combination of split inequality (
ab+12a \le \lfloor{{b+1}\over{2}}\rfloor
) and merge inequality (
ab+12a \le {{b + 1} \over {2}}
). Since
aa
and
bb
are integers, these two are equivalent.