[C++] 4 rotation adjustments for AVL trees

Article directory

• premise
• 1. Structural definition of AVL tree
• 2. Insertion of AVL (Key Points)
• • 1. The inserted node is on the left side of the higher left subtree (right single rotation)
  • 2. The new node is inserted to the right of the higher right subtree (left-handed rotation)
  • 3. The new node is inserted to the left side of the higher right subtree (first right rotation and then left rotation)
  • 4. The new node is inserted to the right of the higher left subtree (first left and then right)
• The overall code inserted

Premise

Although binary search trees can shorten the search efficiency, if the data is ordered or close to ordered, the binary search tree will degenerate into a single tree. Searching for elements is equivalent to searching for elements in a sequence table, which is inefficient.

Therefore, two Russian mathematicians, G.M. Adelson-Velskii and E.M. Landis, invented a method to solve the above problem in 1962:

After inserting a new node into the binary search tree, if it can be ensured that the absolute value of the difference between the heights of the left and right subtrees of each node does not exceed 1 (-1, 0, 1), the height of the tree can be reduced, thus Reduce average search length.
From this, the tree was called the AVL tree, after the first letters of the two scientists’ names.

An AVL tree is either an empty tree or a binary search tree with the following properties:

• Its left and right subtrees are both AVL trees
  
• The absolute value of the height difference between the left and right subtrees (referred to as the balance factor) does not exceed 1
  
  
  If a binary search tree is highly balanced, it is an AVL tree. If it has n nodes, its height can be kept at O(logN), and the search time complexity is O(logN).

Tips: The following is the text of this article, the following cases are for reference

1. Structural definition of AVL tree

Structure creation of tree nodes:

template<class K, class V>
structAVLTreeNode
{<!-- -->
\t
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
 pair<K, V> _kv; //key-value pair to store K AND V
int _bf;//balance factor
//AVL tree does not stipulate that the design balance factor must be selected, it is just an implementation choice to facilitate control.
 
\t//Constructor
AVLTreeNode(const pair<K, V> & amp; kv)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
{<!-- -->}
 
};

Tree frame creation:

template<class K, class V>
classAVLTree
{<!-- -->
typedef AVLTreeNode<K, V> Node; //Node typedef
public:
//......
private:
Node* _root = nullptr;
};

2. Insertion of AVL (Key Points)

The AVL tree introduces a balance factor based on the binary search tree, so the AVL tree can also be regarded as a binary search tree. The insertion process of AVL tree can be divided into two steps:

• Insert new nodes as in a binary search tree
• Adjust the node’s balance factor
  (Find location->Create node->Insert node->Update balance factor->Adjust subtree->Form AVL tree)

1. The inserted node is on the left side of the higher left subtree (right-handed rotation)

This will cause the balance factor of the parent to become -2, and the balance factor of the current node (not the new node) to -1

//Right single rotation
void RotateR(Node* parent)
{<!-- -->
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if(subLR)
{<!-- -->
subLR->_parent = parent;
}
Node* pParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (pParent == nullptr)
{<!-- -->
_root = subL;
_root->_parent = nullptr;
}
else
{<!-- -->
if (pParent->_left == parent)
{<!-- -->
pParent->_left = subL;
}
else pParent->_right = subL;
subL->_parent = pParent;
}
//Update balance factor
parent->_bf = subL->_bf = 0;
}

2. The new node is inserted to the right side of the higher right subtree (left single rotation)

This will cause the balance factor of the parent to become 2, and the balance factor of the current node (not the new node) to be 1

//Left single rotation
void RotateL(Node* parent)
{<!-- -->
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if(subRL)
{<!-- -->
subRL->_parent = parent;
}
Node* pParent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (pParent == nullptr)
{<!-- -->
_root = subR;
_root->_parent = nullptr;
}
else
{<!-- -->
if (pParent->_left == parent)
{<!-- -->
pParent->_left = subR;
}
else pParent->_right = subR;
subR->_parent = pParent;
}
//Update balance factor
subR->_bf = parent->_bf = 0;
}

3. The new node is inserted to the left side of the higher right subtree (first right and then left)

It will cause the balance factor of the parent to become 2, and the balance factor of the current node (not a new node) to become -1

