(Image from wikipedia [1])

- Rotate Left with Labels:

- Rotate Right with Labels:

1:

// rotations.cpp - download here

2:

3:

void

rotateRight(

TreeNode

*

gr,

TreeNode

*

par,

TreeNode

*

ch)

{

4:

//grandparent child becomes ch

5:

if

(

gr->

getRight(

)

=

=

par)

{

6:

gr->

setRight(

ch)

;

7:

}

else

{

8:

gr->

setLeft(

ch)

;

9:

}

10:

11:

TreeNode

*

ch_right

=

ch->

getRight(

)

;

12:

par->

setLeft(

ch_right)

;

13:

ch->

setRight(

par)

;

14:

}

15:

16:

void

rotateLeft(

TreeNode

*

gr,

TreeNode

*

par,

TreeNode

*

ch)

{

17:

//grandparent child becomes ch

18:

if

(

gr->

getRight(

)

=

=

par)

{

19:

gr->

setRight(

ch)

;

20:

}

else

{

21:

gr->

setLeft(

ch)

;

22:

}

23:

24:

TreeNode

*

ch_left

=

ch->

getLeft(

)

;

25:

par->

setRight(

ch_left)

;

26:

ch->

setLeft(

par)

;

27:

}

- Start:

- Rotate right (20, 10):

- Rotate right (10, 5):

- Rotate right (5, 2):

- Rotate right (20, 15):

- Apply algorithm to remainder:

- Start:

- Rotate left at 5 and 11, 17, 43, 53

- Rotate left at 11, 43. We are done because the maximum height difference is one.

1:

algorithm

createBackbone(

root)

2:

tmp

=

root;

3:

while

(

tmp

!=

NULL)

4:

if

tmp

has

a

left

child

5:

rotate

right

about

tmp

and

it's

left

child;

6:

set

tmp

to

the

left

child

that

just

became

the

parent;

7:

else

8:

set

tmp

to

the

right

child

9:

10:

algorithm

createPerfectTree(

n)

11:

make

n/2

left

rotations

starting

from

the

top;

12:

while

(

n

>

1)

13:

n

=

n

/

2;

14:

make

n

left

rotations

starting

from

the

top;

- In AVL Trees each node has a balance factor that specify the difference in height between the left and right subtrees (balance = right_height - left_height).
- The balance factors should always be -1, 0 or +1. Otherwise rebalancing is needed
- AVL Trees do not guarentee that the tree is always perfectly balanced.
- AVL Trees are similar to Red-Black Trees.
- AVL Trees have faster lookup (empirically) than Red-Black Trees because the balancing is more rigid
- Red-Black Trees have faster insertion (empirically) and removal because the balancing is less rigid

- AVL Tree Time Complexities (Worst Case):
- Search: O(lg(n))
- Insert: O(lg(n))
- Delete: O(lg(n))

- Case: +2, +1 (parent is 2 and signs are the same)

- Start:

- Show Node 53

- Insert value

- Right Rotation around 20 and 40

- Start:
- Case: +2, -1 (parent is 2 and signs are the different)

- Start:

- Show Node 30

- Insert value

- Left Rotation around 30 and 40

- Right Rotation with Parent as Root

- Start:
- There are mirror images of step 3 not shown here

- Deletion by copying is prefered because there is less balancing needed.

- Zig Step: The parent is the root and the found node is the left child. A right rotation is done at the root

- Zag Step: The parent is the root and the found node is the right child. A left rotation is done at the root

- Zig-zig Step: The path from the grandparent to the found node was two left pointers. A right rotation is done at the grandparent and parent

- Zag-zag Step: The path from the grandparent to the found node was two right pointers. A left rotation is done at the grandparent and parent

- Zag-zig Step: The path from the grandparent to the found node was a left pointer followed by a right pointer. A left rotation is done at the parent and a right at the grandparent

- Zig-zag Step: The path from the grandparent to the found node was a right pointer followed by a left pointer. A right rotation is done at the parent and a left at the grandparent

- Splay the node to be deleted to the top
- Make the left child the root
- Make the left child's right sub-tree and attach it to the leftmost node of the right child
- Make the right child the new right child of the new root

- http://en.wikipedia.org/wiki/Tree_rotation
- http://en.wikipedia.org/wiki/AVL_tree
- http://en.wikipedia.org/wiki/Splay_tree