DATA
STRUCTURES
MAHESH GOYANI
MAHATMA GANDHI INSTITUE OF TECHNICAL EDUCATION & RESEARCH CENTER
[email protected]
(C) GOYANI MAHESH 1
AVL TREE
BALANCED
BINARY
TREE
(C) GOYANI MAHESH 2
DEGENERATE BST
BST for 14, 15, 4, 9, 7, 18, 3, 5, 16, 20, 17
14
4 15
3 9 18
7 16 20
5 17
(C) GOYANI MAHESH 3
DEGENERATE BST
BST for 14, 15, 4, 9, 7, 18, 3, 5, 16, 20, 17
3
4
5
7
9
14
15
16
Linked List! 17
18
(C) GOYANI MAHESH
20 4
BALANCED BST
We should keep the tree balanced.
One idea would be to have the left and right subtrees have the same height
14
9 15
7 16
5 17
4 18
3 20
Does not force the tree to be shallow.
(C) GOYANI MAHESH 5
We could insist that every node must have left and right subtrees of same height.
But this requires that the tree be a complete binary tree
To do this, there must have (2d+1 – 1) data items, where d is the depth of the tree.
This is too rigid a condition.
(C) GOYANI MAHESH 6
TERMINOLOGY
A Tree is called Balanced Binary Tree if each node possesses one of the
following property:
A node is called Left heavy if the depth of Left sub tree is one longer
than Right sub tree
A node is called Right heavy if the depth of Right sub tree is one longer
than Light sub tree
A node is called balanced if the depth of both the sub tree is same.
This tree is also known as AVL (Adelson – Velskii and Landis) Tree
An AVL tree is identical to a BST except
height of the left and right subtrees can differ by at most 1.
height of an empty tree is defined to be (–1).
Balanced Binary Tree is classified in to categories :
Height Balanced
Weight Balanced
AVL tree increases the efficiency by reducing the searching time in compare
to binary tree (C) GOYANI MAHESH 7
Graphical Representation
A B
B R C
root
D E L F
G
G H I
Left sub tree Right sub tree
(C) GOYANI MAHESH 8
An AVL Tree level
5 0
2 8 1
1 4 7 2
3 3
(C) GOYANI MAHESH 9
Not an AVL tree level
6 0
1 8 1
1 4 2
3 5 3
(C) GOYANI MAHESH 10
The height of a binary tree is the maximum level of its leaves (also called the depth).
The balance of a node in a binary tree is defined as the height of its left subtree
minus height of its right subtree.
Here, for example, is a balanced tree. Each node has an indicated balance of 1, 0, or
–1.
-1
1 0
0 0 1 -1
0 0 0 0 0 0
0 0 0 0
(C) GOYANI MAHESH 11
HEIGHT BALANCED TREE
If we insert new node in AVL Tree, possible changes in status of tree are as
following :
The node was either left or heavy and has now become balanced
The node was balanced and has now become left or right heavy
The node is heavy and new node is inserted in heavy sub tree, this creates
unbalanced tree, such a node is called critical node
(C) GOYANI MAHESH 12
HEIGHT BALANCED TREE
A Weight balanced tree is a binary tree in which additional weight field is also there.
The node of the weight balanced tree contained four fields :
Data Element
Left Child pointer
Right Child Pointer
A Probability or Weight Field
A node, which is most accessible is given maximum priority and set as a root
(C) GOYANI MAHESH 13
INSERT NODE
1. If this is first node than allocate node, set its field and
return
2. If DATA is already present in tree than discard DATA, else
link new node and return
3. Search unbalanced node
4. Adjust for unbalance factor, if there is no critical node,
return
5. If node is balanced and than becomes heavy or the node
is heavy and now becomes balanced then adjust the balance factor
and return
6. Rebalance the tree and return.
(C) GOYANI MAHESH 14
AVL TREE CREATION
Insert(1)
1
(C) GOYANI MAHESH 15
AVL TREE CREATION
Insert(2)
1
(C) GOYANI MAHESH 16
AVL TREE CREATION
Insert(3) single left rotation
1 -2
(C) GOYANI MAHESH 17
AVL TREE CREATION
Insert(3) single left rotation
1 -2
(C) GOYANI MAHESH 18
AVL TREE CREATION
Insert(3)
2
1 3
(C) GOYANI MAHESH 19
AVL TREE CREATION
1 3
(C) GOYANI MAHESH 20
AVL TREE CREATION
Insert(5)
2
1 3 -2
(C) GOYANI MAHESH 21
AVL TREE CREATION
Insert(5)
2
1 4
3 5
(C) GOYANI MAHESH 22
AVL TREE CREATION
Insert(6)
2 -2
1 4
3 5
(C) GOYANI MAHESH 23
AVL TREE CREATION
Insert(6)
4
2 5
1 3 6
(C) GOYANI MAHESH 24
AVL TREE CREATION
Insert(7)
4
2 5 -2
1 3 6
(C) GOYANI MAHESH 25
AVL TREE CREATION
Insert(7)
4
2 6
1 3 5 7
(C) GOYANI MAHESH 26
