[Data Structure] AVL Tree

AVL tree is a balanced search binary tree, which satisfies the nature of search tree (see article on binary search tree, link : Binary search tree), and meets the balance tree

Nature (left and rightthe height difference of the subtree is not more than 2).

In the binary search tree, we know that to insert an element, we must insert it to the appropriate Position, but in the AVL tree, not only must be inserted into the appropriate position

position, also ensure that the tree is a balanced search binary tree after inserting the element.

On how to adjust a binary tree to a balanced binary tree, there are four kinds of rotation involved:

Single-handed left, single-handed right, double-handed left and right, double-handed right and left.

Illustrations for each rotation are given below:

< p>Left single rotation:

Right single spin: the same as left single spin.

rightLeft double rotation:

leftRight double rotation: The situation is similar to right and left double rotation.

Speaking of balanced trees, how to judge whether a binary tree is a balanced binary tree? ? ?

Idea 1: If we can calculate the height of the left subtree and the height of the right subtree, two The person makes a difference to see if it meets the conditions of the balanced tree. In this way, we will

traverse the tree twice, resulting in lower efficiency.

Idea 2: If we traverse every time, we will bring back the height of the tree, so we will traverse less Once, the time complexity is 0 (N). The complete code is given below

code:

#pragma once# includeusing namespace std;#includetemplatestruct AVLTreeNode{ K _key; V _value; AVLTreeNode* _left; AVLTreeNode* _right; AVLTreeNode< K, V>* _parent; int _bf; AVLTreeNode(const K& key,const V& value = 0) :_key(key) ,_value(value) ,_left(NULL) ,_right(NULL) ,_parent(NULL) ,_bf( 0) {}};templateclass AVLTree{ typedef AVLTreeNode Node;public: AVLTree() :_root(NULL) {} ~AVLTree() {_Destroy(_root);} bool InsertNonR(const K& key) {if (_root == NULL) {_root = new Node(key); _root->_parent = NULL; return true;} Node* cur = _root; Node* parent = _root; while (cur) {//Find the insertion position if (cur->_key _r ight;} else if (cur->_key> key) {parent = cur; cur = cur->_left;} //Cannot insert else return false;} cur = new Node(key); cur->_parent = parent; if (parent->_key _right = cur;} else {parent->_left = cur;} while (parent)//After adjusting to the root node, no further adjustment {//if (parent- >_parent && parent->_parent->_left == parent) if(cur == parent->_left) --parent->_bf; else if (cur == parent->_right) //if (parent->_parent ->_right == parent) ++parent->_bf; if (parent->_bf == 0)//Indicates that the height of parent has not changed, and the adjustment ends at this time return true; else if (parent->_bf == 1 || parent->_bf == -1) {cur = parent; parent = parent->_parent;} else {if (parent->_bf == 2)//The tree is unbalanced and needs to be adjusted {if (cur ->_bf == 1) _RotateL(parent); else //if (cur->_bf == -1) _RotateRL(parent);} // if (parent->_bf == -2) else {if (cur ->_bf == -1) _RotateR(parent); else //if (cur->_bf == 1) _RotateLR(parent) ;}}} return true;} void InOrderNonR() {if (_root == NULL) return; stack s; Node* cur = _root; while (cur || !s.empty()) {while ( cur) {s.push(cur); cur = cur->_left;} Node* top = s.top(); s.pop(); cout << top->_key << ""; cur = top- >_right;} cout << endl;} bool IsBalance() {return _IsBalance(_root);} bool IsBalanceOP() {int height = 0; return _IsBalanceOP(_root,height);} size_t Height() {return _Height(_root );} bool Remove(const K& key) {if (_root == NULL) return false; Node* cur = _root; Node* parent = NULL; Node* del = NULL; while (cur) {if (cur->_key _right;} else if (cur->_key> key) {parent = cur; cur = cur->_left;} else//Find the element to be deleted {if ( cur->_left == NULL && cur->_right == NULL)//Leaf node {if (parent && parent->_left == cur) {parent->_left = NULL; parent->_bf++; del = cur ;} else if (parent && parent->_right == cur) {parent->_right = NULL; parent->_bf--; del = cur;} else {del = _root; _root->_parent = NULL;}} else if (cur->_left == NULL | | cur->_right == NULL) {if (cur->_right != NULL) {if (parent == NULL) {_root = cur->_right; _root->_parent = NULL;} if (parent->_right == cur)//Only right children {parent->_right = cur->_right; parent->_bf--;} else if (parent->_left == cur) {parent->_left = cur->_right; ++parent->_bf;}} else//Only the left child {if (parent == NULL) {_root = cur->_left; _root->_parent = NULL;} else if (parent->_left == cur) {parent->_left = cur->_left; parent->_bf++;} else {parent->_right = cur->_left; parent->_bf--;}} del = cur;} else//There are left and right children { Node* minRight = cur->_right; //Find the leftmost node of the right subtree while (minRight->_le ft) {parent = minRight; minRight = minRight->_left;} cur->_key = minRight->_key; if (parent->_left == minRight) {parent->_left = minRight->_right; parent->_bf++ ;} else if (parent->_right == minRight) {parent->_right = minRight->_right; parent->_bf--;} del = minRight;} while (parent) {cur = del; if (cur = = parent->_left) ++parent->_bf; else if (cur == parent->_right) --parent->_bf; if (parent->_bf == 0) {cur = parent; parent = parent- >_parent;} else if (parent->_bf == 1 || parent->_bf == -1) {//The height does not change, jump out directly break;} else {if (parent->_bf == 2)/ /The tree is unbalanced and needs to be adjusted {if (cur->_bf == 1) _RotateL(parent); else //if (cur->_bf == -1) _RotateRL(parent);} // if (parent- >_bf == -2) else {if (cur->_bf == -1) _RotateR(parent); else //if (cur->_bf == 1) _RotateLR(parent);}}} delete del; del = NULL; return true;}} return false; }protected: //Optimized version bool _IsBalanceOP(Node* root,int& height) { if (root == NULL) {height = 0; return true;} int leftHeight = 0; if (!_IsBalanceOP(root->_left, leftHeight)) return false; int rightHeight = 0; if (!_IsBalanceOP(root-> _right, rightHeight)) return false; height = 1 + rightHeight> leftHeight? rightHeight: leftHeight; return true;} size_t _Height(Node* root) {if (root == NULL) return 0; int leftHeight = _Height(root-> _left); int rightHeight = _Height(root->_right); return leftHeight> rightHeight? leftHeight + 1: rightHeight + 1;} //Most nodes will be calculated twice, time complexity 0(N*N) bool _IsBalance (Node* root) {if (root == NULL) return true; int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); if (rightHeight-leftHeight != root->_bf) {cout << "Balance factor abnormal" << root->_key << "";} return abs(rightHeight-lef tHeight) <2 && _IsBalance(root->_left) && _IsBalance(root->_right);} void _RotateR(Node* parent) {Node* subL = parent->_left; Node* ppNode = parent->_parent;// Remember the parent node of parent Node* subLR = subL->_right; //parent connects to subLR parent->_left = subLR; if (subLR != NULL) subLR->_parent = parent; //parent connects to subL subL- >_right = parent; parent->_parent = subL; //ppNode and subL are connected if (ppNode == NULL) {_root = subL; subL->_parent = NULL;} else {if (ppNode->_left == parent ) ppNode->_left = subL; else ppNode->_right = subL; subL->_parent = ppNode;} subL->_bf = parent->_bf = 0;} void _RotateL(Node* parent) {Node* subR = parent ->_right; Node* ppNode = parent->_parent;//Remember the parent node of parent Node* subRL = subR->_left; //subRL is connected to parent parent->_right = subRL; if (subRL != NULL) subRL->_parent = parent; //subR is connected to parent subR->_left = parent; parent->_parent = subR; //ppNode is connected to subR if (ppNode == NULL) {_root = subR; subR->_parent = NULL;} else {if (ppNode->_left == parent) ppNode->_left = subR; else ppNode->_right = subR; subR->_parent = ppNode;} parent->_bf = subR->_bf = 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) {parent->_bf = 0; subL->_bf = -1; subLR->_bf = 1;} else // bf == -1 {parent->_bf = 1; subL->_bf = 0; subLR->_bf = -1;}} void _RotateRL(Node* parent) {Node* subR = parent ->_right; Node* subRL = subR->_left; int bf = subRL->_bf; _RotateR(parent->_right); _RotateL(parent); if (bf == 0) {parent->_bf = 0; subR ->_bf = 0;} else if (bf == 1) {parent->_bf = -1; subR->_bf = 0; subRL->_bf = 1;} else {parent->_bf = 0; subR- >_bf = 1; subRL->_bf = -1;}} void _Destroy(Node* root) {if (root == NULL) return; _Destroy(root->_left); _Destroy(root->_righ t); delete root; }private: Node* _root;};void TestAVL(){ AVLTree tree1; int array1[] = {16, 3, 7, 11, 9, 26, 18, 14, 15 }; for (int i = 0; i  tree2; for (size_t i = 0;i

About AVL tree, that’s it~