AVL Trees

Balancing Binary Search

Trees
› Adelson-Velskii and Landis (AVL) trees
(height-balanced trees)
› Splay trees and other self-adjusting trees
› B-trees and other multiway search trees
 AVL Trees
• AVL trees are height-balanced binary
search trees
• Balance factor of a node
› height(left subtree) - height(right subtree)
• An AVL tree has balance factor
calculated at every node
› For every node, heights of left and right
subtree can differ by no more than 1
› Store current heights in each node
 Node Heights
Tree A (AVL) Tree B (AVL)
height=2 BF=1-0=1 2
6 6
1 0 1 1
4 9 4 9
0 0 0 0 0
1 5 1 5 8

height of node = h
balance factor = hleft-hright
empty height = -1
 Node Heights after Insert 7
Tree A (AVL) Tree B (not AVL)
balance factor
2 3 1-(-1) = 2
6 6
1 1 1 2
4 9 4 9
0 0 0 0 0 1 -1
1 5 7 1 5 8
0
7
height of node = h
balance factor = hleft-hright
empty height = -1
 Insert and Rotation in AVL
Trees
• Insert operation may cause balance factor
to become 2 or –2 for some node
› only nodes on the path from insertion point to
root node have possibly changed in height
› So after the Insert, go back up to the root
node by node, updating heights
› If a new balance factor (the difference hleft-
hright) is 2 or –2, adjust tree by rotation around
the node
 Single Rotation in an AVL
Tree
2 2
6 6
1 2 1 1
4 9 4 8
0 0 1 0 0 0 0
1 5 8 1 5 7 9
0
7
 Insertions in AVL Trees
Let the node that needs rebalancing be .

There are 4 cases:

Outside Cases (require single rotation) :
1. Insertion into left subtree of left child of .
2. Insertion into right subtree of right child of .
Inside Cases (require double rotation) :
3. Insertion into right subtree of left child of .
4. Insertion into left subtree of right child of .
The rebalancing is performed through four
separate rotation algorithms.
 AVL Insertion: Outside Case
Consider a valid
AVL subtree
j

k h

h
h
Z
X Y
AVL Insertion: Outside Case
j Inserting into X
destroys the AVL
property at node j
k h

h+1 h Z
Y
X
AVL Insertion: Outside Case
j Do a “right rotation”

k h

h+1 h Z
Y
X
 Single right rotation
j Do a “right rotation”

k h

h+1 h Z
Y
X
Outside Case Completed
“Right rotation” done!
k (“Left rotation” is mirror
symmetric)

h+1
j
h h

X Y Z
AVL property has been restored!
 AVL Insertion: Inside Case
Consider a valid
AVL subtree
j

k h

h h Z
X Y
 AVL Insertion: Inside Case
Inserting into Y
destroys the j Does “right rotation”
restore balance?
AVL property

k
at node j
h

h h+1 Z
X
Y
AVL Insertion: Inside Case

k “Right rotation”
does not restore
balance… now k is
h j out of balance

X h+1
h

Z
Y
 AVL Insertion: Inside Case
Consider the structure
of subtree Y… j
k h

h h+1 Z
X
Y
 AVL Insertion: Inside Case
Y = node i and
subtrees V and W
j
k h

h
i h+1 Z
X h or h-1

V W
AVL Insertion: Inside Case
j We will do a left-right
“double rotation” . . .

k
i Z
X
V W
Double rotation : first rotation
j left rotation complete

i
k Z
W
X V
Double rotation : second
rotation
j Now do a right rotation

i
k Z
W
X V
 Double rotation : second
rotation
right rotation complete

Balance has been

i restored

k j
h h
h or h-1

X V W Z
 Insertion in AVL Trees
• Insert at the leaf (as for all BST)
› only nodes on the path from insertion point to
root node have possibly changed in height
› So after the Insert, go back up to the root
node by node, updating heights
› If a new balance factor (the difference hleft-
hright) is 2 or –2, adjust tree by rotation around
the node
Example of Insertions in an
AVL Tree
2
20 Insert 5, 40
0 1
10 30
0 0
25 35
Example of Insertions in an
AVL Tree
2
3
20 20
1 1 1 2
10 30 10 30
0 0 0 1
0 0
5 25 35 5 25 35
0
40
Now Insert 45
Single rotation (outside case)
3
3
20 20
1 2 1 2
10 30 10 30
0 0 2
0 0
5 25 35 5 25 40 1
0 0
35 45
Imbalance 1 40

