[Data Structure] AVL tree detailed

4. Check whether the AVL tree is balanced

#includeusing namespace std;templatestruct AVLtreeNode //Node structure {typedef AVLtreeNode Node; Node* _left; Node* _right; Node* _parent; K _key; V _value; int _bf; AVLtreeNode(const K& key,const V& value) :_key(key), _value(value), _left(NULL), _right(NULL), _parent(NULL), _bf(0) / /Balance factor {}};templateclass AVLtree{ typedef AVLtreeNode Node;public: AVLtree() :_root(NULL) {} bool Insert(const K& key, const V& value) {if (NULL == _root) {_root = new Node(key, value); return true;} Node* cur = _root; Node* parent = NULL; while (cur) {if (cur->_key _right;} else if (cur->_key>key) {parent = cur; cur = cur->_left;} else {return false;}} if (parent->_key _right = tmp; tmp->_parent = parent; parent->_bf++;} if (parent->_key>key) {Node* tmp = new Node(key, value); parent ->_left = tmp; tmp->_parent = parent; parent->_bf--;} while (parent) {if (parent->_bf == 0) //It turned out to be 1 or -1, then it won’t be inserted afterwards It has an effect on the height of the tree; {return true;} else if (parent->_bf == 1 || parent->_bf == -1) //It turned out to be 0, which has an effect on the height of the tree {Node* pparent = parent->_parent; if (pparent != NULL) {if (pparent->_left == parent)// The height on the left tree increases pparent->_bf--; else // The height on the right tree increases pparent->_bf++; } parent = pparent;} else //The balance factor is 2/-2, which changes from 1 or -1. It does not satisfy the balance tree and needs to be rotated {if (parent->_bf == 2) //The right tree is too high { if (parent->_right->_bf == 1) //Need left-handed structure {_RotateL(parent); return true;} else if (parent->_right->_bf = -1) //Need right-left-handed structure {_RotateRL (parent); return true;}} else //The balance factor is -2 {if (parent->_left->_bf == -1) //The structure that needs right single rotation {_RotateR(parent); return true;} else if (parent->_left->_bf == 1) //Structure that needs left and right rotation {_RotateLR(parent); return true;}}}}} bool IsBalance() {return _IsBalance(_root);} void InOrder() {_InOrder(_root); cout << endl; }protected: bool _IsBalance(Node* root) {if (NULL == root) return true; int bf = _Depth(root->_right)-_Depth(root->_left) ; if (bf == root->_bf) return true; else {cout << root->_key << "Balance factor abnormal" << endl; return false;} return _IsBalance(root->_left); return _IsBalance( root->_right);} int _Depth(Node* root) {if (NULL == root) return 0; int left = _Depth(root->_left)+1; int right = _Depth(root->_right) + 1 ; return left> right? left: right;} void _InOrder(Node* root) {if (NULL == root) return; _InOrder(root->_left); cout << root->_key << ""; _InOrder( root->_right);} void _RotateL(Node* parent) //Left single rotation {Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) subRL ->_parent = parent; Node* pparent = pa rent->_parent; subR->_left = parent; parent->_parent = subR; if (NULL == pparent) {_root = subR; subR->_parent = NULL;} else {if (pparent->_left == parent ) {pparent->_left = subR; subR->_parent = pparent;} else {pparent->_right = subR; subR->_parent = pparent;}} parent->_bf = subR->_bf = 0;} void _RotateR (Node* parent) //Right single rotation {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 == NULL) {_root = subL; subL->_parent = NULL;} else {if (pparent->_left == parent) {pparent->_left = subL; subL->_parent = pparent;} else {pparent->_right = subL; subL->_parent = pparent;}} parent->_bf = subL->_bf = 0;} void _RotateRL(Node* parent) //Right and left double rotation {Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; //It must be recorded and changed after rotation _RotateR(subR); _RotateL(parent); if (bf == 0) //After inserting, the root node of the subtree is 0, and the height is not affected, then the balance factor of the parent node and grandfather node after adjustment is 0 {parent- >_bf = subRL->_bf=subR->_bf = 0;} else if (bf == 1) //After inserting the right tree height, the right tree is given to the left of subR, so the balance factor of subR is 0, and the left tree The height is lower than the right tree, and the parent's right tree is given, so the balance factor of parent is 1 {parent->_bf = -1; subR->_bf = subRL->_bf = 0;} else if (bf == -1) //After insertion, the left tree is high, the right tree is given to the left of subR, so the balance factor of subR is 1, and the height of the left tree is lower than the right tree, and the parent's right tree is given to the parent's right tree, so the balance factor of parent is 0 {parent->_bf = subRL->_bf = 0; subR->_bf = 1;}} void _RotateLR(Node* parent) //Left and right double rotation {Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; _RotateL(subL); _RotateR(parent); if (bf == 0) parent->_bf =subLR->_bf = subL->_bf = 0; else if (bf == 1) {parent ->_bf = subLR->_bf = 0; subL->_bf = -1;} else if (bf == -1) {parent->_bf = 1; subL->_bf = subLR->_bf = 0;} }private: Node* _root;};void TestAVLtree(){ AVLtree tree; int a[] = {16, 3, 7, 11, 9, 26, 18, 14, 15 }; for (size_t i = 0; i  tree1; int a1 [] = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; for (size_t i = 0; i   
  
 

