AVL Tree Review and Code
●
Today we will continue to to review AVL trees and
work through sample code
●
The first review step will be to examine a tree
again and add in the actual height numbers to
show the heights of the tree
●
We will then add in nodes and see when it
becomes unbalanced
Proper AVL Tree
Closer examination of the height
●
Height of the left sub-tree – height of the right
sub-tree
●
We can do right – left if we want but in this case
we have done left – right
●
Root = 3 – 2 = 1
●
Left Node (9) = 1 – 2 = -1
●
Right of (9)(21) = 1 – 0 = 1
●
Left of (9)(8) = leaf = 0
●
Left of (21)(11) = leaf = 0
●
Right of root (53) = 0 – 1 = -1
●
Right of 53(65) = leaf = 0
AVL Tree
●
This tree is a proper AVL tree at this point
●
What happens when we need to rotate a tree – if
it is not balanced
●
Let us take a closer at rotation
AVL Tree
●
Since we always have to keep the AVL tree intact
, we will only need to rotate a sub-tree
●
Let us examine the following initial sub-tree
●
AVL Tree
●
We will walk step by step through a left rotation
●
Since y has a left sub-tree, we will assign x to be
the parent of the left sub-tree...
AVL Tree
If the parent of x is null then y becomes the root
Else if x is the left child of p then make y the left
child of p
Else assign y as the right child of p
AVL Tree
●
Last step – make y the parent of x
●
AVL Tree
Now let us do an example of the tree
Let us list out the example…
Root of sub-tree = 50
Left of root = 40
Right of root = 60
Left of 60 = 58
Right of 60 = 70
AVL Left Rotation
First step is x becomes the parent of 58
So x = 50
Left of x = 40 (Same)
Right of x = 58 (Change)
Y = 60 (Same)
Right of Y = 70 (Same)
AVL Left Rotation
Next step is to make Y the “root” or the parent of X
So Y (now root) = 60 (Change)
Right of Y is 70 (Same)
Left of Y = x = 50
Left of x = 40 (Same)
Right of x = 58 (Same)
Now we are balanced
AVL Full Insert Example
●
Seeing the example visually…
Sub-tree to start…
●
AVL Full Insert Example
●
First step of rotation...
●
AVL Full Insert Example
●
End result of rotation
●
AVL Tree
●
Right Rotation – Initial Tree
●
AVL Tree
●
If x has a sub-tree then y becomes the parent of
that sub-tree
●
AVL Tree
●
If x has a sub-tree then y becomes the parent of
that sub-tree
●
AVL Tree
●
If the parent of y is null then x becomes the root
●
Else if y is the right child of its parent then make
x the right child of p
●
Else set x as the left child of p
●
AVL Tree
●
Then make x the parent of y
AVL Tree
●
Another example of using the numbers…
●
Y = 70
●
X = 60
●
Right of X = 65
●
Left of X = 55
●
Right of Y = 80
AVL Tree
●
Another example of using the numbers…
●
Y = 70
●
Right of Y = 80 (Same)
●
Left of Y = 65 (Change)
●
X = 60
●
Left of X = 55
AVL Tree
●
X becomes root (60)
●
Y Right of X= 70 (Change)
●
Right of Y = 80 (Same)
●
Left of Y = 65 (Same)
●
Left of X = 55
AVL Tree
●
Right rotation visual example
●
AVL Tree
●
Step one
●
AVL Tree
●
Final Step
●
AVL Tree
●
Example using code
●
First tree
●
●
AVL Tree
●
Printed Out Tree
●
R----33
●
L----13
●
| L----9
●
| | L----8
●
| | R----11
●
| R----21
●
R----53
●
R----61
●
AVL Tree
●
Delete 13
●
Right after the delete
●
●
AVL Tree
●
We have to rebalance with height problem on the
left
●
●
AVL Tree
●
The 9 gets moved up and 21 becomes a right
child of 9 and the 11 becomes a left child of 21
●
●
AVL Tree
●
Example from code…
●
R----33
●
L----9
●
| L----8
●
| R----21
●
| L----11
●
R----53
●
R----61
