Search Trees
Related homework questions: h3-6
A binary tree
is a set
of nodes where each node
has two pointers,
.left and
.right.
The size of
is
.
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
:
Maximum number of nodes in a binary tree of height
:
The minimum height of binary trees with
nodes:
A binary tree is a binary search tree if each node
has a field
.key that satisfies the BST property:
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.
More generally, define the balance of any node
of a binary tree to be the height of the left subtree minus the height of the right subtree:
UPDATE PHASE: Insert or delete as we would in a binary search tree.
REBALANCE PHASE: Let
be parent of the node that was just inserted, or just cut during deletion, in the UPDATE PHASE. THe path from
to the root will be called the rebalance path. We now move up this path, rebalancing nodes along this path as necessary.
Let
be the first unbalanced node we encounter along the rebalance path from bottom to top. It is clear that
has a balance of
. The situation is illustrated below:

Figure 16: Node u is unbalanced after insertion or deletion
CASE (I.a):
and
. This means that the inserted node is in the left subtree of
. In this case, we rotate
, the result would be balanced. Moreover, the height of
is now
. We call this the "single-rotation" case.

Figure 17: AVL Insertion: CASE (I.a)
CASE (I.b):
and
. This means that the inserted node is in the right subtree of
. In this case, let us expand the subtree
and let
be its root. The two children of
will have heights
and
where
. Now a double-rotation at
results in a balanced tree of height
rooted at
.

Figure 17: AVL Insertion: CASE (I.b)
CASE (D.a):
and
. This is like case (I.a) and treated in the same way, namely a single rotation at
. Now
is replaced by
after this rotation, and the new height of
is
. Now
is AVL balanced. However, since the original height is
, there may beb unbalanced node further up the rebalance path. Thus, this is a non-terminal case.
CASE (D.b):
and
. This is like case (I.b) and treated in the same way, namely a double rotation at
. Again, this is a non-terminal case.
CASE (D.c):
. This case is new, we simply rotate at
. We check that
is balanced and has height
. Since
is in the place of
which has height
originally, we can safely terminate the rebalancing process.

Figure 20: AVL Deletion: CASE (D.c) rotate(v)
Related homework questions: h4-3
Extended size:
Ratio:
Example:
UPDATE PHASE: Insert or delete as we would in a binary search tree. In insertion, this results in a new leaf
in
. If deletion, we will physically "cut" the leaf
from
.
REBALANCE PHASE: Let
be the parent of
. Clearly, every node that is not RB balanced must lie on the root-path of
. 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)
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: Letbe the number of children of an internal node. This is also known as the degree of. In general, we have the bounds.The root is an exception, with the bound.
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:
where
.
Default assumption for leaves:
.
For an internal node
,
- is overfull if its degree is.
- is underfull if its degree is.
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
This is a combination of split inequality (
) and merge inequality (
). Since
and
are integers, these two are equivalent.
Last modified 1yr ago