AVL Tree

AVL Tree
What is AVL Tree | AVL Tree meaning

An AVL is a self-balancing Binary Search Tree (BST) where the difference between
the heights of left and right subtrees of any node cannot be more than one.
Characteristics of AVL Tree:
 It follows the general properties of a Binary Search Tree.

 Each subtree of the tree is balanced, i.e., the difference between the height of
the left and right subtrees is at most 1.
 The tree balances itself when a new node is inserted. Therefore, the insertion
operation is time-consuming
Advantages of AVL Tree:
 AVL trees can self-balance.

 It also provides faster search operations.
 AVL trees also have balancing capabilities with a different type of rotation
 Better searching time complexity than other trees, such as the binary Tree.
 Height must not be greater than log(N), where N is the total number of nodes in
the Tree.
Disadvantages of AVL Tree:
 AVL trees are difficult to implement

 AVL trees have high constant factors for some operations.
Maximum & Minimum number of Nodes

Page 1 of 10
Maximum number of nodes = 2 H+1 – 1
Minimum number of nodes of height H = min no of nodes of height (H-1) + min no of
nodes of height(H-2) + 1
where H(0)=1
H(1)=2
Insertion in an AVL Tree

AVL Tree:
AVL tree is a self-balancing Binary Search Tree (BST) where the difference between
heights of left and right subtrees cannot be more than one for all nodes.
Example of AVL Tree:
The above tree is AVL because the differences between the heights of left and right
subtrees for every node are less than or equal to 1.
Example of a Tree that is NOT an AVL Tree:
The above tree is not AVL because the differences between the heights of the left
and right subtrees for 8 and 12 are greater than 1.
Page 2 of 10
Insertion in AVL Tree:
Insertion in AVL tree is performed in the same way as it is performed in a binary
search tree. The new node is added into AVL tree as the leaf node. However, it
may lead to violation in the AVL tree property and therefore the tree may need
balancing.
The tree can be balanced by applying rotations. Rotation is required only if, the
balance factor of any node is disturbed upon inserting the new node, otherwise
the rotation is not required.
Depending upon the type of insertion, the Rotations are categorized into four
categories.
SN Rotation Description
The new node is inserted to the left sub-tree of left sub-tree of

1 LL Rotation
critical node.
The new node is inserted to the right sub-tree of the right sub-
2 RR Rotation
tree of the critical node.
The new node is inserted to the right sub-tree of the left sub-
3 LR Rotation
The new node is inserted to the left sub-tree of the right sub-
4 RL Rotation
In an AVL tree, the balance factor of a node is the difference in height between its
left and right subtrees. The balance factor is calculated to determine if the tree is
balanced or unbalanced:
 Balance factor = 0: The node is balanced, and the left and right subtrees are
the same height
 Balance factor > 0: The node is right heavy, meaning the left subtree is shorter
than the right subtree
 Balance factor < 0: The node is left heavy, meaning the left subtree is taller
than the right subtree
The balance factor of every node in an AVL tree must be between -1 and 1. If a
node's balance factor is outside of this range, the tree is considered unbalanced
and needs to be rebalanced.
The balance factor is calculated using the formula:

Page 3 of 10
 Balance Factor = height(left subtree) - height(right subtree)
The height of a subtree is the number of edges between the root node and the
leaf node.
Q. Construct an AVL tree by inserting the following elements in the given

order.
63, 9, 19, 27, 18, 108, 99, 81
The process of constructing an AVL tree from the given set of elements is shown
in the following figure.
At each step, we must calculate the balance factor for every node, if it is found to
be more than 2 or less than -2, then we need a rotation to rebalance the tree. The
type of rotation will be estimated by the location of the inserted element with
respect to the critical node.
All the elements are inserted in order to maintain the order of binary search tree.
Page 4 of 10
To delete a node from an AVL tree, you can follow these steps:
1. Remove the node you want to delete.
2. Update the heights of the nodes as you move up the tree from the deleted
node.
3. Check for any nodes that need to be balanced.
4. If you find an imbalance, perform rotations to balance the tree.
Here are some things to consider when deleting nodes from an AVL tree:
5. Deleting a leaf node: This is easy because there are no child nodes to
consider.
6. Deleting a node with one child node: Connect the parent and child nodes.
7. Deleting a node with two child nodes: Replace the node to be deleted with its
in-order successor or predecessor, then delete that node.
8. Action position: This is the parent node from which a node was removed. It
indicates the first node whose height may have been affected by the deletion.
9. Rotation: Rotations are performed when the balance factor is not -1, 0, or 1.
Deletion in AVL Tree

