# catalog:

## I Concept & principle

Previously, we understood the binary search tree, but we found that if the data is orderly or close to orderly, the binary search tree will degenerate into a single tree

AVL tree is a balanced binary tree. It just adds a balance factor to the binary search tree to form the current balanced binary tree Binary search tree link

^

Here we focus on understanding the balance factor

## II Balance factor

Balance factor: the balance factor is an integer value to judge whether the corresponding binary tree is balanced, so as to stabilize the binary tree and prevent the binary tree from degenerating into the above single branch tree

Rules:

1. There is a balance factor on each corresponding node to indicate whether the binary tree is balanced

~

2. Balance factor of each node = layers of right subtree - layers of left subtree

~

3. When the corresponding balance factor is (- 1 ~ 1), it is a balanced binary tree, otherwise it needs to be adjusted

## III definition

There is a left child node inside the AVL tree Right child node Parent node Corresponding stored data There is also the balance factor. We create a structure and encapsulate it as something that should be stored inside a node

template<class T> //Generic declaration struct AVLNode{ //Created structure AVLNode<T>* _parent; //Create corresponding parent node AVLNode<T>* _left; //Left child AVLNode<T>* _right; //Right child T _val; //Internal corresponding value //Balance factor int _bf; AVLNode(const T& val = T()) //Initialize a corresponding node :_parent(nullptr) , _left(nullptr) , _right(nullptr) //Node assigned nullptr , _val(val) //Direct data transfer , _bf(0) //The equilibrium factor is directly reduced to 0 {} };

In this way, all the things needed to create a corresponding node are passed in, When using this structure later, we only need to give it an alias, and then create it in the way of new

## IV Rotation of AVL tree

### 1. Left hand interface understanding

Understanding of the left rotation interface: because the balance factor of the node will change after the AVL tree is inserted, for this reason, we need to operate the left rotation of the binary tree inserting a new node, so as to restore the binary tree to the balanced binary tree

