Tutorial
1. Rotations
(c) does improve overall balance:
COMP20007 Design of Algorithms
Week 10 Workshop Solutions
(a) doesn’t improve overall balance:
XL
→
LYAX AV VY
(b) doesn’t improve overall balance:
XL
→
LX UU
U L
→
X
U LX
Balance factor listed below each node. Calculated by subtracting the height of the node’s left subtree from the height of its right subtree.
H
0 DL
B −1 F J 0 N
1 C 0 I −1 M 0 O
0000
2. Balance factor
1
3. AVL Tree Insertion Insertion of A and V is fine, all balanced (balance factor below node): A
1
V
0
Inserting L causes an imbalance at A, and it’s a zig-zag case so we need two rotations to fix it:
A
2
V
A
L
2 →L→0
−1 0
Then, inserting T is fine:
But inserting R gets us into trouble! It causes an imbalance at V. This time it’s a zag-zag case, so we only need one rotation:
L
1
0
L
2 AV
0T−2 →
L
1 AT
00 RV
00
R
L
1 AV
0
T
−1 0
AV V00
−1 0
Next, insertion of E, X, and M cause no imbalances:
L
1 AT
10 ERV
0M−1 1X 00
The final insertion, P, causes a zag-zig problem at R, once again fixed with two rotations:
2
LL
22 ATAT
1 E R −1 V 1 E R −1 V →→
0 M −2 1 X 0 P −2 1 X 1P 0 M−1 0
00 L
1 AT
10 EPV
001 MRX
000
Notes:
• The terms ‘zig’ and ‘zag’ are used to describe imbalances. A ‘zig-zag’ case, for example, refers to a node with an imbalance because of its right (‘zig’) subtree, and the imbalance in that subtree is coming from the left side (‘zag’).
• To determine which type of imbalance we are dealing with, we can look at the sign of the balance factor. If it’s a +2, that means the problem is in the right child. If the right child has a -1 (different sign), then the problem is with it’s left child, and it’s a zig-zag case. Two rotations are needed. If the right child has a +1 (same sign), then the problem is with its right child, and it’s a zig-zig case. One rotation is needed. Likewise, if the sign at the unbalanced node is -2, then the problem is with the left child. If the left child has a balance factor of -1 (same sign), then the problem is with its left child, i.e. it’s a zag-zag case. One rotation is needed. If the left child has a balance factor of +1 (different sign), then the problem is with its right child, i.e. it’s a zag-zig case. Two rotations are needed.
• Always deal with an imbalance at the deepest available point. For example, when inserting P, both R and L became unbalanced, but we dealt with the problem at R. This automatically fixed the problem at L. In reality, we only calculate balance factors on our way back up the tree from the insertion, so we can simply deal with the first imbalance (+2 or -2 balance factor) we encounter. All balance factors have been shown at all stages in the above diagrams, but in reality only the heights would be stored with each node — balance factors would only be calculated on the way back up the tree after an insertion, and only for the nodes on this direct path.
3
4. 2-3 Tree Insertion Inserting the first two elemens results in a leaf node: AL
With the insertion of G, our leaf ends up with 3 elements, so it must be split up – we promote the middle element like so:
G AO
G
ALO
When we add R we get a node with 3 elements and must promote the middle one.
GGO
→
A ALR
Adding I just adds to a leaf node.
GO AILR
Adding H leaves a node with 3 elements, we will fix this my promoting I twice:
GO GIO
→
ARAHLRT I
Inserting O adds to the right most leaf node:
AGL
→
LOR
HIL
→
GO AHLRT
Finally, we can insert M into a leaf node without having to do any promotions, so the final 2-3 tree looks like:
I GO
AHLMRT
4