void RotateRL(Node* parent)
{<!-- -->
Node* subR = parent->_right; //Left subtree 60
Node* subRL = subR->_left;//The left subtree of the right subtree 90
int bf = subRL->_bf; // Record SubRLd balance factor

// First perform right single rotation with SubR as the axis
RotateR(parent->_right);
// Then perform left single rotation
RotateL(parent);
if (bf == -1)
{<!-- -->
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
}
else if (bf == 0)
{<!-- -->
parent->_bf = 0;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (bf == 1)
{<!-- -->
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
}
else assert(0);
}


void RotateLR(Node* parent)
{<!-- -->
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
if (bf == 0)
{<!-- -->
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == -1)
{<!-- -->
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)
{<!-- -->
subL->_bf = -1;
parent->_bf = 0;
subLR->_bf = 0;
}
else assert(0);
}

4. Insert the new node to the right of the higher left subtree (first left and then right)

This will cause the parent’s balance factor to become -2, and the current node’s balance factor to become 1

 void RotateLR(Node* parent)
{<!-- -->
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
if (bf == 0)
{<!-- -->
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == -1)
{<!-- -->
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)
{<!-- -->
subL->_bf = -1;
parent->_bf = 0;
subLR->_bf = 0;
}
else assert(0);
}

The overall code inserted

bool Insert(const pair<K, V> & amp; kv)
{<!-- -->
if (_root == nullptr)
{<!-- -->
_root = new Node(kv);
return true;
}
Node* parent = nullptr;//parent is the parent node of cur
Node* cur = _root;//cur goes down
while (cur)
{<!-- -->
if (cur->_kv.first > kv.first)//I am younger than you, look to the left
{<!-- -->
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)//I am older than you, look to the right
{<!-- -->
parent = cur;
cur = cur->_right;
}
else
{<!-- -->
return false;//AVL tree does not allow duplicate values
}
}
//Going here means we have found the correct position where we want to insert the kv value, and we are ready to insert the node...
cur = new Node(kv);
if (parent->_kv.first < kv.first)//If the new node is larger than the parent node, then the right pointer of the parent node points to the new node
{<!-- -->
parent->_right = cur;
cur->_parent = parent;
}
else//If the new node is smaller than the parent node, then the left pointer of the parent node points to the new node
{<!-- -->
parent->_left = cur;
cur->_parent = parent;
}
//Start updating the balance factor
while (parent)//Update to the root node to complete the update of the balance factor
{<!-- -->
//1. If a new node is added to the right subtree, then the _bf of the parent node is increased by one.
//2. If a new node is added to the left subtree, then the _bf of the parent node will be reduced by one.
// + 1 and -1 everyone can decide by themselves, as long as it is right, whatever it is will work!
if (cur == parent->_right)
{<!-- -->
parent->_bf + + ;
}
else
{<!-- -->
parent->_bf--;
}
// Whether to continue updating based on: whether the height of the subtree changes
// 1. parent->_bf == 0 means that the previous parent->_bf was 1 or -1
// Explain that before, one side of the parent was high and the other was low. This time, the short side is inserted and the height of the subtree where the parent is located remains unchanged. There is no need to continue to update upwards.
// 2. parent->_bf == 1 or -1 means that it was parent->_bf == 0 before, and both sides were the same height. Now insert one side and it is higher.
//The height of the subtree where parent is located has changed, continue to update upwards
// 3. parent->_bf == 2 or -2, indicating that parent->_bf == 1 or -1 before, and now the insertion is seriously unbalanced and violates the rules.
// In-place processing--rotation

// Rotation:
// 1. Let the left and right height of this subtree not exceed 1
// 2. Continue to maintain the search tree during the rotation process
// 3. Update and adjust the balance factor of the child node
// 4. Keep the height of this subtree the same as before insertion

//If the new node cur makes the balance factor of the parent node parent become 0, it means that the inserted node has no impact on the balance factor of the entire tree.
//No need to judge upward, you can exit directly
if (parent->_bf == 0)
{<!-- -->
break;
}
//If the new cur makes the balance factor of the parent node parent become 1 or -1, then we have to continue to judge whether the balance factor of the above node is correct.
//Indicates that the previous balance has been broken and the height of the subtree has changed, which may cause problems with the balance factor of the parent node.
else if (parent->_bf == 1 || parent->_bf == -1)
{<!-- -->
cur = parent;
parent = parent->_parent;
}
//When the balance factor appears 2 or -2, the subtree needs to be adjusted
else if (parent->_bf == 2 || parent->_bf == -2)
{<!-- -->
if (parent->_bf == 2 & amp; & amp; cur->_bf == 1)//left rotation
{<!-- -->
RotateL(parent);
}
else if (parent->_bf == -2 & amp; & amp; cur->_bf == -1)//right rotation
{<!-- -->
RotateR(parent);
}
else if (parent->_bf == -2 & amp; & amp; cur->_bf == 1)//left and right rotation
{<!-- -->
RotateLR(parent);
}
else if (parent->_bf == 2 & amp; & amp; cur->_bf == -1)//right-left rotation
{<!-- -->
RotateRL(parent);
}
else
{<!-- -->
assert(false);
}
break;//You can exit after rotating once, because we have already judged upward when rotating. Unless there is a new insertion, the tree will be an avl tree.
}
else
{<!-- -->
assert(false);//An error is reported directly here. When you reach this point, the tree is no longer an AVL tree.
}
}
return true;
}