PowerPoint Presentation
Data Structures: A Pseudocode Approach with C, Second Edition
1
AVL Tree Basic Concepts
An AVL tree is a BST that is guaranteed to always be balanced. We begin with a discussion of its basic structural differences and then discuss the four different balancing situations that can occur when data are inserted or deleted.
AVL Tree Balance Factor
Balancing Trees
Data Structures: A Pseudocode Approach with C, Second Edition
2
Data Structures: A Pseudocode Approach with C, Second Edition
3
Data Structures: A Pseudocode Approach with C, Second Edition
4
Two Binary Search Trees
Data Structures: A Pseudocode Approach with C, Second Edition
5
In 1962, two Russian mathematicians,
G.M. Andel’son-Velskii and E.M. Landis,
created the balanced binary tree structure that is named after them – the AVL tree.
An AVL tree is a search tree in which the heights of the subtrees differ by no more than one.
Evgenii Mikhailovich Landis:
Data Structures: A Pseudocode Approach with C, Second Edition
6
Data Structures: A Pseudocode Approach with C, Second Edition
7
An AVL tree is a BST with the following properties:
It is balanced.
Each subtree is itself an AVL tree.
Data Structures: A Pseudocode Approach with C, Second Edition
8
An AVL tree is a BST with the following properties:
It is balanced.
Each subtree is itself an AVL tree.
9
12
5
2
20
25
29
Balance Factor is 0!
Data Structures: A Pseudocode Approach with C, Second Edition
9
An AVL tree is a BST with the following properties:
It is balanced.
Each subtree is itself an AVL tree.
9
12
5
2
20
25
29
out of balance
Data Structures: A Pseudocode Approach with C, Second Edition
10
9
12
5
Balance Factor = 0
Equal Heavy EH
Data Structures: A Pseudocode Approach with C, Second Edition
11
Balance Factor = 0
Equal Heavy EH
9
12
5
EH
EH
EH
9
5
EH
LH
Balance Factor = 1
Left Heavy LH
Data Structures: A Pseudocode Approach with C, Second Edition
12
Balance Factor = 0
Equal Heavy EH
9
5
EH
LH
Balance Factor = 1
Left Heavy LH
9
12
5
EH
EH
EH
9
12
RH
EH
Balance Factor = -1
Right Heavy RH
Data Structures: A Pseudocode Approach with C, Second Edition
13
AVL Tree Operations
1. Traverse BT Traversals
2. Search BST Search
3. Insert BST Insert + Rotations
4. Delete BST Delete + Rotations
Data Structures: A Pseudocode Approach with C, Second Edition
14
Data Structures: A Pseudocode Approach with C, Second Edition
15
(continued)
Data Structures: A Pseudocode Approach with C, Second Edition
16
Left of Left
Data Structures: A Pseudocode Approach with C, Second Edition
17
Left of Left
Right of Right
Data Structures: A Pseudocode Approach with C, Second Edition
18
Left of Left
Right of Right
Right of Left
Data Structures: A Pseudocode Approach with C, Second Edition
19
Left of Left
Right of Right
Right of Left
Left of Right
Data Structures: A Pseudocode Approach with C, Second Edition
20
Left of Left
Right rotation
Data Structures: A Pseudocode Approach with C, Second Edition
21
Data Structures: A Pseudocode Approach with C, Second Edition
22
Right of Right
Left rotation
Data Structures: A Pseudocode Approach with C, Second Edition
23
Data Structures: A Pseudocode Approach with C, Second Edition
24
Right of Left
Double rotation right:
– left rotation
– right rotation
Data Structures: A Pseudocode Approach with C, Second Edition
25
Data Structures: A Pseudocode Approach with C, Second Edition
26
Left of Right
Double rotation left:
– right rotation
– left rotation
Data Structures: A Pseudocode Approach with C, Second Edition
27
Data Structures: A Pseudocode Approach with C, Second Edition
28
Data Structures: A Pseudocode Approach with C, Second Edition
29
An AVL tree is a search tree in which the heights of the subtrees differ by no more than one.
Data Structures: A Pseudocode Approach with C, Second Edition
30
AVL Tree Implementations
Insertion and deletion in an AVL tree follow the same basic rules 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 section we develop the insertion and deletion algorithms for a AVL tree, including algorithms to balance the tree.
Insert into AVL Tree
AVL Tree Delete Algorithm
Data Structures: A Pseudocode Approach with C, Second Edition
31
Data Structures: A Pseudocode Approach with C, Second Edition
32
Data Structures: A Pseudocode Approach with C, Second Edition
33
Data Structures: A Pseudocode Approach with C, Second Edition
34
Data Structures: A Pseudocode Approach with C, Second Edition
35
Data Structures: A Pseudocode Approach with C, Second Edition
36
Data Structures: A Pseudocode Approach with C, Second Edition
37
Data Structures: A Pseudocode Approach with C, Second Edition
38
Data Structures: A Pseudocode Approach with C, Second Edition
39
Data Structures: A Pseudocode Approach with C, Second Edition
40
/docProps/thumbnail.jpeg