avl trees avl trees avl trees avl trees avl trees avl trees avl trees

avl trees

1. Data Structures: A Pseudocode Approach with C, Second Edition 1
Objectives
Upon completion you will be able to:
• Explain the differences between a BST and an AVL tree
• Insert, delete, and process nodes in an AVL tree
• Understand the operation of the AVL tree ADT
AVL Search TreesAVL Search Trees

2. Data Structures: A Pseudocode Approach with C, Second Edition 2
AVL Tree Basic Concepts
• While BST is simple and easy to understand, it has one major
problem which is not balanced.
• In 1968, two Russian mathematicians, G.M. Adelson-Velskii and
E.M. Landis, created the balanced binary tree structure that is
AVL tree.
• An AVL tree is a BST that is guaranteed to always be balanced.
• An AVL tree is a binary tree that either is
1. empty or
2. consists of two AVL subtrees, T
L and T
R , whose heights
differ by no more than 1
| H
L – H
R | ≤ 1

3. Data Structures: A Pseudocode Approach with C, Second Edition 3

4. Data Structures: A Pseudocode Approach with C, Second Edition 4
8-1 AVL Tree Basic Concepts
• AVL Tree Balance Factor
• Balancing Trees

5. Data Structures: A Pseudocode Approach with C, Second Edition 5
AVL Tree Balance Factor
The balance factor = H
L – H
R

The balance factor for any node in AVL tree must be +1, 0, -1

The descriptive identifiers are as follows:

LH for left high (+1) indicates the left subtree is higher than the right
subtree.

EH for even high (0) indicates the subtrees are the same height.

RH for right high (-1) indicates the left subtree is shorter than the right
subtree.

6. Data Structures: A Pseudocode Approach with C, Second Edition 6

7. Data Structures: A Pseudocode Approach with C, Second Edition 7
Balancing Trees
AVL trees are balanced by rotating nodes either to the left or
to the right
Four cases that require rebalancing. All unbalanced trees fall
into one of these four cases:
1. Left of left: A subtree of a tree that is left high has also
become left high.
2. Right of right: A subtree of a tree that is right high has also
become right high.
3. Right of left: A subtree of a tree that is left high become
right high.
4. Left of right: A subtree of a tree that is right high become
left high.

8. Data Structures: A Pseudocode Approach with C, Second Edition 8

9. Data Structures: A Pseudocode Approach with C, Second Edition 9
(continued)

10. Data Structures: A Pseudocode Approach with C, Second Edition 10
Case 1:
Left of Left

11. Data Structures: A Pseudocode Approach with C, Second Edition 11
Case 2:
Right of Right

12. Data Structures: A Pseudocode Approach with C, Second Edition 12
Case 3:
Right of Left

13. Data Structures: A Pseudocode Approach with C, Second Edition 13
Case 4:
Left of Right

14. Data Structures: A Pseudocode Approach with C, Second Edition 14
AVL Tree Implementations
Insertion and deletion in an AVL tree follow the same basic rules Insertion and deletion in an AVL tree follow the same basic rules
for insertion and deletion in a BST. The difference lies in the for insertion and deletion in a BST. The difference lies in the
tree balancing, which occurs as we back out of the tree. In this tree balancing, which occurs as we back out of the tree. In this
section we develop the insertion and deletion algorithms for a section we develop the insertion and deletion algorithms for a
AVL tree, including algorithms to balance the tree.AVL tree, including algorithms to balance the tree.
•Insert into AVL Tree
•AVL Tree Delete Algorithm

15. Data Structures: A Pseudocode Approach with C, Second Edition 15

16. Data Structures: A Pseudocode Approach with C, Second Edition 16

17. Data Structures: A Pseudocode Approach with C, Second Edition 17

18. Data Structures: A Pseudocode Approach with C, Second Edition 18

19. Data Structures: A Pseudocode Approach with C, Second Edition 19

20. Data Structures: A Pseudocode Approach with C, Second Edition 20

21. Data Structures: A Pseudocode Approach with C, Second Edition 21

22. Data Structures: A Pseudocode Approach with C, Second Edition 22

23. Data Structures: A Pseudocode Approach with C, Second Edition 23

24. Data Structures: A Pseudocode Approach with C, Second Edition 24

25. Data Structures: A Pseudocode Approach with C, Second Edition 25