AVL树又称平衡二叉搜索树, It can ensure the relative balance of the binary tree height, reduce the height of the binary tree as much as possible, and improve the search efficiency. In the worst case, a simple binary search tree will have a time complexity of O(N), such as insertion, search, and deletion.

For example:

Therefore, the AVL tree can avoid this situation, making the time complexity of adding, deleting, checking and modifying O(lgN). (ps: lgN here refers to N whose log base is 2.) Then how does the AVL tree do it? Yes, look at its characteristics and you will probably know:

1> The absolute value of the difference between the height of the left subtree and the right subtree does not exceed 1

2.> Each left and right subtree in the tree is an AVL tree

3.>Each node has a balance factor (balance factor--bf), and the balance factor of any node is- 1,0,1. (The balance factor of each node is equal to the height of the right subtree minus the height of the left subtree) .

Think about such a problem, since it is ensured that the difference in the height of the binary tree does not exceed 1, the time complexity can be reduced Isn’t it better to ensure that the height of the left and right subtrees is the same? Of course it won’t work. What if the tree has only two nodes? Therefore, we can only guarantee that the height difference cannot exceed 1.

According to ordinary insertion, if you give an array of: 1,2,3,4,5,6,7, it will definitely lead to the situation shown in the figure above, so we need to adjust it. So under what circumstances need to be adjusted, and how?

The situations that need to be adjusted are roughly divided into the following types:

1>Need to turn right:

Pictures are an intuitive performance , The process looks like this:

First take the right tree of node p (if it exists) as the left tree of g, break the original relationship between p and g, and then let the right of p point to g, Make new connections. Note here that because my AVL tree has a three-pronged chain structure (left, right, parent), the parent node of g needs to be saved before the parent node of g points to p. Because, if the father of g exists, finally let it point to p (as shown above). The rotation is not difficult, but pay attention to the adjustment of the balance factor. Then we must be careful, we must pay attention to the trigeminal chain when changing the pointer to change the point of the father's pointer! The blogger doesn’t know where he took several places at the time and didn’t change the direction of the father node. Although this error is easy to find, it still costs me precious time!

2>Need to turn left:

The right single spin is similar to the left single spin, it is the node I changed the name to make it easier for everyone to understand the code.

3>Need left and right double rotation

You can see that the left and right double rotation is actually the left rotation with p as the axis first Once, turn right again with g as the axis. But in fact, if the left and right spins only call two single spins, there will be problems. Yes, the problem lies in the balance factor. According to the changes in the position of the nodes in the single-spin, we can draw a picture to show the changes in the final node of the right-left single-spin.

4>Need right and left double rotation:

Similar to left and right double rotation, right and left double rotation is also right first After supination, the balance factor is handled very similarly to the left and right double rotation, and the balance factor is determined according to the final position of its node.

1>If the root node is empty, directly insert and assign to the root node

2>Find the inserted position first through the key code, if you find the Given a code with the same key code, the insertion fails (the key structure and key+value structure do not allow duplicate key codes in the tree, which will cause search errors)

3>Insert, insert to the left balance factor Decrease one, insert it to the right and add one

4>Check if it is balanced, and adjust it to balance if unbalanced (there is a comment in the specific code to explain it)

Thought: Recursively calculate every The left and right tree heights of a node are compared with the balance factor of the node with the value of the right tree minus the left tree. If they are equal, the node is balanced, and the judgment is made recursively.

Code implementation of the above problem:

