[High-order data structure] AVL tree {Concept and implementation; node definition; insert and adjust balance factors; rotation operations: left single rotation, right single rotation, left and right double rotation, right and left double rotation; verification and performance analysis of AVL tree}

AVL tree

1. The concept of AVL tree

• Although the binary search tree can shorten the search efficiency, if the data is ordered or close to ordered, the binary search tree will degenerate into a single branch 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:

• AVL tree: also known as height-balanced search binary tree. When a new node is inserted 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 (it needs to be By adjusting the nodes), the height of the tree can be reduced, thereby reducing the average search length.

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

1. The absolute value of the difference between the heights of the left and right subtrees (referred to as the balance factor) does not exceed 1 (-1/0/1)
2. Its left and right subtrees are both AVL trees

If a binary search tree is highly balanced, it is an AVL tree. If it has n nodes, its height can be kept at log_2 n, and the search time complexity is O(log_2 n).

2. Core structure of AVL tree

template <class K, class V>
struct AVLTreeNode{<!-- -->
  AVLTreeNode<K,V> *_left; //Pointer to the left node
  AVLTreeNode<K,V> *_right; //Pointer to the right node
  AVLTreeNode<K,V> *_parent; //Pointer to parent node
  pair<K,V> _kv; //Storage element key-value pairs
  int _bf; //balance factor balance factor
        
  AVLTreeNode(const pair<K,V> & amp;kv)
    :_left(nullptr),
    _right(nullptr),
    _parent(nullptr),
    _kv(kv),
    _bf(0)
  {<!-- -->}
};

template <class K, class V>
class AVLTree{<!-- -->
  typedef AVLTreeNode<K,V> Node;
  Node *_root = nullptr;
  
public:
  bool Insert(const pair<K,V> & amp;kv); //Insert and maintain the balance of the AVL tree
  void Inorder(){<!-- --> //Inorder traversal
    _Inorder(_root);
    cout << endl;
  }
  int Height(){<!-- --> //Returns the height of the binary tree
    return _Height(_root);
  }
  bool Isbalance(){<!-- --> //Check whether the binary tree is balanced
    return _Isbalance(_root);
  }
  
private:
  void RotateL(Node *parent); //Left single rotation
  void RotateR(Node *parent); //Right rotation
  void RotateLR(Node *parent); //Double left and right rotation
  void RotateRL(Node *parent); //Double right and left rotation
  void _Inorder(Node *root);
  int _Height(Node *root);
  bool _Isbalance(Node *root);
};

3. Insertion of AVL tree

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. Then the insertion process of AVL tree can be divided into three steps:

1. Insert new nodes as in a binary search tree
2. Adjust the node’s balance factor
3. If the binary tree where a node is located is no longer balanced, balance is restored through rotation.

template <class K, class V>
bool AVLTree<K,V>::Insert(const pair<K,V> & amp;kv)
{<!-- -->
  //1. Insert new nodes according to the binary search tree method
  if(_root == nullptr)
  {<!-- -->
    _root = new Node(kv);
    return true;
  }

  Node *cur = _root;
  Node *parent = nullptr; //cur needs to traverse down to null, so the pointer of the parent node must be recorded
  while(cur != nullptr)
  {<!-- -->
    if(kv.first > cur->_kv.first)
    {<!-- -->
      parent = cur;
      cur = cur->_right;
    }
    else if(kv.first < cur->_kv.first)
    {<!-- -->
      parent = cur;
      cur = cur->_left;
    }
    else{<!-- -->
      return false;
    }
  }
  cur = new Node(kv);
  if(kv.first > parent->_kv.first)
  {<!-- -->
    parent->_right = cur;
  }
  else{<!-- -->
    parent->_left = cur;
  }
  cur->_parent = parent; //Don't forget to modify the parent node pointer
    
  //2.Adjust the balance factor of the node
  while(parent!=nullptr) //Only affects the balance factors of all ancestor nodes of the inserted node, and parent continues to traverse up to the root node
  {<!-- -->
    //Update the balance factor of the parent node
    //Balance factor = height of the right tree - height of the left tree
    if(cur == parent->_right)
    {<!-- -->
       + + parent->_bf; //Insert the right node, bf + +;
    }
    else{<!-- -->
      --parent->_bf; //Insert left node, bf--;
    }
//Detect the balance factor of the parents after updating
    if(parent->_bf == 0)
    {<!-- -->
      //Updated from 1/-1 to 0, indicating that the height of the binary tree with the parent node as the root remains unchanged and there is no need to continue to adjust upward.
      break;
    }
    else if(abs(parent->_bf) == 1)
    {<!-- -->
      //Updated from 0 to 1/-1, it means that the height of the binary tree with the parent node as the root has increased by one level and needs to continue to be adjusted upward.
      parent = parent->_parent;
      cur = cur->_parent;
    }
    else if(abs(parent->_bf) == 2)
    {<!-- -->
      //3. After updating, it is 2/-2, which means that the subtree where the parent is located is already unbalanced and needs to be restored to balance through rotation.
      //......
      //The following content will be explained↓↓↓
    }
    else{<!-- -->
      //Unless the code is wrong, there can be no other situation.
      assert(false);
    }
  }
  return true;
}

