Scribd
Upload
136 views19 pages

Understanding AVL Trees and Deletion Methods

1. An AVL tree is a self-balancing binary search tree where the height of the two child subtrees of every node differ by at most one. 2. Each node stores an additional "balance factor" field representing the height difference between its left and right subtrees. 3. Rotations are performed during insertions and deletions to rebalance the tree if the balance factor of a node exceeds 1 or -1. 4. Deletions in AVL trees involve checking for balance after removal and performing rotations to restore balance if needed.

Uploaded by

dpkmds
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPSX, PDF, TXT or read online on Scribd
136 views19 pages

Understanding AVL Trees and Deletion Methods

1. An AVL tree is a self-balancing binary search tree where the height of the two child subtrees of every node differ by at most one. 2. Each node stores an additional "balance factor" field representing the height difference between its left and right subtrees. 3. Rotations are performed during insertions and deletions to rebalance the tree if the balance factor of a node exceeds 1 or -1. 4. Deletions in AVL trees involve checking for balance after removal and performing rotations to restore balance if needed.

Uploaded by

dpkmds
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPSX, PDF, TXT or read online on Scribd
You are on page 1/ 19

AVL Tree

BY
RAJANIKANTH B
Introduction
AVL Tree is also a Binary Search Tree but it is balanced tree.
Here balanced means the difference between height of right
subtree and left subtree must be -1 OR 0 OR +1.

In AVL Tree every node will have one extra information


known as BALANCE FACTOR.

BalanceFactor = HeightOfRightSubtree – HeightOfLeftSubtree


The AVL tree is named after its two inventors, G.M.
Adelson-Velsky and E.M. Landis, who published it in
their 1962.

Example
After every insertion / deletion we need to check the BALANCE FACTOR
If it is other than -1 or 0 or +1 then we perform ROTATION to make the
Tree Balance.

Note

All AVL Trees are Binary Search Trees but All Binary
Search Trees need not be AVL Tree

All Binary Search Trees are Binary Trees but All


Binary Trees need not be Binary Search Tree
Rotations
Left Rotation (LL)
Single
Rotation
Right Rotation (RR)

Left Right Rotation (LR)


Double
Rotation
Right Left Rotation (RL)
LL Rotation Insert: A , B , C

0
1
2
A
0 0
1
B
0
C
RR Rotation Insert: C , B , A

0
1
2
C

0 B
1 0

0
A
LR Rotation Insert: C , A , B

0
1
2
C
0
1 0
A
0
B
RL Rotation Insert: A , C , B

0
1
2
A
0 0
1
C
0
B
Example
Construct AVL Tree by inserting 1 to 10
1

3
Deletion
Deletion in AVL Tree have 3 cases
1. Deleting node without any child
2. Deleting node with one child
3. Deleting node with two children
1. Deleting node without any child
Step – 1:
Find given node in AVL Tree by performing search operation

Step – 2:
Remove given node in AVL Tree by using ‘delete’ operator

Step – 3:
Check balance factor of each node in AVL tree

Step – 4:
If tree is not balanced perform suitable Rotation operation to
make tree balanced
Deletion Delete: 5

2 8

1 3 6 9

5 7 10
2. Deleting node with one child
Step – 1:
Find given node in AVL Tree by performing search operation

Step – 2:
Make a link between its Parent and its Child

Step – 3:
Remove given node in AVL Tree by using ‘delete’ operator

Step – 4:
Check balance factor of each node in AVL tree

Step – 5:
If tree is not balanced perform suitable Rotation operation to
make tree balanced
Deletion Delete: 6

2 8

1 3 6 9

7 10
Deletion Delete: 7

2 8

1 3 7 9

10
3. Deleting node with two children
Step – 1:
Find given node in AVL Tree by performing search operation
Step – 2:
Find the Smallest node in its Right Subtree
Step – 3:
Swap both given node and the Smallest node in its right subtree

Step – 4:
Remove given node in AVL Tree by using ‘delete’ operator
Step – 5:
Check balance factor of each node in AVL tree
Step – 6:
If tree is not balanced perform suitable Rotation operation to
make tree balanced
Deletion Delete: 4

2 9

1 3 8 10
Assignment
Construct AVL Tree by inserting 10 to 1

Write applications of AVL Trees


Explain Deletion in AVL Tree in detail

You might also like