[go: up one dir, main page]
Scribd
Upload
13 views4 pages

AVLtree

An AVL tree is a balanced binary search tree where the balance factor of each node is -1, 0, or +1. To maintain balance after insertions or deletions, rotations (LL, RR, LR, RL) are performed to adjust the positions of nodes. Every AVL tree is a binary search tree, but not all binary search trees are AVL trees.

Uploaded by

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

AVLtree

An AVL tree is a balanced binary search tree where the balance factor of each node is -1, 0, or +1. To maintain balance after insertions or deletions, rotations (LL, RR, LR, RL) are performed to adjust the positions of nodes. Every AVL tree is a binary search tree, but not all binary search trees are AVL trees.

Uploaded by

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

AVL Tree Data Structure

An AVL tree is a balanced binary search tree. In an AVL tree, balance factor of
every node is either -1, 0 or +1.
The balance factor of a node is calculated either height of left subtree - height of
right subtree (OR) height of right subtree - height of left subtree.

Example of AVL Tree

The above tree is a binary search tree and every node is satisfying balance factor
condition. So this tree is said to be an AVL tree.

Every AVL Tree is a binary search tree but every Binary Search Tree need not be
AVL tree.

AVL Tree Rotations


In AVL tree, after performing operations like insertion and deletion we need to check the
balance factor of every node in the tree. If every node satisfies the balance factor
condition then we conclude the operation otherwise we must make it balanced. Whenever
the tree becomes imbalanced due to any operation we use rotation operations to make
the tree balanced.

Rotation is the process of moving nodes either to left or to right to make the tree balanced.

There are four rotations and they are classified into two types.
Single Left Rotation (LL Rotation)
In LL Rotation, every node moves one position to left from the current position. To
understand LL Rotation, let us consider the following insertion operation in AVL Tree...
Single Right Rotation (RR Rotation)
In RR Rotation, every node moves one position to right from the current position. To
understand RR Rotation, let us consider the following insertion operation in AVL Tree...

Left Right Rotation (LR Rotation)


The LR Rotation is a sequence of single left rotation followed by a single right rotation. In
LR Rotation, at first, every node moves one position to the left and one position to right
from the current position. To understand LR Rotation, let us consider the following insertion
operation in AVL Tree...
Right Left Rotation (RL Rotation)
The RL Rotation is sequence of single right rotation followed by single left rotation. In RL
Rotation, at first every node moves one position to right and one position to left from the
current position. To understand RL Rotation, let us consider the following insertion
operation in AVL Tree...

You might also like