4. Rotation of AVL tree

If a new node is inserted into an originally balanced AVL tree, it may cause imbalance. At this time, the structure of the tree must be adjusted to make it balanced. Depending on the insertion position of the node, the rotation of the AVL tree is divided into four types:

4.1 Left-handed rotation

The new node is inserted to the right of the higher right subtree – right-right: left single rotation

explain:

1. In the above figure, before insertion, the AVL tree is balanced. a, b, c are AVL subtrees with height h (h>=0). The new node inserted into the right subtree c of 60 adds one layer to the c-tree, eventually leading to an imbalance in the binary tree rooted at 30.
2. To balance 30, you need to rotate 30 to the left and lift 60 up. Let the left subtree of 30 increase by one level and the right subtree decrease by one level. That is, let 30 be the left subtree of 60.
3. If 60 has a left subtree b, the root of tree b must be greater than 30 and less than 60, which is exactly the right subtree of 30. After the rotation is completed, just update the node’s balance factor.
4. During the rotation process, there are the following situations to consider:
   1. The left subtree b of 60 nodes may exist or be empty.
   2. 30 may be the root node or a subtree
   • If it is the root node, after the rotation is completed, the root node pointer _root needs to be updated.
   • If it is a subtree, it may be the left subtree or the right subtree of a node. The pointer of the parent node to be updated.

template <class K, class V>
void AVLTree<K,V>::RotateL(Node *parent){<!-- --> //parent corresponds to 30
  Node *subR = parent->_right; //subR corresponds to 60
  Node *subRL = subR->_left; //subRL corresponds to the root of the b-tree
  Node *ppNode = parent->_parent; //Record the parent node of 30 to facilitate connection after rotation.
  //30 connects with b-tree
  parent->_right = subRL;
  if(subRL != nullptr) //b tree may be empty
  {<!-- -->
    subRL->_parent = parent;
  }
    
  //30 and 60 reconnect
  subR->_left = parent;
  parent->_parent = subR;
  
  //Connect the parent nodes of 60 and 30
  //If 30 is the root node, update the root node pointer _root to point to 60
  //if(_root == parent)
  if(ppNode == nullptr)
  {<!-- -->
    _root = subR;
  }
  else{<!-- -->
    //To connect the parent nodes of 60 and 30, first determine whether 30 is the left subtree or the right subtree of the parent node.
    if(ppNode->_left == parent)
    {<!-- -->
      ppNode->_left = subR;
    }
    else{<!-- -->
      ppNode->_right = subR;
    }
  }
  subR->_parent = ppNode;
  //Update the balance factor, after rotating 60 and 30, the balance factor becomes 0
  subR->_bf = parent->_bf = 0;
}

The role of rotation: 1. Balance the binary tree 2. Reduce the height of the binary tree (restore to the height h + 2 before insertion)

4.2 Right-handed single rotation

The new node is inserted to the left of the higher left subtree – left-left: right single rotation

For a detailed explanation, refer to left-handed rotation.

template <class K, class V>
void AVLTree<K,V>::RotateR(Node *parent){<!-- -->
  Node *subL = parent->_left;
  Node *subLR = subL->_right;
  Node *ppNode = parent->_parent;

  subL->_right = parent;
  parent->_parent = subL;
                                                                                                        
  parent->_left = subLR;
  if(subLR != nullptr)
  subLR->_parent = parent;

  //if(_root == parent)
  if(ppNode == nullptr)
  {<!-- -->
    _root = subL;
  }
  else{<!-- -->
    if(ppNode->_left == parent)
    {<!-- -->
      ppNode->_left = subL;
    }
    else{<!-- -->
      ppNode->_right = subL;
    }
  }
  subL->_parent = ppNode;
    
  subL->_bf = parent->_bf = 0;
}

The role of rotation: 1. Balance the binary tree 2. Reduce the height of the binary tree (restore to the height h + 2 before insertion)

4.3 Double left and right rotation

The new node is inserted to the right of the higher left subtree – left and right: first left single rotation and then right single rotation