#includeusing namespace std;templatestruct AVLtreeNode //Node structure {typedef AVLtreeNode Node; Node* _left; Node* _right; Node* _parent; K _key; V _value; int _bf; AVLtreeNode(const K& key,const V& value) :_key(key), _value(value), _left(NULL), _right(NULL), _parent(NULL), _bf(0) / /Balance factor {}};templateclass AVLtree{ typedef AVLtreeNode Node;public: AVLtree() :_root(NULL) {} bool Insert(const K& key, const V& value) {if (NULL == _root) {_root = new Node(key, value); return true;} Node* cur = _root; Node* parent = NULL; while (cur) {if (cur->_key _right;} else if (cur->_key>key) {parent = cur; cur = cur->_left;} else {return false;}} if (parent->_key _right = tmp; tmp->_parent = parent; parent->_bf++;} if (parent->_key>key) {Node* tmp = new Node(key, value); parent->_left = tmp; tmp ->_parent = parent; parent->_bf--;} while (parent) {if (parent->_bf == 0) //It turned out to be 1 or -1, then the insertion will not affect the height of the tree; {return true;} else if (parent->_bf == 1 || parent->_bf == -1) //It turned out to be 0, which has an impact on the height of the tree {Node* pparent = parent->_parent; if ( pparent != NULL) {if (pparent->_left == parent)// Increase the height of the left tree pparent->_bf--; else // Increase the height of the right tree pparent->_bf++;} parent = pparent;} else //The balance factor is 2/-2, which is changed from 1 or -1. It does not satisfy the balance tree and needs to be rotated {if (parent->_bf == 2) //The right tree is too high {if (parent->_right- >_bf == 1) //Need left-handed structure {_RotateL(parent); return true;} else if (parent->_right->_bf = -1) //Need right-left-handed structure {_RotateRL(parent); return true; }} else //The balance factor is -2 {if (parent->_left->_bf == -1) //Structure that requires right single rotation {_RotateR(parent); return true;} else if (parent->_left ->_bf == 1) //Structure that needs left and right rotation {_RotateLR(parent); return true;}}}}} bool IsBalance() {return _IsBalance(_root);} void InOrder() {_InOrder(_root); cout << endl; }protected: bool _IsBalance(Node* root) {if (NULL == root) return true; int bf = _Depth(root->_right)-_Depth(root->_left); if (bf == root-> _bf) return true; else {cout << root->_key << "Balance factor abnormal" << endl; return false;} return _IsBalance(root->_left); return _IsBalance(root->_right);} int _Depth (Node* root) {if (NULL == root) return 0; int left = _Depth(root->_left)+1; int right = _Depth(root->_right) + 1; return left> right? Left: right ;} void _InOrder(Node* root) {if (NULL == root) return; _InOrder(root->_left); cout << root->_key << ""; _InOrder(root->_right);} void _RotateL (Node* parent) //Left single rotation {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 (NULL == pparent) {_root = subR; subR->_parent = NULL;} else {if (pparent->_left == parent) {pparent->_left = subR ; subR->_parent = pparent;} else {pparent->_right = subR; subR->_parent = pparent;}} parent->_bf = subR->_bf = 0;} void _RotateR(Node* parent) //right Single spin {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 == NULL) {_root = subL; subL->_parent = NULL;} else {if (pparent->_left == parent) {pparent->_left = subL; subL->_parent = pparent;} else {pparent->_right = subL; subL->_parent = pparent;}} parent->_bf = subL->_bf = 0;} void _RotateRL(Node* parent) // Right and left double rotation {Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; //It must be recorded and changed after rotation _RotateR(subR); _Rota teL(parent); if (bf == 0) //After insertion, the root node of the subtree is 0, and the height is not affected, then the balance factor of the parent node and grandfather node after adjustment is 0 {parent->_bf = subRL- >_bf=subR->_bf = 0;} else if (bf == 1) //After inserting the right tree height, the right tree is given to the left of subR, so the balance factor of subR is 0, and the height of the left tree is lower than the right tree , Gave the parent’s right tree so the parent’s balance factor is 1 {parent->_bf = -1; subR->_bf = subRL->_bf = 0;} else if (bf == -1)//Left after insertion The height of the tree, the right tree is given to the left of subR, so the balance factor of subR is 1, and the height of the left tree is lower than that of the right tree, and the parent's right tree is given so the balance factor of parent is 0 {parent->_bf = subRL->_bf = 0; subR->_bf = 1;}} void _RotateLR(Node* parent) //Left and right double rotation {Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf ; _RotateL(subL); _RotateR(parent); if (bf == 0) parent->_bf =subLR->_bf = subL->_bf = 0; else if (bf == 1) {parent->_bf = subLR ->_bf = 0; subL->_bf = -1;} else if (bf == -1) {parent->_bf = 1; subL->_bf = subLR->_bf = 0;} }private: Node* _root;};void TestAVLtree(){ AVLtree tree; int a[] = {16, 3, 7, 11, 9, 26, 18, 14, 15 }; for (size_t i = 0; i  tree1; int a1[] = {4, 2, 6 , 1, 3, 5, 15, 7, 16, 14 }; for (size_t i = 0; i 

If there is something that is not clearly written or is wrong, please give us more advice