0 45
Now Insert 34
Double rotation (inside case)
3
3
20 20
1 3 1 2
10 30 10 35
0 0 2
0 1
5 Imbalance 25 40 5 30 40 1
0
1 35 45 0 0 25 34 45
Insertion of 34 0
34
 AVL Tree Deletion
• Similar but more complex than insertion
› Rotations and double rotations needed to
rebalance
› Imbalance may propagate upward so that
many rotations may be needed.
 B Tree (Introduction)
 A B-Tree is a specialized multi-way tree designed
especially for use on external disk.
 B-tree variants are used mostly today as index
structures in database applications.
 B-Tree nodes should correspond to a block of data
 Each node stores many data items and has many
successors (stores addresses of successor blocks)
 B Trees (Motivation)
 Assume that we use an AVL tree to store about 20 million
records
 We end up with a very deep binary tree with lots of
different disk accesses; log2 20,000,000 is about 24, so this
takes about 0.2 seconds
 We know we can’t improve on the log n lower bound on
search for a binary tree
 But, the solution is to use more branches and thus reduce
the height of the tree!
 As branching increases, depth decreases
 B Tree (Definition)
• A B-tree of order m is an m-way tree (i.e., a tree where
each node may have up to m children) in which:
1. number of keys in each non-leaf node is one less than the
number of its children (m – 1) and these keys partition the
keys in the children in the fashion of a search tree
2. all leaves are on the same level
3. all non-leaf nodes except the root have at least m / 2
children
4. root is either a leaf node, or it has from two to m children
5. leaf node contains no more than m – 1 keys
• The number m should always be odd
 B-tree of Order 5 Example
All internal nodes have at least ceil(5 / 2) = ceil(2.5) = 3 children (and
hence at least 2 keys), other then the root node.
The maximum number of children that a node can have is 5 (so that 4
is the maximum number of keys)
each leaf node must contain at least 2 keys
 B-Tree Insertion
1) B-tree starts with a single root node (which is also a leaf
node) at level 0.
2) Once the root node is full with p – 1 search key values and
when attempt to insert another entry in the tree, the root node
splits into two nodes at level 1.
3) Only the middle value is kept in the root node, and the rest of
the values are split evenly between the other two nodes.
4) When a nonroot node is full and a new entry is inserted into it,
that node is split into two nodes at the same level, and the
middle entry is moved to the parent node along with two
pointers to the new split nodes.
5) If the parent node is full, it is also split.
6) Splitting can propagate all the way to the root node, creating
a new level if the root is split.
 B-Tree Deletion
1) If deletion of a value causes a node to be
less than half full, it is combined with it
neighboring nodes, and this can also
propagate all the way to the root.
- Can reduce the number of tree levels.
 B-Tree Order 5 Insertion
Originally we have an empty B-tree of order 5
Want to insert C N G A H E K Q M F W L T Z D P R X Y S
Order 5 means that a node can have a maximum of 5
children and 4 keys
All nodes other than the root must have a minimum of 2
keys
The first 4 letters get inserted into the same node
 B-Tree Order 5 Insertion Cont.
When we try to insert the H, we find no room in this node,
so we split it into 2 nodes, moving the median item G
up into a new root node.
 B-Tree Order 5 Insertion Cont.
Inserting E, K, and Q proceeds without requiring
any splits
 B-Tree Order 5 Insertion Cont.
Inserting M requires a split
 B-Tree Order 5 Insertion Cont.
The letters F, W, L, and T are then added without
needing any split
 B-Tree Order 5 Insertion Cont.
When Z is added, the rightmost leaf must be split. The
median item T is moved up into the parent node
 B-Tree Order 5 Insertion Cont.
The insertion of D causes the leftmost leaf to be split. D happens to
be the median key and so is the one moved up into the parent
node.
The letters P, R, X, and Y are then added without any need of
splitting
 B-Tree Order 5 Insertion Cont.
Finally, when S is added, the node with N, P, Q, and R splits,
sending the median Q up to the parent.
The parent node is full, so it splits, sending the median M up to
form a new root node.
 B-Tree Order 5 Deletion
Initial B-Tree
 B-Tree Order 5 Deletion Cont.
Delete H
Since H is in a leaf and the leaf has more than the
minimum number of keys, we just remove it.
 B-Tree Order 5 Deletion Cont.
Delete T.
Since T is not in a leaf, we find its successor (the next item in ascending order),
which happens to be W.
Move W up to replace the T. That way, what we really have to do is to delete W
from the leaf .