void RotateL(Node* parent){ Node* subR = parent->_right; //What is defined here is the right subtree corresponding to the parent node, that is, B Node* subRL = subR->_left; //Here we get the left subtree of node B, that is, the node to be converted by left rotation subR->_left = parent; //Connect B to the corresponding parent node parent->_right = subRL; //Connect the right subtree of the parent node with B if (subRL) //When the node in this intermediate state exists subRL->_parent = parent; //Then let the parent node of its child node point to the real parent node if (parent == _root){ //When the parent node is the root node _root = subR; //Point to parent node subR->_parent = nullptr; //Its internal pointer is converted to null } else{ //If both exist Node* pparent = parent->_parent; //Defines the parent node of the parent if (pparent->_left == parent) //If the parent node is to the left of the grandfather node, point it to pparent->_left = subR; else pparent->_right = subR; //Otherwise, it is the right direction subR->_parent = pparent; //Finally, let the parent node generated by its left rotation point to the grandfather's node } parent->_parent = subR; //Point the parent node of the parent to the child node of the rotation parent->_bf = subR->_bf = 0; //Because after left rotation, the internal balance factor becomes 0 }

The explanation of sinistral rotation has been relatively clear. The main thing is to draw pictures to understand the process step by step

### 2. Right hand interface understanding

The right-handed operation is similar to the left-handed operation. We can understand it by analogy. I won't comment more

void RotateR(Node* parent){ Node* subL = parent->_left; //Similarly, create its corresponding node point Node* subLR = subL->_right; //Its internal nodes point to subL->_right = parent; parent->_left = subLR; if (subLR) subLR->_parent = parent; //Determine whether the parent is the root node if (parent == _root){ //Root node _root = subL; subL->_parent = nullptr; } else{ Node* pparent = parent->_parent; if (pparent->_left == parent) pparent->_left = subL; else pparent->_right = subL; subL->_parent = pparent; } parent->_parent = subL; subL->_bf = parent->_bf = 0; }

### 3. Understanding of insert interface

The code about Insert here is connected. I just split it for easier understanding

For the implementation of inserting an element, we also first traverse the binary tree, find the corresponding addition position, and insert the corresponding data. We also need to use left-hand and right-hand operations to realize the balanced binary tree according to the insertion position

bool insert(const T& val){ //Insert function //Binary search tree if (_root == nullptr){ _root = new Node(val); //If the root node is empty, it is directly created as the root node return true; } Node* cur = _root; //Otherwise, the corresponding root node is created Node* parent = nullptr; //Parent node is null while (cur){ //There is a corresponding insertion position parent = cur; //Insert data if (cur->_val == val) return false; else if (cur->_val > val) cur = cur->_left; else cur = cur->_right; } cur = new Node(val); //Create a new Node with Node if (parent->_val > val) parent->_left = cur; else parent->_right = cur; cur->_parent = parent; //Adjustment, starting from parent while (parent){ //Update the balance factor of the parent if (parent->_left == cur) --parent->_bf; else ++parent->_bf; if (parent->_bf == 0) //parent short subtree height + 1 break; else if (parent->_bf == 1 || parent->_bf == -1){ //Continue to update upward cur = parent; parent = parent->_parent; } else if (abs(parent->_bf) == 2){

The above is the understanding of inserting nodes, and the following is the adjustment of the binary tree after inserting elements

#### (1) The new node is inserted to the left of the higher left subtree - left left: right single rotation

The distinction here is achieved by the size of the balance factor between the parent node and its corresponding child node!!!

if (parent->_bf == -2 && cur->_bf == -1){ //If the left is high, it rotates right RotateR(parent); }

#### (2) The new node is inserted to the right of the higher right subtree - right right right: left single rotation

else if (parent->_bf == 2 && cur->_bf == 1){ RotateL(parent); //Parent node left rotation }

#### (3) 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

else if (parent->_bf == -2 && cur->_bf == 1){ Node* subLR = cur->_right; int bf = subLR->_bf; RotateL(cur); //First child node left rotation RotateR(parent); //Rotate the parent node to the right if (bf == 1){ Because when an update occurs,There will be a node update error,So update manually parent->_bf = 0; cur->_bf = -1; } else if (bf == -1){ parent->_bf = 1; cur->_bf = 0; } }

#### (4) The new node is inserted to the left of the higher right subtree - right left: right single rotation first and then left single rotation

else if (parent->_bf == 2 && cur->_bf == -1){ //First obtain the bf corresponding to the subRL Node* subRL = cur->_left; int bf = subRL->_bf; RotateR(cur); RotateL(parent); //After the occurrence of right left double rotation, the bf value of the corresponding child nodes may be different and need to be updated //Here, the judgment method is used to distinguish the location of the linked node, and then update the corresponding bf if (bf == 1){ cur->_bf = 0; Because when an update occurs,There will be a node update error,So update manually parent->_bf = -1; } else if (bf == -1){ cur->_bf = 1; parent->_bf = 0; } } break; } } return true; }

## V Print interface

The printing interface here is relatively simple. It mainly uses recursive method to cycle to the internal val

void inorder(){ _inorder(_root); //Call the following function cout << endl; } void _inorder(Node* root){ if (root){ _inorder(root->_left); //First traverse the left node cout << root->_val << " "; _inorder(root->_right); //Traversing the corresponding right node } }

## Vi Verify AVL tree interface

The verification of AVL tree is to judge whether it is a balanced binary tree by the balance factor and the height difference between the left and right subtrees

int Height(Node* root){ //Encapsulate the function to realize the height judgment of the corresponding child node if (root == nullptr) return 0; int left = Height(root->_left); int right = Height(root->_right); return left > right ? left + 1 : right + 1; } bool _isBalance(Node* root){ //Function to judge whether it is balanced if (root == nullptr) return true; //Check whether the balance factor is consistent with the height difference between the left and right subtrees //Call the function to view the height of the corresponding subtree int left = Height(root->_left); int right = Height(root->_right); if (right - left != root->_bf){ cout << " Node: " << root->_val << " bf:" << root->_bf << " height gap: " << right - 1; //output return false; } return abs(root->_bf) < 2 && _isBalance(root->_left) //Circular judgment && _isBalance(root->_right); //Balanced output 1 } bool isBalance(){ //The final encapsulated interface return _isBalance(_root); }

In general, we still understand the implementation of balanced binary tree insertion, because traversal and left-handed and right-handed operations will be involved during insertion, which is difficult to understand. We pay attention to the understanding of left-handed and right-handed, as well as left-handed and right-handed