Tree-rotations

  • November 2019
  • PDF

This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA


Overview

Download & View Tree-rotations as PDF for free.

More details

  • Words: 629
  • Pages: 11
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