by An AVL (Adelson-Velskii and Landis) Tree is a self balancing Binary Search Tree which has the following properties.
For any node “A”, the height of the left subtree of “A” and height of the right subtree of “A” differ by 1 at max.
For every node in an AVL Tree, the difference between the height of its left subtree and right subtree should not be more than 1. Whenever insertion makes a node unbalanced, AVL rotations are used to balance the tree again.
In this article, let’s look into the Left-Right Rotation, also called LR Rotation.
In case of Binary search Trees worst case search complexity is O(n) in cases when the Binary Search Tree is skewed. In AVL tree, since heights of left and right subtree are balanced, hence search complexity improves to O(log n). Before going ahead have a look into AVL Tree Basics.
AVL Tree Rotations
Whenever a new element is inserted into an AVL Tree, there is a chance of AVL tree becoming unbalanced. In order to rebalance AVL tree again to satisfy the height criteria, AVL tree rotations are performed.
In order to rebalance the tree, we start at the node inserted and travel up the tree, balancing each and every node of the tree if needed.
What is Left-Right Rotation in AVL Tree?
Left-Right rotation is required when:
- a node becomes left-heavy;
- the newly inserted node lies in the right subtree of its left child.
In this case, single rotation operations are unable to rebalance the AVL Tree and hence double rotation is performed to rebalance the tree.
To do so
- First a Left rotate operation is done on the left child of the unbalanced node and then
- Right Rotate operation is performed on the unbalanced node.
Let’s take an example to understand it better.
- As you can see in the above example node “34” becomes unbalanced after insertion of new node “32”. In order to balance node “34”
- Left rotate operation is performed on left child “23” of the unbalance node “34”.
- After that Right rotate operation is performed on the unbalanced node “34”.
- Now the tree becomes balanced again.
Condition for Left Right Rotations
Left Right rotation operation is being applied only when following condition is met.
- After insertion of new node,
- if the parent node of the new node has higher left subtree than right subtree by >= 2
- new node is added as the right child of the parent’s left child
This is called an LR imbalance. To summarize it means
Unbalanced node -> Left Heavy
Left child -> Right Heavy
Algorithm
- Insert the new node at it’s location using Binary Search Tree insertion algorithm
- Check the height_balance of the parent node.
- if the parent node of the new node has higher left subtree than right subtree by >= 2
- new node is added as the right child of the parent’s left child.
- if above condition holds good then
- perform left rotate operation on node’s left child.
- Perform right rotate operation on node.
- return the new parent node.
Before going ahead have a look into Left Rotate Operations and Right Rotate Operations.
AVL Tree Class definition
Since AVL Tree is a Binary Search Tree also, hence in all code below we have used the same property to show how to use inheritance effectively.
In below code, we have define AVL class as a derived class of Binary Search Tree Base class. Please check here for more information related to Binary Search Tree implementations before going ahead.
Let’s have a look into basic C++ class definition for AVL Tree.
template <typename T>
class BinarySearchTree
{
public:
T m_data;
BinarySearchTree* m_left;
BinarySearchTree* m_right;
BinarySearchTree (T data);
virtual ~BinarySearchTree ();
};
template <typename T>
class AVL: public BinarySearchTree<T>
{
public:
int m_height;
AVL (T data);
~AVL ();
};
template <typename T>
AVL<T>::AVL (T data):BinarySearchTree<T> (data), m_height (0)
{}
template <typename T>
AVL<T>::~AVL ()
{}
C++ Code for Left-Right Rotation
Let’s look into the sample code for this.
/* Left Right Rotate
* x x z
* / \ / \ / \
* y a z a y x
* / \ -----> / \ -----> / / \
* b z y c b c a
* \ /
*new entry --> c b
*
*/
template <typename T>
AVL<T>* left_right_rotate (AVL<T>* node_to_be_balanced)
{
node_to_be_balanced -> m_left = left_rotate (dynamic_cast<AVL<T>*> (node_to_be_balanced -> m_left));
return right_rotate (node_to_be_balanced);
}
/* Left Rotate
* x z
* / \ / \
* y z x b
* / \ ----> / \ \
* a b y a c
* \
* c
*/
template <typename T>
AVL<T>* left_rotate (AVL<T>* node_to_be_balanced)
{
AVL<T>* temp = dynamic_cast<AVL<T>*> (node_to_be_balanced -> m_right);
AVL<T>* left_child = dynamic_cast<AVL<T>*> (node_to_be_balanced -> m_right -> m_left);
temp -> m_left = node_to_be_balanced;
node_to_be_balanced -> m_right = left_child;
node_to_be_balanced -> m_height = height_of_node (node_to_be_balanced);
temp -> m_height = height_of_node (temp);
return temp;
}
/* Right Rotate
* x y
* / \ / \
* y z b x
* / \ ----> / / \
* b a c a z
* /
* c
*/
template <typename T>
AVL<T>* right_rotate (AVL<T>* node_to_be_balanced)
{
AVL<T>* temp = dynamic_cast<AVL<T>*> (node_to_be_balanced -> m_left);
AVL<T>* right_child = dynamic_cast<AVL<T>*> (temp -> m_right);
temp -> m_right = node_to_be_balanced;
node_to_be_balanced -> m_left = right_child;
node_to_be_balanced -> m_height = height_of_node (node_to_be_balanced);
temp -> m_height = height_of_node (temp);
return temp;
}
Height of the node function definition
template <typename T>
int height_of_node (BinarySearchTree<T>* root)
{
if (!root)
return 0;
int left = height_of_node (root -> m_left);
int right = height_of_node (root -> m_right);
if (left > right)
return 1 + left;
else
return 1 + right;
}
Time Complexity
The actual LR rotation takes constant time: O(1), because only a fixed number of pointer updates are required.
If we include insertion and finding the unbalanced node, AVL insertion remains: O(log n) because the height of an AVL Tree is O(log n).
Other AVL Tree Rotations
AVL Trees can become unbalanced in four different ways.
You can also check the other rotation cases:
- AVL Tree Right Rotation (LL Rotation)
- AVL Tree Left Rotation (RR Rotation)
- AVL Tree Left-Right (LR) Rotation
For the complete balancing flow, you can also refer to your AVL Tree Basics, AVL Tree Insertion and AVL Tree Deletion articles.
Summary
Left-Right Rotation is used when:
Node -> Left Heavy
Left Child -> Right Heavy
The balancing sequence is:
Left Rotation on Left Child
+
Right Rotation on Unbalanced Node
So the Left-Right case can be remembered as:
LR = Left Rotate + Right Rotate