Change the double rotation into a single rotation and then rotate, that is, first perform a left single rotation on 30, and then perform a right single rotation on 90. After the rotation is completed, the update of the balance factor will be considered.

Left and right double rotation can be subdivided into 3 situations:

1. a, b, c, d are empty trees and 60 is new, causing double rotation.
2. Insert a new addition into the b-tree, causing a double rotation.
3. Inserting a new addition into the c-tree causes a double rotation.

The double rotation process in the three cases remains unchanged, but the update of the balance factor needs to be processed separately:

The key to double rotation is to update the balance factor. The balance factors of the three nodes 30, 60, and 90 were incorrectly set to 0 during the two single rotations (because the conditions for single rotation were not met). The balance factors of the three nodes should be readjusted according to the above three different situations. How to distinguish between three different situations? Confirmed based on balance factor of 60 before rotation.

template <class K, class V>
void AVLTree<K,V>::RotateLR(Node *parent){<!-- --> //parent corresponds to 90
  Node *subL = parent->_left; //subL corresponds to 30
  Node *subLR = subL->_right; //subLR corresponds to 60
  int bf = subLR->_bf; //Record the balance factor of 60 before rotation
  RotateL(subL); //30 left single rotation
  RotateR(parent); //90 right single rotation
    
  //Update balance factor
  subLR->_bf = 0; //The balance factor of 60 must be 0
  switch(bf) //Confirm that this is the case based on the balance factor of 60 before rotation
  {<!-- -->
    case 1:
      subL->_bf = -1;
      parent->_bf = 0;
      break;
    case-1:
      subL->_bf = 0;
      parent->_bf = 1;
      break;
    case 0:
      subL->_bf = 0;
      parent->_bf = 0;
      break;
    default:
      //Unless the code is wrong, there can be no other situation.
      assert(false);
      break;
  }
}

The final result of left and right double rotation is:

1. subLR serves as the root of the binary tree, subL serves as the left subtree of subLR, and parent serves as the right subtree of subLR.
2. The left and right subtrees of subLR are made into the right and left subtrees of subL and parent respectively.

4.4 Double right and left rotation

The new node is inserted to the left of the higher right subtree – right-left: first rotate right and then rotate left

For a detailed explanation, refer to left and right double rotation.

template <class K, class V>
void AVLTree<K,V>::RotateRL(Node *parent){<!-- -->
  Node *subR = parent->_right;
  Node *subRL = subR->_left;
  int bf = subRL->_bf;
  RotateR(subR);
  RotateL(parent);
  //Update balance factor
  subRL->_bf = 0;
  switch(bf)
  {<!-- -->
    case 1:
      subR->_bf = 0;
      parent->_bf = -1;
      break;
    case-1:
      subR->_bf = 1;
      parent->_bf = 0;
      break;
    case 0:
      subR->_bf = 0;
      parent->_bf = 0;
      break;
    default:
      //Unless the code is wrong, there can be no other situation.
      assert(false);
      break;
  }
}

The final result of right and left double rotation is:

1. Take subRL as the root of the binary tree, parent as the left subtree of subRL, and subR as the right subtree of subRL.
2. The left and right subtrees of subRL are made into the right and left subtrees of parent and subR respectively.

4.5 minute situational rotation

 else if(abs(parent->_bf) == 2)
    {<!-- -->
//3. After updating, it is 2/-2, which means that the subtree where the parent is located is already unbalanced and needs to be restored to balance through rotation.
      if(parent->_bf == 2 & amp; & amp; cur->_bf == 1) //Right right, left single rotation
      {<!-- -->
        RotateL(parent);
      }
else if(parent->_bf == 2 & amp; & amp; cur->_bf == -1) //right left, right left double rotation
      {<!-- -->
        RotateRL(parent);
      }
      else if(parent->_bf == -2 & amp; & amp; cur->_bf == -1) //Left left, right single rotation
      {<!-- -->
        RotateR(parent);
      }
      else if(parent->_bf == -2 & amp; & amp; cur->_bf == 1) //left and right, left and right double rotation
      {<!-- -->
        RotateLR(parent);
      }
      else
      {<!-- -->
        //Unless the code is wrong, there can be no other situation.
        assert(false);
      }
      break; //Note: After the rotation is completed, the height of the subtree with the original parent as the root is reduced, it is already balanced, and there is no need to update it upwards.
    }

Summarize:
If the subtree rooted with parent is unbalanced, that is, the balance factor of parent is 2 or -2, consider the following situations:

