COMP90038 – Algorithms and Complexity Lecture 15
COMP90038 Algorithms and Complexity
Lecture 15: Balanced Trees
(with thanks to Harald Søndergaard & Michael Kirley)
Casey Myers Casey.Myers@unimelb.edu.au David Caro Building (Physics) 274
COMP90038 – Algorithms and Complexity
Lecture 15
Review from Lecture 14
• A binary search tree, or BST, is a binary tree that stores elements in all internal nodes, with each sin-tree satisfying the BST property:
Let the root be 𝑟; then each element in the left subtree is smaller that 𝑟 and each element in the right sub-tree is larger than 𝑟. (For simplicity, we assume that all keys are different.)
COMP90038 – Algorithms and Complexity
Lecture 15
Review from Lecture 14
• BSTs are useful for search applications. To search for 𝑘 in a BST, compare against its root r. If r = 𝑘, we are done; otherwise search in the left or right sub-tree, according to k < r or k > r.
• If a BST with n elements is “reasonably” balanced, search involves in the worst case, Θ(log 𝑛) comparisons.
COMP90038 – Algorithms and Complexity
Lecture 15
Review from Lecture 14
• If the BST is not well balanced, search performance degrades, and may be as bad as linear search:
COMP90038 – Algorithms and Complexity
Lecture 15
Approaches to Balanced Binary Search Trees
• To optimise the performance of BST search, it is important to keep trees (reasonably) balanced
• Instance simplification approaches: Self-balancing trees:
– AVL trees
– Red-black trees
– Splay trees
• Representational changes:
– 2-3 trees
– 2-3-4 trees
– B-trees
COMP90038 – Algorithms and Complexity
Lecture 15
Approaches to Balanced Binary Search Trees
• To optimise the performance of BST search, it is important to keep trees (reasonably) balanced
• Instance simplification approaches: Self-balancing trees:
– AVL trees
– Red-black trees
– Splay trees
• Representational changes:
– 2-3 trees
– 2-3-4 trees
– B-trees
COMP90038 – Algorithms and Complexity Lecture 15
AVL Trees
• Named after Adelson-Velsky and Landis
• Recall that we defined the height of the empty tree as -1.
• For a binary (sub-) tree, let the balance factor be the difference between the height of its left sub-tree and that of its right sub-tree.
• An AVL tree is a BST in which the balance factor is -1, 0, or 1, for every sub-tree.
COMP90038 – Algorithms and Complexity
Lecture 15
AVL Trees: Examples and Counter-Examples
• Which of these are AVL trees?
COMP90038 – Algorithms and Complexity
Lecture 15
AVL Trees: Examples and Counter-Examples
• Which of these are AVL trees?
✘
✘
COMP90038 – Algorithms and Complexity
Lecture 15
AVL Trees: Examples and Counter-Examples
• Which of these are AVL trees?
H: 3, 1; BF: 3-1 = 2
COMP90038 – Algorithms and Complexity
Lecture 15
AVL Trees: Examples and Counter-Examples
• Which of these are AVL trees?
H: 3, 3; BF: 3-3 = 0
COMP90038 – Algorithms and Complexity
Lecture 15
AVL Trees: Examples and Counter-Examples
• Which of these are AVL trees?
H: 0, 1; BF: 0-1 = -1
COMP90038 – Algorithms and Complexity
Lecture 15
AVL Trees: Examples and Counter-Examples
• Which of these are AVL trees?
H: 0, 2; BF: 0-2 = -2
COMP90038 – Algorithms and Complexity Lecture 15
Building an AVL Tree
• As with standard BSTs, insertion of a new mode always takes place at the fringe of the tree.
• If insertion of the new node makes the AVL tree unbalanced (some nodes get balance factors of 2 or -2), transform the tree to regain its balance.
• Regaining balance can achieved with one or two simple, local transformtions, so- called rotations.
COMP90038 – Algorithms and Complexity Lecture 15
AVL Trees: R-Rotation
COMP90038 – Algorithms and Complexity Lecture 15
AVL Trees: L-Rotation
COMP90038 – Algorithms and Complexity
Lecture 15
AVL Trees: LR-Rotation
COMP90038 – Algorithms and Complexity
Lecture 15
AVL Trees: RL-Rotation
COMP90038 – Algorithms and Complexity
Lecture 15
AVL Trees: Where to Perform the Rotation
• Along an unbalanced path, we may have several nodes with balance factor 2 (or -2).
• It is always the lowest unbalanced subtree that is re-balanced.
COMP90038 – Algorithms and Complexity
Lecture 15
AVL Trees: Where to Perform the Rotation
• Along an unbalanced path, we may have several nodes with balance factor 2 (or -2). H: 3, 1; BF: 3-1 = 2
4
H: 0, 2; BF: 0-2 = -2 15
2
3
H: 0, 0; BF: 0-0 = 0 H: 0, 1; BF: 0-1 = -1
H: 0, 0; BF: 0-0 = 0
• It is always the lowest unbalanced subtree that is re-balanced.
COMP90038 – Algorithms and Complexity
Lecture 15
AVL Trees: Where to Perform the Rotation
• Along an unbalanced path, we may have several nodes with balance factor 2 (or -2).
4 15
⇒
4 25
213 3
• It is always the lowest unbalanced subtree that is re-balanced.
COMP90038 – Algorithms and Complexity Lecture 15
AVL Trees: Example
• Insert each of these number into the AVL tree in order: 14, 17, 11, 7, 53, 4, 13, 12
COMP90038 – Algorithms and Complexity Lecture 15
AVL Trees: Example
• Insert each of these number into the AVL tree in order: 14, 17, 11, 7, 53, 4, 13, 12 14
11
17
7
53
COMP90038 – Algorithms and Complexity Lecture 15
AVL Trees: Example
• Insert each of these number into the AVL tree in order: 14, 17, 11, 7, 53, 4, 13, 12
14
11 17 ⇒ 11 17
7 53 7 53
H: 1, 0; BF: 1-0 = 1 H: 0, 0; BF: 0-0 = 0
14
H: 2, 0; BF: 2-0 = 2
4
COMP90038 – Algorithms and Complexity Lecture 15
AVL Trees: Example
• Insert each of these number into the AVL tree in order: 14, 17, 11, 7, 53, 4, 13, 12 14 14
11 17 ⇒ 11 17
7 53 7 53
4
COMP90038 – Algorithms and Complexity Lecture 15
AVL Trees: Example
•
Insert each of these number into the AVL tree in order: 14, 17, 11, 7, 53, 4, 13, 12 14 14
11 17 ⇒ 7 17
7 53 4 11 53
4
COMP90038 – Algorithms and Complexity Lecture 15
AVL Trees: Example
• Insert each of these number into the AVL tree in order: 14, 17, 11, 7, 53, 4, 13, 12 14
7 17 11
4
53 13
COMP90038 – Algorithms and Complexity Lecture 15
AVL Trees: Example
• Insert each of these number into the AVL tree in order: 14, 17, 11, 7, 53, 4, 13, 12 14 14
7 17 ⇒ 7 17
4 11 53 4 11 53
13
13
12
COMP90038 – Algorithms and Complexity Lecture 15
AVL Trees: Example
• Insert each of these number into the AVL tree in order: 14, 17, 11, 7, 53, 4, 13, 12 14
7 17 11
4
53
H: 1, 0; BF: 1-0 = 1
12
H: 0, 2; BF: 0-2 = -2
13
H: 0, 0; BF: 0-0 = 0
COMP90038 – Algorithms and Complexity Lecture 15
AVL Trees: Example
• Insert each of these number into the AVL tree in order: 14, 17, 11, 7, 53, 4, 13, 12 14
7 17 11
4
53 13
12
COMP90038 – Algorithms and Complexity Lecture 15
AVL Trees: Example
• Insert each of these number into the AVL tree in order: 14, 17, 11, 7, 53, 4, 13, 12 14 14
7 17 ⇒ 7 17
4 11 53 4 12 53
13 1113 12
COMP90038 – Algorithms and Complexity
Lecture 15
AVL Trees: The Single Rotation, Generally
• This shows an R-rotation; an L-rotation is similar.
COMP90038 – Algorithms and Complexity
Lecture 15
AVL Trees: The Single Rotation, Generally
• This shows an LR-rotation; an RL-rotation is similar.
COMP90038 – Algorithms and Complexity Lecture 15
AVL Trees: Example
• Insert each of these number into the AVL tree in order: 5, 6, 8, 3, 2, 4, 7
COMP90038 – Algorithms and Complexity Lecture 15
AVL Trees: Example
• Insert each of these number into the AVL tree in order: 5, 6, 8, 3, 2, 4, 7 5 H: 0, 2; BF: 0-2 = -2 6
6⇒58 8
COMP90038 – Algorithms and Complexity Lecture 15
AVL Trees: Example
• Insert each of these number into the AVL tree in order: 5, 6, 8, 3, 2, 4, 7 6
2
H: 2, 0; BF: 2-0 = 2
58 3
COMP90038 – Algorithms and Complexity Lecture 15
AVL Trees: Example
• Insert each of these number into the AVL tree in order: 5, 6, 8, 3, 2, 4, 7 66
58⇒38
32 2
5
COMP90038 – Algorithms and Complexity Lecture 15
AVL Trees: Example
• Insert each of these number into the AVL tree in order: 5, 6, 8, 3, 2, 4, 7
6 38 5
2
4
COMP90038 – Algorithms and Complexity Lecture 15
AVL Trees: Example
• Insert each of these number into the AVL tree in order: 5, 6, 8, 3, 2, 4, 7 H: 3, 1; BF: 3-1 = 2
6 38 5
2
4
COMP90038 – Algorithms and Complexity Lecture 15
AVL Trees: Example
• Insert each of these number into the AVL tree in order: 5, 6, 8, 3, 2, 4, 7
6 38 5
2
4
COMP90038 – Algorithms and Complexity Lecture 15
AVL Trees: Example
• Insert each of these number into the AVL tree in order: 5, 6, 8, 3, 2, 4, 7
6
6
383⇒ 255
4
5 3
6
COMP90038 – Algorithms and Complexity Lecture 15
AVL Trees: Example
• Insert each of these number into the AVL tree in order: 5, 6, 8, 3, 2, 4, 7
65 38⇒36 25 248
4
COMP90038 – Algorithms and Complexity Lecture 15
AVL Trees: Example
• Insert each of these number into the AVL tree in order: 5, 6, 8, 3, 2, 4, 7 5
36 48
7
2
COMP90038 – Algorithms and Complexity Lecture 15
AVL Trees: Example
• Insert each of these number into the AVL tree in order: 5, 6, 8, 3, 2, 4, 7 5
36 48
7
2
COMP90038 – Algorithms and Complexity Lecture 15
AVL Trees: Example
• Insert each of these number into the AVL tree in order: 5, 6, 8, 3, 2, 4, 7
5 36
2482468 7
⇒
5 37
COMP90038 – Algorithms and Complexity
Lecture 15
Properties of AVL Trees
• The notion of “balance” that is implied by the AVL condition is sufficient to guarantee that the depth of an AVL tree with 𝑛 nodes is Θ log 𝑛 .
• For random data, the depth is very close to 𝑙𝑜𝑔!𝑛, the optimum.
• In the worst case, search will need at most 45% more comparisons than with a
perfectly balanced BST.
• Deletion is harder to implement that insertion but also Θ log 𝑛 .
COMP90038 – Algorithms and Complexity
Lecture 15
Other Kinds of Balanced Trees
• A red-black tree is a BST with a slightly different concept of “balanced”. Its nodes are coloured red of black, so that:
• No red node has a red child.
• Every path from the root to the fringe has the same number of black nodes.
A splay tree is a BST which is not only self-adjusting, but also adaptive. Frequently accessed items are brought closer to the root, so their access becomes cheaper.
A worst-case red-black tree (the longest path is twice as long as the shortest path).
COMP90038 – Algorithms and Complexity Lecture 15
2-3 Trees
• 2-3 trees and 2-3-4 trees are search trees that allow more than one item to be stored in a tree node.
• As with BSTs, a node that holds a single item has (at most) two children.
• A node that holds two items (a so-called 3-node) has (at most) three children.
• And for 2-3-4 trees, a node that holds three items (a 4-node) has (at most) four children.
• This allows for a simple way of keeping search trees balanced.
COMP90038 – Algorithms and Complexity Lecture 15
2-Nodes and 3-Nodes
COMP90038 – Algorithms and Complexity Lecture 15
Insertion in a 2-3 Tree
• To insert a key 𝑘, pretend that we are searching for 𝑘.
• This will take us to a leaf node in the tree, where 𝑘 should now be inserted; if the
node we find there is a 2-node, 𝑘 can be inserted without further ado.
• Otherwise we had a 3-node, and the two inhabitants, together with 𝑘, momentarily
form a node with three elements; in sorted order, call them 𝑘”, 𝑘! and 𝑘#.
• We now split the node, so that 𝑘” and 𝑘# form their own individual 2-nodes. The
middle key, 𝑘! is promoted to the parent node.
• The promotion may cause the parent node to overflow, in which case it gets split the same way. The only time the tree’s height changes is when the root overflows.
COMP90038 – Algorithms and Complexity
Lecture 15
Example: Build a 2-3 Tree from 9, 5, 8, 3, 2, 4, 7
COMP90038 – Algorithms and Complexity
Lecture 15
Example: Build a 2-3 Tree from 9, 5, 8, 3, 2, 4, 7
COMP90038 – Algorithms and Complexity
Lecture 15
Exercise: 2-3 Tree Construction: C, O, M, P, U, T, I, N, G
• Build the 2-3 tree that results from inserting these keys, in the given order, into an initially empty tree:
C, O, M, P, U, T, I, N, G
COMP90038 – Algorithms and Complexity
Lecture 15
Exercise: 2-3 Tree Construction: C, O, M, P, U, T, I, N, G
M C
M,P
C O U
⇒
C O,P C O
C ⇒ C, O MM
C, M, O
O,P,U
⇒
M,P ⇒ C O T,U
M,P
C,I O T,U
⇒⇒
⇒
⇒
COMP90038 – Algorithms and Complexity
Lecture 15
Exercise: 2-3 Tree Construction: C, O, M, P, U, T, I, N, G
M,P ⇒ M,P ⇒ M,P
C,I N,O T,U
T,U
T,U
C,I
O T,U
C,G,I N,O G,M,P
M GP
C,I
N,O
T,U
C
I
N,O
⇒
⇒
COMP90038 – Algorithms and Complexity Lecture 15
2-3 Tree Analysis
• Worst case search time results when all nodes are 2-nodes.
• The relation between the number 𝑛 of nodes and the height h is:
𝑛 = 1+2+4+⋯+2$ = 2$%” −1
• Thatis,𝑙𝑜𝑔! 𝑛+1 =h+1.
• In the best case, all nodes are 3-nodes:
𝑛 = 2+2×3+2×3! +⋯+2×3$ = 3$%” −1
• Thatis,𝑙𝑜𝑔# 𝑛+1 =h+1.
• Hence we have 𝑙𝑜𝑔# 𝑛 + 1 − 1 ≤ h ≤ 𝑙𝑜𝑔! 𝑛 + 1 − 1 .
• Useful formula: ∑) 𝑎& = *!”#+” , for 𝑎 ≠ 1. &'( *+”
COMP90038 – Algorithms and Complexity Lecture 15
Coming Up Next
• How to buy time, by spending a bit more space (Levitin 7.1 & 7.2).