COMP2100/COMP6442
Data Structures Part III
Sid Chi
[Lecture 4]
–
Kin Chau
1
Recap from Previous Lecture
• Balanced search tree
• Belong to binary search tree
• But with a height of O(log(n)) guaranteed for n items
• Height h = maximum number of edges from the root to a leaf
• Examples
• Red-black tree • AVL tree
• B-tree
h ≈ log(n)
2
Tree Rotation
• Our basic operation for changing tree structure is called rotation • Rotation preserves inorder key ordering
• How would tree rotation actually work?
y rightRotate(y) x xC Ay
A B leftRotate(x) B C
3
Example
• Left Rotate at node 9 7
leftRotate(x) 7
x
5 9y5x12
812 9
11 811
y
4
AVL Tree
• AVL tree is binary search tree that has a height difference between with left and right subtrees of a node is at most 1
• In BST, left subtree keys are less than the root and right subtree keys are greater than the root
• Each node has a height of the subtree rooted at that node
• Balance:
• Define the balance of a node n
• b(n) = Height with only Right Subtree – Height with only Left Subtree • Legal values for AVL tree: b(n) in {-1, 0, 1}
• Otherwise, b(n) > 1 or b(n) < -1, then it is an unbalanced AVL tree
5
AVL Tree Example
height Key
balance Key
3 35
-1 35
2 15
1 50
0 15
-1 50
1 7
1 16
0 40 0 17
0 7
1 16
0 40 0 17
0 5
0 10
0 5
0 10
6
AVL Tree Insertion
• Adding a new node cannot make an unbalanced parent
• Assume the parent p's balance in b(p) in {-1, 0, 1} before insertion • The parent will have
• b(p) = 0 if already has a child,
• b(p) = 1 if a new left child, or b(p) = -1 if a new right child
• Otherwise it would not be our parent or the parent would have been
unbalanced already
07 p
-1 7 1 7 0 7 ppp
05 01005010 Still balanced Still balanced
7
AVL Tree Insertion
• Even if the parent is not unbalanced, it is possible that the grandparent becomes unbalanced
• Hence, we need a way to re-balance the grandparent
-1 15
-2 15 -1 15 0 7
-2 15 17
0 7
-1 7
05 05 Unbalanced Unbalanced
8
AVL Tree Insertion
• Rotations are required to balance AVL tree
• Case 1 (left-left or right-right): Requires 1 rotation
• Case 2 (left-right or right-left): Requires 2 rotations (first convert to Case 1)
-2 9 -1 7
1 rotation
1 rotation
2 5
1 7 Case 1
0 5
Case 1
-29 05 09 27
0 9
0 7
-1 5
Case 2 0 7
2 rotations
2 rotations
-1 9 0 5 Case 2
9
AVL Tree Insertion
• Insert[n]
• If empty tree, then
• Set n as root, b(n) = 0. Return
• Else insert n (by walking the tree to a leaf p and inserting the new node as its
child), set b(n) = 0, and look at its parent p
• If b(p) was -1, then b(p) = 0. Return
• If b(p) was +1, then b(p) = 0. Return
• If b(p) was 0, then update b(p) and call Insert-fix[p, n]
10
AVL Tree Insertion
• Basic idea:
• Work up ancestor chain updating balances of the ancestor chain or fix a node
that is unbalanced
• Insert-fix[p, n]
• Precondition: p and n are balanced: b(p), b(n) in {-1,0,1}
• Postcondition: g, p, and n are balanced: b(g), b(p), b(n) in {-1,0,1}
• If p is null or p.parent is null, return • Let g p.parent
11
AVL Tree Insertion
• Insert-fix[p, n]
• Assume p is left child of g // If p is right child, swap left/right, +/-
• Update b(g) // Update g's balance to new accurate value for now
• Case a: if b(g) = 0, return
• Case b: if b(g) = -1, Insert-fix[g, p] // Fix recursively
• Case c: if b(g) = -2
• If Case 1, then rotateRight(g);
• If Case 2, then rotateLeft(p); rotateRight(g);
12
Example
1 10
30
2 10
Case 1
15
-1 20
0 20
0 20
1 20
0 10
1 10
0 30
0 30
0 30
0 15
25
0 20
0 20
025
Case 2
0 20
-115 025
12
0 12
-1 30
2 10 0 12
-1 30
1 10
-1 30
0 10
0 15
015 025 13
Example
0 20
5
-1 20
015 025
3
-2 20
-1 30
015 025 Case 1
-1 20
0 25
0 12
-1 30
-1 12
-1 30
-2 12
0 10
0 15
0 25
-110
-210
0 5
-1 5
-1 20
-1 30 112 025
0 15
03 -2 20
0 10 05
0 8
-2 12
-1 30
8
Case 2
-1 5
015 025
112
-130
03
110
03
08 0305 14
0 10
0 15
AVL Tree Deletion
• Deletion operations may also require rebalancing via rotations
• The key idea is to update the balance of the nodes on the ancestor
pathway
• If an ancestor gets out of balance then perform rotations to rebalance
• Unlike insertion, rotations during deletion does not mean you are done, but need to continue recursively to the root
• More cases in AVL tree deletion
15
Demo
https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
16
B
• Generalization of binary search trees
• Not binary trees (i.e., more than two children per node) • The “B” stands for Bayer (the inventor)
• Designed for searching data stored on block-oriented devices • Map tree nodes into blocks
• Balanced tree
• By keeping all leaves at the same level
• Each node can hold multiple items and have multiple children
• B-tree grows and shrinks from the root
• Binary search tree only grows downward and also shrink from downward
-
Tree
17
B
-
Tree Structure
d1 d2 d3 d4
a a ?d1 d4? f f 12 12
d1 ? d2 d2 ? d3 d3 ? d4
b1 b2 b3 c1 c2 c3 e1
18
Example
4 11 18 21
1 3 24 25
6 8 9 12 14 16 20
19
-
Tree Properties
B
• T is a B-tree of degree m ( 3) if it satisfies the following properties:
1. All leaves of T appear on the same level of T
2. Every node of T has at most m children
3. Every node of T, except for the root and the leaves, has at least m/2 children
4. The root of T is either a leaf or has at least two children
5. An internal node with k children stores k-1 keys, and a leaf stores between m/2-1 and m-1 keys. The keys v.keyi, where 1 i k-1, of a node v are maintained in sorted order, v.key1 ... v.keyk-1
6. If v is an internal node with k children, the k-1 keys of v separate the range of keys stored in the subtrees rooted at the children of v. If xi is any key stored in the subtree rooted at the i-th child, the following holds:
x1 v.key1 x2 ...v.keyk-2 xk-1 v.keyk-1 xk
20
Searching B
• Determine the range at each node
• Follow the pointer of the corresponding range as in binary search tree
-
Tree
1 3
? < 4 4 11 18 21 21 < ?
24 25
4 < ? < 11 11 < ? < 18
18 < ? < 21
6 8 9 12 14 16 20
21
Organization of B
• Each non-leave node can have a variable number of children
• Must all be in a specific key range
• Number of child nodes typically vary between m/2 and m (with m–1 keys)
• Split nodes that would otherwise have contained m + 1 children (after insertion)
• Merge nodes that contain less than m/2 children (after deletion)
22
-
Tree
-
B
• Consider B-tree where each node can have up to 2 keys (3 children)
• Add 1: • Add 2: • Add 3:
Tree Insertion
1 1
2 12
3 12
Split
2 13
• Add 4: 2 134
4
23
B
•Add5: 2 134
-
Tree Insertion
5 Split
2 4 135
• Add 6:
24 1356
24 1356
6
• Add 7:
7
24
B
• Add 7:
-
Tree Insertion
24
7 1356
Split
246 135
Promote
4 26
7
135
7 25
-
Tree Insertion Basic Operations
B
• Split:
• When trying to add to a full node • Split node at the central value
• Promote:
• Must insert root of split node higher up • May require a new split
Split
3
2
1 3
1 2
24 6 Promote
135
7
4
26 135
726
B
• Find target leaf L
• If L has less than m - 2 entries :
• Add the entry
• Else
• Repeat
• Allocate new leaf L'
• Pick the m/2 highest keys of L and move them to L'
• Insert highest key of L and corresponding address leaf into the parent • If the parent is full
• Split it and add the middle key to its parent node • Until a parent is found that is not full
-
Tree Insertion (Basic Idea)
27
Demo
https://www.cs.usfca.edu/~galles/visualization/BTree.html
28
Summary
• AVL tree
• Keeping every node's balance in {-1, 0, 1}
• Rotations are required during insertion and deletion • AVL tree is almost balanced tree
• B-tree
• B-tree properties • Insertion
29
Reference
• Visualizations
• https://www.cs.usfca.edu/~galles/visualization/AVLtree.html • https://www.cs.usfca.edu/~galles/visualization/BTree.html
30