Introduction To AVL Trees
Dr. Thomas E. Hicks
Trinity University
[Set all IE margins
to .5]
---------------- Double Rotate Right ----------------
Double Rotate-Right Rotation (a)
Example 1: Add Nodes 50, 10 (Balance Factors are
Red!)
________
|__50__| +1
.
________
|__10__| +0
Add Node 30
________
|__50__| +2 <--
A
.
________
|__10__| -1 <--
B
.
________
|__30__| +0 <--
C/N
Theory - Double Rotate-Right Rotation Needed
(a)
- A is placed to the right of C
- B is placed to the left of C
- Adjust Root/Father
________
|__30__| +0 <--
C
.
.
________
________
|__10__| +0 <--
B
|__50__| +0 <--A
This is the simple/trivial case for Double Rotate-Right
Rotation (N is a leaf node with no sons). After the Double Rotate-Right
Rotation
The Balance Factor of A =
____________
The Balance Factor of B =
____________
The Balance Factor of C =
____________
AVL DOUBLE ROTATE - RIGHT Rotation (General Form
A)
Balanced
subtree
. ? .
(Prior To Insertion which forces a rotation):
. .
__L__._Info_._bf_._R__
|_.__|___A__|_+1_|_._|
.
______________________
|_.__|___B__|_+0_|_._|
Un-Balanced
subtree
. ? .
(After Insertion - now needs a
rotation):
. .
__L__._Info_._bf_._R__
|_.__|___A__|_+2_|_._|
.
______________________
|_.__|___B__|_-1_|_._|
.
______________________
|_.__|___C__|_+0_|_._|
Re-Balanced
subtree
. ? .
(After Double Rotate-Right(a)
Rotation):
. .
__L__._Info_._bf_._R__
|_.__|___C__|_+0_|_._|<...................................
.
.
.
.
.
.
______________________
______________________ h+1
.
|_.__|___B__|_+0_|_._|
|_.__|___A__|_+0_|_._|
.
Add Node 20, 5 - No Rotation
Needed
________
|__30__| +1 <--
C
.
.
________
________
|__10__| +0 <--
B
|__50__| +0 <--A
.
.
________
________
|___5__| +0
|__20__| +0 <--
N
Add Node 25 - Rotation
Needed
________
|__30__| +2 <--
A
.
.
________
________
|__10__| -1 <--
B
|__50__| +0
.
.
________
________
|___5__| +0
|__20__| -1 <--C
.
________
|__25__| +0 <--
N/C-R
Theory - Double Rotate-Right Rotation Needed
(b)
- A is placed to the right of C
- B is placed to the left of C
- That which is to the right of C (C-R) is placed to the left
of A
- That which is to the left of C (C-L) is placed to the right
of B
- That which is to the left of B (B-L) stays to the left of
B
- That which is to the right of A (A-R) stays to the right of
A
- Adjust Root/Father
________
|__20__| +0 <--
C
.
.
________
________
|__10__| +1 <--
B
|__30__| +0 <--A
.
.
.
.
________
________
________
|___5__| +0
<--
B-L
|__25__| -0 <--C-R |__50__| +0 <--A-R
This is
the general case for Rotate-Right Rotation (N is a leaf node with no sons).
After the Rotate-Right Rotation
The Balance Factor
of A = ___________________
The Balance Factor
of B = ___________________
The Balance Factor
of C = ___________________
Let us Add Node 12 Instead of Node 25 (above)- Rotation
Needed
________
|__30__| +2 <--
A
.
.
________
________
|__10__| -1 <--
B
|__50__| +0
.
.
________
________
|___5__| +0
|__20__| +1 <--C
.
________
|__12__| +0 <--
N/C-L
Theory - Double Rotate-Right Rotation Needed
(c)
- A is placed to the right of C
- B is placed to the left of C
- That which is to the right of C (C-R) is placed to the left
of A
- That which is to the left of C (C-L) is placed to the right
of B
- That which is to the left of B (B-L) stays to the left of
B
- That which is to the right of A (A-R) stays to the right of
A
- Adjust Root/Father
________
|__20__| +0 <--
C
.
.
________
________
|__10__| +0 <--
B
|__30__| -1 <--A
.
.
.
________
________
________
|___5__| +0
<--
B-L |__12__| -0 <--C-L
|__50__| +0 <--A-R
This is
the general case for Rotate-Right Rotation (N is a leaf node with no sons).
After the Rotate-Right Rotation
The Balance Factor
of A = ___________________
The Balance Factor
of B = ___________________
The Balance Factor
of C = ___________________
AVL DOUBLE ROTATE - RIGHT Rotation (General Form
B)
Remember that when using AVL Rotations for Insertion, There
will only be four standard forms which trigger rotations. The Double
Rotate-Right rotation must occur whenever A = +2 and B = -1.
Balanced
subtree
. ? .
(Prior To Insertion which forces a rotation):
. .
__L__._Info_._bf_._R__
|_.__|___A__|_+1_|_._|<...................................
.
.
.
.
.
.
______________________
h+1.
|_.__|___B__|_+0_|_._|
.
.
.
.
__________________<.. .
.
.
| A-R
| . .
__________________<..
______________________
|
| . .
|
B-L |
.
|_.__|___C__|_+0_|_._|
|
| . .
|
|
.
.
.
|
| . .
|
| . __________________<..
..>__________________
|
| .h .
|
| . |
C-L |
. .
| C-R
|
|
| . .
|
| .
|
| . .
|
|
|
| . .
|
| .h
|
| . h-1 .
|
|
|
| . .
|
| .
|
| . .
|
| |________________|<.. .
|
| .
|
| . .
|
|
.
|_________________|<...>|________________|<..
. |________________|<......................................
Un-Balanced
subtree
. ? .
(After Insertion - now needs a
rotation):
. .
__L__._Info_._bf_._R__
|_.__|___A__|_+2_|_._|<...................................
.
.
.
.
.
.
______________________
.
|_.__|___B__|_-1_|_._|
.
.
.
.
__________________<.. .
.
.
| A-R
| . .
__________________<..
______________________
|
| . .
|
B-L |
.
|_.__|___C__|_-1_|_._|
|
| . .
|
|
.
.
.
|
| . .
|
| . __________________<..
..>__________________
|
| .h .
|
| . |
C-L |
. .
| C-R
|
|
| . .
|
| .
|
| . .
|
|
|
| . .
|
| .h
|
| .h-1 h.
|
|
|
| . .
|
| .
|
| . .
|
| |________________|<.. .
|
| .
|
| . .
|
|
.
|_________________|<...>|________________|<..
.
|________________|
h+2.
..>|______N_________| <.....................................
- A is placed to the right of C
- B is placed to the left of C
- That which is to the right of C (C-R) is placed to the left
of A
- That which is to the left of C (C-L) is placed to the right
of B
- That which is to the left of B (B-L) stays to the left of
B
- That which is to the right of A (A-R) stays to the right of
A
- Adjust Root/Father
Re-Balanced
subtree
. ? .
(After Double Rotate-Right(b)
Rotation):
. .
__L__._Info_._bf_._R__
|_.__|___C__|_+0_|_._|<...................................
.
.
.
.
.
.
______________________
______________________ h+1
.
|_.__|___B__|_+1_|_._|
|_.__|___A__|_+0_|_._|
.
.
.
.
.
.
.
.
.
.
.
__________________<..
__________________<..
..>__________________ __________________<..
.
|
B-L | .
| C-L
| . .
| C-R
| |
A-R | . .
|
| .
|
| . .
|
|
|
| . .
|
| .h
|
| .h-1 .
|
|
|
| . .
|
| .
|
| . .
|
|
|
| .h .
|
| .
|
| . .
|
|
|
| . .
|
| .
|
| . .
|
|
|
| . .
|
| .
|
| . .
|
|
|
| . .
|
| . |________________|<.. h.
|________________|
|
| . .
|_________________|<
..>|______N_________| |________________| .
.
AVL DOUBLE ROTATE - RIGHT Rotation (General Form
C)
Balanced
subtree
. ? .
(Prior To Insertion which forces a rotation):
. .
__L__._Info_._bf_._R__
|_.__|___A__|_+1_|_._|<...................................
.
.
.
.
.
.
______________________
.
|_.__|___B__|_+0_|_._|
.
.
.
.
__________________<.. .
.
.
| A-R
| . .
__________________<..
______________________
|
| . .
|
B-L |
.
|_.__|___C__|_+0_|_._|
|
| . .
|
|
.
.
.
|
| . .
|
| . __________________<..
..>__________________
|
| .h .
|
| . |
C-L |
. .
| C-R
|
|
| . .
|
| .
|
| . .
|
|
|
| . .
|
| .h
|
| . h-1 .
|
|
|
| . .
|
| .
|
| . .
|
| |________________|<.. .
|
| .
|
| . .
|
|
h+1.
|_________________|<...>|________________|<..
. |________________|<......................................
Un-Balanced
subtree
. ? .
(After Insertion - now needs a
rotation):
. .
__L__._Info_._bf_._R__
|_.__|___A__|_+2_|_._|<...................................
.
.
.
.
.
h+2.
______________________
.
|_.__|___B__|_-1_|_._|
.
.
.
.
__________________<.. .
.
.
| A-R
| . .
__________________<..
______________________
|
| . .
|
B-L |
.
|_.__|___C__|_+1_|_._|
|
| . .
|
|
.
.
.
|
| . .
|
| . __________________<..
..>__________________
|
| .h .
|
| . |
C-L |
. .
| C-R
|
|
| . .
|
| .
|
| . .
|
|
|
| . .
|
| .h
|
| .h h-1.
|
|
|
| . .
|
| .
|
| . .
|
| |________________|<.. .
|
| .
|
| . .
|
|
.
|_________________|<.
|________________| . .
|________________|
.
..>|______N_________|<...................................................................................
Re-Balanced
subtree
. ? .
(After Double Rotate-Right(c)
Rotation):
. .
__L__._Info_._bf_._R__
|_.__|___C__|_+0_|_._|<...................................
.
.
.
.
.
.
______________________
______________________ h+1
.
|_.__|___B__|_+0_|_._|
|_.__|___A__|_-1_|_._|
.
.
.
.
.
.
.
.
.
.
.
__________________<.
__________________<..
..>__________________ __________________<..
.
|
B-L | .
| C-L
| . .
| C-R
| |
A-R | . .
|
| .
|
| . .
|
|
|
| . .
|
| .h
|
| . h-1.
|
|
|
| . .
|
| .
|
| . .
|
|
|
| .h .
|
| .
|
| .h .
|
|
|
| . .
|
| .
|
| . .
|
|
|
| . .
|
| .
|
| . .
|
|
|
| . .
|
| . |________________| .
. |________________|
|
| . .
|_________________|<.
|______N_________|<..
|________________| . .
In The Space Below, ADD 14, 16, 17, 18, & 19 to the
tree above [practice additional ROTATE - LEFT rotations] Sketch!
Label A, B, and N/C. Write in the balance
factors.