Preface
AVL tree: It is the earliest self-balancing binary search tree invented. In the AVL tree,The maximum height difference between two subtrees corresponding to any node is 1, so it is also calledheight balanced tree. The average and worst-case time complexities of search, insertion, and deletion are
. Adding and removing elements may require one or more tree rotations to rebalance the tree.
Tree node class, balanced binary tree class
template <typename KeyType>
class AVLNode{ public: KeyType key; AVLNode *left; AVLNode *right; AVLNode(KeyType k):key(k),left(nullptr),right(nullptr){}
}; template <typename KeyType>
class AVLTree{ typedef AVLNode<KeyType> Node; private: Node *avlroot; int __getheight(const Node *root);//Find the height of the tree int __diff(const Node *root);//Find the balance factor Node *__insert(Node *&root,const KeyType key);//Insert internal implementation Node *__delnode(Node *root,const KeyType key);//Delete internal implementation Node *__balance(Node *root);//balance operation //Four kinds of rotation operations Node *__rotation_ll(Node *root); Node *__rotation_rr(Node *root); Node *__rotation_lr(Node *root); Node *__rotation_rl(Node *root); Node *__search(Node *root,const KeyType key);//Find internal implementation void __traversal(Node *root);//Traversal (in-order) internal implementation void __deleteTree(Node *root);//delete tree Node *__treeMax(Node *root);//The previous root node is the largest Node *__treeMin(Node *root);//The front root node is the smallest public: AVLTree(){avlroot = nullptr;} //Default constructor ~AVLTree(); AVLTree(const KeyType *arr,int len); //Constructor, array construction bool insert(const KeyType key);//Insert external interface bool search(const KeyType key);//Find external interface void traversal();//Traverse (in-order) external interface bool delnode(const KeyType key);//Delete external interface
};
insert operation
The idea is very simple, if the value of the current node is less than the value of the current node, go left; if the value of the current node is greater than the value of the current node, go right. A balancing operation needs to be performed after each insertion to ensure the balance of the tree.
//Insert internal implementation
template <typename KeyType>
AVLNode<KeyType> *AVLTree<KeyType>::__insert(Node *&root,const KeyType key){ if(root == nullptr){ root = new Node(key); return root; } if(key < root->key){ //Less than the value of the current node, go left __insert(root->left,key); root = __balance(root); //Balance the current node return root; }else if(key > root->key){ //Greater than the value of the current node, go right __insert(root->right,key); root = __balance(root); //Balance the current node return root; }else{ return root; } } //Insert external interface
template <typename KeyType>
bool AVLTree<KeyType>::insert(const KeyType key){ return __insert(avlroot,key) == nullptr ? false : true;
}
balancing operation
//Find the height of the tree
template <typename KeyType>
int AVLTree<KeyType>::__getheight(const Node *root){ if(root == nullptr) return 0; return max(__getheight(root->left) , __getheight(root->right)) + 1;
} //Find the balance factor
template <typename KeyType>
int AVLTree<KeyType>::__diff(const Node *root){ if(root == nullptr) return 0; return __getheight(root->left) - __getheight(root->right);
} //balance operation
template <typename KeyType>
AVLNode<KeyType> *AVLTree<KeyType>::__balance(Node *root){ int dis = __diff(root); if(dis > 1){//The left subtree is higher than the right subtree if(__diff(root->left) > 0) root = __rotation_ll(root);//rotate left else root = __rotation_lr(root);//Rotate left and right }else if(dis < -1){//The right subtree is higher than the left subtree if(__diff(root->right) < 0) root = __rotation_rr(root);//Rotate right else root = __rotation_rl(root);//Rotate right and left } return root;
}
rotation operation
The core part of a balanced binary tree is the rotation operation. In order to ensure the balance of the binary tree, it is necessary to determine whether the current node is balanced every time a node is inserted or deleted. If it is unbalanced, a rotation operation is required. According to the actual situation of the binary tree, it can be divided into four types: single rotation (left-left, right-right), double rotation (left-right, right-left). Baidu has many detailed explanations, so I won’t go into details here. The code is as follows:
//Four kinds of rotation
template <typename KeyType>
AVLNode<KeyType> *AVLTree<KeyType>::__rotation_ll(Node *root){ Node *temp = root->left; root->left = temp->right; temp->right = root; return temp;
}
template <typename KeyType>
AVLNode<KeyType> *AVLTree<KeyType>::__rotation_rr(Node *root){ Node *temp = root->right; root->right = temp->left; temp->left = root; return temp;
}
template <typename KeyType>
AVLNode<KeyType> *AVLTree<KeyType>::__rotation_lr(Node *root){ root->left = __rotation_rr(root->left); return __rotation_ll(root);
}
template <typename KeyType>
AVLNode<KeyType> *AVLTree<KeyType>::__rotation_rl(Node *root){ root->right = __rotation_ll(root->right); return __rotation_rr(root);
}
delete node
When deleting a node, you need to discuss it on a case-by-case basis, and remember to perform balancing operations after deleting the node.
//Delete the internal implementation of the node
template <typename KeyType>
AVLNode<KeyType> *AVLTree<KeyType>::__delnode(Node *root,const KeyType key){ if(root == nullptr) return root; if(!search(key)){ //The deleted node does not exist cout << "Key not find!" << endl; return root; } if(key == root->key){ if (root->left != nullptr && root->right != nullptr) { //Both the left and right subtrees of the deleted node are not empty. if(__diff(root) > 0){ //The left subtree is higher root->key = __treeMax(root->left)->key; //Find the maximum value of the left subtree to replace the current node and make it sink into a leaf node root->left = __delnode(root->left, root->key); //Delete the replaced current node in the left subtree }else{ //The right subtree is higher root->key = __treeMin(root->right)->key; //Find the minimum value of the right subtree to replace the current node root->right = __delnode(root->right, root->key); } }else{ //The deleted node has a child or the deleted node itself is a leaf node Node * temp = root; root = (root->left) ? (root->left) : (root->right); delete temp; temp = nullptr; //Avoid wild pointers } }else if(key < root->key){ //If the value is less than the current node, look for it in the left subtree root->left = __delnode(root->left,key); root = __balance(root); }else{ //If the value is greater than the current node, search to the right subtree root->right = __delnode(root->right,key); root = __balance(root); } return root;
} //Delete external interface
template <typename KeyType>
bool AVLTree<KeyType>::delnode(const KeyType key){ return __delnode(avlroot,key) == nullptr ? false : true;
}
Overall implementation code and testing
#include <iostream>
#include <algorithm> using namespace std; template <typename KeyType>
class AVLNode{ public: KeyType key; AVLNode *left; AVLNode *right; AVLNode(KeyType k):key(k),left(nullptr),right(nullptr){}
}; template <typename KeyType>
class AVLTree{ typedef AVLNode<KeyType> Node; private: Node *avlroot; int __getheight(const Node *root);//Find the height of the tree int __diff(const Node *root);//Find the balance factor Node *__insert(Node *&root,const KeyType key);//Insert internal implementation Node *__delnode(Node *root,const KeyType key);//Delete internal implementation Node *__balance(Node *root);//balance operation //Four kinds of rotation operations Node *__rotation_ll(Node *root); Node *__rotation_rr(Node *root); Node *__rotation_lr(Node *root); Node *__rotation_rl(Node *root); Node *__search(Node *root,const KeyType key);//Find internal implementation void __traversal(Node *root);//Traversal (in-order) internal implementation void __deleteTree(Node *root);//delete tree Node *__treeMax(Node *root);//The previous root node is the largest Node *__treeMin(Node *root);//The front root node is the smallest public: AVLTree(){avlroot = nullptr;} //Default constructor ~AVLTree(); AVLTree(const KeyType *arr,int len); //Constructor, array construction bool insert(const KeyType key);//Insert external interface bool search(const KeyType key);//Find external interface void traversal();//Traverse (in-order) external interface bool delnode(const KeyType key);//Delete external interface
}; //All internal implementations
//Find the height of the tree
template <typename KeyType>
int AVLTree<KeyType>::__getheight(const Node *root){ if(root == nullptr) return 0; return max(__getheight(root->left) , __getheight(root->right)) + 1;
} //Find the balance factor
template <typename KeyType>
int AVLTree<KeyType>::__diff(const Node *root){ if(root == nullptr) return 0; return __getheight(root->left) - __getheight(root->right);
} //Insert internal implementation
template <typename KeyType>
AVLNode<KeyType> *AVLTree<KeyType>::__insert(Node *&root,const KeyType key){ if(root == nullptr){ root = new Node(key); return root; } if(key < root->key){ __insert(root->left,key); root = __balance(root); return root; }else if(key > root->key){ __insert(root->right,key); root = __balance(root); return root; }else{ return root; } } //balance operation
template <typename KeyType>
AVLNode<KeyType> *AVLTree<KeyType>::__balance(Node *root){ int dis = __diff(root); if(dis > 1){//The left subtree is higher than the right subtree if(__diff(root->left) > 0) root = __rotation_ll(root); else root = __rotation_lr(root); }else if(dis < -1){//The right subtree is higher than the left subtree if(__diff(root->right) < 0) root = __rotation_rr(root); else root = __rotation_rl(root); } return root;
} //Four kinds of rotation
template <typename KeyType>
AVLNode<KeyType> *AVLTree<KeyType>::__rotation_ll(Node *root){ Node *temp = root->left; root->left = temp->right; temp->right = root; return temp;
}
template <typename KeyType>
AVLNode<KeyType> *AVLTree<KeyType>::__rotation_rr(Node *root){ Node *temp = root->right; root->right = temp->left; temp->left = root; return temp;
}
template <typename KeyType>
AVLNode<KeyType> *AVLTree<KeyType>::__rotation_lr(Node *root){ root->left = __rotation_rr(root->left); return __rotation_ll(root);
}
template <typename KeyType>
AVLNode<KeyType> *AVLTree<KeyType>::__rotation_rl(Node *root){ root->right = __rotation_ll(root->right); return __rotation_rr(root);
} //Find internal implementation
template <typename KeyType>
AVLNode<KeyType> *AVLTree<KeyType>::__search(Node *root,const KeyType key){ if(root == nullptr) return nullptr; if(key == root->key) return root; else if(key < root->key) return __search(root->left,key); else return __search(root->right,key);
} //Traversal (in-order) internal implementation
template <typename KeyType>
void AVLTree<KeyType>::__traversal(Node *root){ if(root == nullptr) return; __traversal(root->left); cout << root->key << " "; __traversal(root->right);
} template <typename KeyType>
AVLNode<KeyType> *AVLTree<KeyType>::__treeMax(Node *root){ return (root->right) ? __treeMax(root->right) : root;
}
template <typename KeyType>
AVLNode<KeyType> *AVLTree<KeyType>::__treeMin(Node *root){ return (root->left) ? __treeMin(root->left) : root;
} //Delete the internal implementation of the node
template <typename KeyType>
AVLNode<KeyType> *AVLTree<KeyType>::__delnode(Node *root,const KeyType key){ if(root == nullptr) return root; if(!search(key)){ cout << "Key not find!" << endl; return root; } if(key == root->key){ if (root->left != nullptr && root->right != nullptr) { if(__diff(root) > 0){ root->key = __treeMax(root->left)->key; root->left = __delnode(root->left, root->key); }else{ root->key = __treeMin(root->right)->key; root->right = __delnode(root->right, root->key); } }else{ Node * temp = root; root = (root->left) ? (root->left) : (root->right); delete temp; temp = nullptr; } }else if(key < root->key){ root->left = __delnode(root->left,key); root = __balance(root); }else{ root->right = __delnode(root->right,key); root = __balance(root); } return root;
} //delete tree
template <typename KeyType>
void AVLTree<KeyType>::__deleteTree(Node *root){ if(root == nullptr) return; __deleteTree(root->left); __deleteTree(root->right); delete root; root = nullptr; return;
} //All external interfaces
//Constructor-array construction
template <typename KeyType>
AVLTree<KeyType>::AVLTree(const KeyType *arr,int len){ avlroot = nullptr; for(int i = 0;i < len;i++){ insert(*(arr + i)); }
} //Insert external interface
template <typename KeyType>
bool AVLTree<KeyType>::insert(const KeyType key){ return __insert(avlroot,key) == nullptr ? false : true;
} //Find external interface
template <typename KeyType>
bool AVLTree<KeyType>::search(const KeyType key){ return __search(avlroot,key) == nullptr ? false : true;
} //Traverse (in-order) external interface
template <typename KeyType>
void AVLTree<KeyType>::traversal(){ __traversal(avlroot);
} //Delete external interface
template <typename KeyType>
bool AVLTree<KeyType>::delnode(const KeyType key){ return __delnode(avlroot,key) == nullptr ? false : true;
} //destructor
template <typename KeyType>
AVLTree<KeyType>::~AVLTree(){ __deleteTree(avlroot);
} int main(){ int arr[] = {16,3,7,11,9,26,18,14,15}; AVLTree<int> tree(arr,sizeof(arr)/sizeof(arr[0])); tree.traversal(); cout << endl; tree.insert(8); tree.traversal(); cout << endl; if(tree.search(14)){ cout << "Found!" << endl; }else{ cout << "Not Found!" << endl; } tree.delnode(11); tree.traversal(); cout << endl; if(tree.search(11)) { cout << "Found!" << endl; } else { cout << "Not Found!" << endl; } return 0;
}