AVL Tree Insertion An LL Rotation I 12 y z x z y
4 8
16 z 8 10
2 4
w y x 1 2
6
6
14 10
x = w 1
rotateLL(z)
AVL Tree Insertion – An LL Rotation
AVL Tree Insertion – An LL Rotation I
AVL Tree Insertion An LL Rotation II 12 y z x z y
4 8
16 z 8 10
2 4
w y x 1 2
6
6
14 10
x = w 1
rotateLL(z)
AVL Tree Insertion – An LL Rotation II
AVL Tree Insertion An LL Rotation III - Details 12 y z x z y
16
4 8 z 8 10
2 4
y x w 1 2
6
6
14 10
x =w 1
rotateLL(z)
AVL Tree Insertion - An LL Rotation III - Details
AVL Tree Insertion An LR Rotation
12 z x 16
6 8 y z x
z 8 10
4 6 y
() 5 6
4 2
y x
()
14 10
x 2
55
1. rotateRR(y) 2. rotateLL(z)
AVL Tree Insertion - An LR Rotation II
AVL Tree Insertion An LR Rotation
12 z x 16
6 8 y z x
z 8 10
4 6 y
() 5 6
4 2
y x
()
14 10
x 2
55
1. rotateRR(y) 2. rotateLL(z)
AVL Tree Insertion - An LR Rotation I
AVL Tree Removal An R0 Imbalance LL Rotation
12 q y z 8 4
16
y
() 10 8
2 4 2
6
z
14
6
AVL Tree Removal - An R0 Imbalance
AVL Tree Removal An R-1 Imbalance (LR Double) (L-1 Imbalance (RR Single)) y 28 z 18 x z y x
18
8 12 8
y 28 12q z 12 16
4 4 8
y 2 4 2
z
10 14 10
6x 6 10 8
16 16 h=2
2
6
6
h=3
10 h=2
h=3
AVL Tree Removal - An R-1, L-1 Imbalance
Red Black Tree Insertion Left Outside Grandchild An LL Rotation
12 16
8 z y
2 4
10 z
y x 1 2 x
14
() 1
4 ()
insert(1) y rotateLL(z) black z red
AVL Tree Insertion – An LL Rotation
Red Black Tree Insertion – An LL Rotation
Red Black Tree Insertion Left Inside Grandchild An LR Rotation
z x 12 8 y x
z 4 8
12 16 x
y
2
10 14
10 6 8
4 2 6
() 5 6
16
10
14
insert(5) x rotateRR(y) black flip(8) z red rotateLL(z)
AVL Tree Insertion – An LL Rotation Red Black Tree Insertion – An LR Rotation
Red Black Tree Removal Case 3 and Case 1 53 29 y v z
y z y
40 29 7
84 53
z v 40 52
29 7
y x
84
40 68
x
v 7
35
52
35
52
remove(7): black of z (red) y colour x z black red z black
Case replace 3: 1: `double' black v withsibling `special blackyat on null' v, right with red sibling a red child. y on right. z y red, colour(z) y black rotateRR(z) x black, z black, restructure rotateRR(z) at v
Red Black Tree Removal – Case 1, 3
68
Red Black Tree Removal Case 2 z 29 v z 53
6 y
y
v 4
8
40
84
52
68
remove(8) y red z black
Case 2: Sibling y isis black black leaf leaf on right onon left left with with with replace v with `special null' two black (null) children children y red z is red black so(root so z restructure black so no restructure) at z
Red Black Tree Removal – Case 2