Deleting a node from an AVL tree is similar to that in a binary search tree.
Deletion may disturb the balance factor of an AVL tree and therefore the tree
needs to be rebalanced in order to maintain the AVLness. For this purpose, we
need to perform rotations. The two types of rotations are L rotation and R rotation.
Here, we will discuss R rotations. L rotations are the mirror images of them.
If the node which is to be deleted is present in the left sub-tree of the critical node,
then L rotation needs to be applied else if, the node which is to be deleted is
present in the right sub-tree of the critical node, the R rotation will be applied.
Let us consider that, A is the critical node and B is the root node of its left sub-
tree. If node X, present in the right sub-tree of A, is to be deleted, then there can
be three different situations:
R0 rotation (Node B has balance factor 0 )
If the node B has 0 balance factor, and the balance factor of node A disturbed
upon deleting the node X, then the tree will be rebalanced by rotating tree using
R0 rotation.
The critical node A is moved to its right and the node B becomes the root of the
tree with T1 as its left sub-tree. The sub-trees T2 and T3 becomes the left and
right sub-tree of the node A. the process involved in R0 rotation is shown in the
following image.
Page 5 of 10
Example:
Delete the node 30 from the AVL tree shown in the following image.
Solution
In this case, the node B has balance factor 0, therefore the tree will be rotated by
using R0 rotation as shown in the following image. The node B(10) becomes the
root, while the node A is moved to its right. The right child of node B will now
become the left child of node A.
Page 6 of 10
R1 Rotation (Node B has balance factor 1)
R1 Rotation is to be performed if the balance factor of Node B is 1. In R1 rotation,

the critical node A is moved to its right having sub-trees T2 and T3 as its left and
right child respectively. T1 is to be placed as the left sub-tree of the node B.
The process involved in R1 rotation is shown in the following image.
Example
Delete Node 55 from the AVL tree shown in the following image.
Page 7 of 10
Solution :
Deleting 55 from the AVL Tree disturbs the balance factor of the node 50 i.e. node
A which becomes the critical node. This is the condition of R1 rotation in which,
the node A will be moved to its right (shown in the image below). The right of B is
now become the left of A (i.e. 45).
The process involved in the solution is shown in the following image.
R-1 Rotation (Node B has balance factor -1)
R-1 rotation is to be performed if the node B has balance factor -1. This case is
treated in the same way as LR rotation. In this case, the node C, which is the right
child of node B, becomes the root node of the tree with B and A as its left and
right children respectively.
Page 8 of 10
The sub-trees T1, T2 becomes the left and right sub-trees of B whereas, T3, T4
become the left and right sub-trees of A.
The process involved in R-1 rotation is shown in the following image.
Example
Delete the node 60 from the AVL tree shown in the following image.
Solution:
in this case, node B has balance factor -1. Deleting the node 60, disturbs the
balance factor of the node 50 therefore, it needs to be R-1 rotated. The node C
i.e. 45 becomes the root of the tree with the node B(40) and A(50) as its left and
right child.
Page 9 of 10
Page 10 of 10

AVL Tree

Uploaded by

Copyright:

Available Formats

AVL Tree

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

AVL Tree

Uploaded by

Copyright:

Available Formats

AVL Tree

What is AVL Tree | AVL Tree meaning

Characteristics of AVL Tree:

 It follows the general properties of a Binary Search Tree.

Advantages of AVL Tree:

 AVL trees can self-balance.

Disadvantages of AVL Tree:

 AVL trees are difficult to implement

Maximum & Minimum number of Nodes

Insertion in an AVL Tree

The new node is inserted to the left sub-tree of left sub-tree of

The balance factor is calculated using the formula:

Q. Construct an AVL tree by inserting the following elements in the given

Deletion in AVL Tree

R1 Rotation is to be performed if the balance factor of Node B is 1. In R1 rotation,

The process involved in R1 rotation is shown in the following image.

The process involved in the solution is shown in the following image.

R-1 Rotation (Node B has balance factor -1)

The process involved in R-1 rotation is shown in the following image.

You might also like