1. The balance factor of parent is 2, which means that the right subtree of parent is high. Let the root of parent’s right subtree be subR.

   • When the balance factor of subR is 1 (right-right), perform left-handed rotation

   • When the balance factor of subR is -1 (right-left), perform a right-left double rotation

2. The balance factor of parent is -2, which means that the left subtree of parent is high. Let the root of parent’s left subtree be subL.

   • When the balance factor of subL is -1 (left-left), perform right single rotation

   • When the balance factor of subL is 1 (left and right), perform left and right double rotation

You can break directly after rotation; because after rotation, the height of the subtree before and after the element is inserted is h + 2 without changing, and there is no need to adjust the balance factor of the upper node. Maximum of one rotation per insertion.

Therefore, the time complexity of inserting elements into the AVL tree is: finding the insertion position O(log_2N) + updating the balance factor O(log_2N) + rotating O(1) = O(log_2N).

5. Verification of AVL tree

The AVL tree adds balance restrictions on the basis of the binary search tree. Therefore, to verify the AVL tree, you can divide it into two steps:

1. Verify that it is a binary search tree
   If an in-order traversal can obtain an ordered sequence, it is a binary search tree.

2. Verify that it is a balanced tree

   • The absolute value of the subtree height difference of each node does not exceed 1
   • Is the node’s balance factor calculated correctly?

   template <class K, class V>
   bool AVLTree<K,V>::_Isbalance(Node *root){<!-- -->
     if(root == nullptr) return true; //Note that an empty tree is also an AVL tree
     int lh = _Height(root->_left); //_Height returns the height of the binary tree
     int rh = _Height(root->_right);
     int diff = rh-lh; //Calculate the balance factor
     if(diff != root->_bf)
     {<!-- -->
       cout << "Key: " << root->_kv.first << "bf: " << root->_bf << " Balance factor abnormality" << endl;
       return false;
     }
     return abs(diff) < 2 & amp; & amp; _Isbalance(root->_left) & amp; & amp; _Isbalance(root->_right);
   }
   

3. test case

   //Insert one or two sets of sequence tests
   void Test1(){<!-- -->
     //int arr[] = {16, 3, 7, 11, 9, 26, 18, 14, 15};
     int arr[] = {<!-- -->1,2,3,4,5,6,7,8,9,10};
     AVLTree<int, int> avl;
     for(auto e : arr)
     {<!-- -->
       avl.Insert(make_pair(e, e));
     }
     avl.Inorder();
     cout << "Isbalance: " << avl.Isbalance() << endl;
   }
   
   //Insert 10,000 random values for testing
   void Test2(){<!-- -->
     srand(time(NULL));
     AVLTree<int, int> avl;
     const int N = 10000;
     for(int i = 0; i<N; + + i)
     {<!-- -->
       int x = rand();
       avl.Insert(make_pair(x, i));
     }
     cout << "Isbalance: " << avl.Isbalance() << endl;
   }
   

6. Deletion of AVL tree (understanding)

The steps to delete AVL tree nodes are as follows:

1. Find the node to delete in the AVL tree.
2. If the node to be deleted is a leaf node, just delete it directly.
3. If the node to be deleted has only one child node, first make the predecessor node point to the child node of the node, and then delete the node.
4. If the node to be deleted has two child nodes, you need to find the replacement node of the node (that is, the smallest node in the right subtree of the node or the largest node in the left subtree), then exchange the values of the replacement node, and finally delete the replacement node .
5. After deleting a node, it is necessary to update the balance factors of all nodes on the path from the node to the root node, and make balance adjustments so that the entire tree meets the properties of the AVL tree again.

The balance adjustment method of deletion operations is similar to the insertion operation of AVL tree, but some details need to be paid attention to when implementing. It should be noted that deletion operations may cause the balance factors of multiple nodes to change, so updates and balance adjustments need to be looped upward all the way to the root node. For specific implementation, you can refer to “Introduction to Algorithms” or “Data Structure – Description Using Object-Oriented Methods and C++” Yin Renkun Edition.

7. Performance of AVL tree

• The AVL tree is an absolutely balanced binary search tree, which requires that the absolute value of the height difference between the left and right subtrees of each node does not exceed 1. This ensures efficient time complexity during query, that is, log_2 (N ).

• However, if you want to make some structural modifications to the AVL tree, the performance is very low. For example: when inserting, you need to maintain its absolute balance, and the number of rotations is relatively high; what is even worse is that when deleting, the rotation may continue to the root. s position.

• Therefore, if you need a data structure with efficient query and ordering, and the number of data is static (that is, it will not change), you can consider the AVL tree. But if a structure is frequently modified, it is not suitable. At this time we need a data structure with better performance-red-black tree.