There is no uniform rotation operation for AVLTree (C++ implementation)
- 2020-07-21 09:12:36
- OfStack
Recently, due to the severe epidemic situation, I could only rest at home. In my spare time, I realized C++ once
The university teacher only taught some simple data structures and algorithms. These high-level data structures still need to be learned actively and implemented by hands.
I had only heard of AVLTree before, and it took me about 3 days to go from reading about the principle to writing it point by point and debugging it in point 1. I think it's been a long time.
The AVL tree is generally not written by us, but in order to have a copy of the implemented code that I can review later, I decided to be tough on myself and implement it once
The following code adopts C++11 standard
It was compiled and debuggable on ubuntu 18.04
/*
* BinarySearchTree.h
* 1. When you add an element, you have to decide for yourself whether it is legal or not
* 2. In addition to the hierarchical traversal, this source code is used recursive traversal, to reduce the consumption of the stack, should be implemented recursive traversal
* 3. This code is implemented AVL The tree without system 1 Rotation operation is discussed by case LL,LR,RR,RL To balance the tree
* Created on: 2020 years 1 month 29 day
* Author: LuYonglei
*/
#ifndef SRC_BINARYSEARCHTREE_H_
#define SRC_BINARYSEARCHTREE_H_
#include <queue>
template<typename Element>
class BinarySearchTree {
public:
BinarySearchTree(int (*cmp)(Element e1, Element e2)); // Comparison function pointer
virtual ~BinarySearchTree();
int size(); // Number of elements
bool isEmpty(); // Whether is empty
void clear() {
// Empty all the elements
NODE *node = root_;
root_ = nullptr;
using namespace std;
queue<NODE*> q;
q.push(node);
while (!q.empty()) {
NODE *tmp = q.front();
if (tmp->left != nullptr)
q.push(tmp->left);
if (tmp->right != nullptr)
q.push(tmp->right);
delete tmp;
q.pop();
}
}
void add(Element e) {
// Add elements
add(e, cmp_);
}
void remove(Element e) {
// Remove elements
remove(Node(e, cmp_));
}
bool contains(Element e) {
// Whether it contains an element
return Node(e, cmp_) != nullptr;
}
void preorderTraversal(bool (*visitor)(Element &e)) {
// The former sequence traversal
if (visitor == nullptr)
return;
bool stop = false; // Stop sign, if stop for true , then stop the traversal
preorderTraversal(root_, stop, visitor);
}
void inorderTraversal(bool (*visitor)(Element &e)) {
// In the sequence traversal
if (visitor == nullptr)
return;
bool stop = false; // Stop sign, if stop for true , then stop the traversal
inorderTraversal(root_, stop, visitor);
}
void postorderTraversal(bool (*visitor)(Element &e)) {
// After the sequence traversal
if (visitor == nullptr)
return;
bool stop = false; // Stop sign, if stop for true , then stop the traversal
postorderTraversal(root_, stop, visitor);
}
void levelOrderTraversal(bool (*visitor)(Element &e)) {
// Sequence traversal, iterative implementation
if (visitor == nullptr)
return;
levelOrderTraversal(root_, visitor);
}
int height() {
// The height of the tree
return height(root_);
}
bool isComplete() {
// To determine whether it is complete 2 tree
return isComplete(root_);
}
private:
int size_;
typedef struct _Node {
Element e;
_Node *parent;
_Node *left;
_Node *right;
int height; // Node height
_Node(Element e_, _Node *parent_) :
e(e_), parent(parent_), left(nullptr), right(nullptr), height(1) {
// Node constructor
}
inline bool isLeaf() {
return (left == nullptr && right == nullptr);
}
inline bool hasTwoChildren() {
return (left != nullptr && right != nullptr);
}
inline int balanceFactor() {
// Get the equilibrium factor of the node
int leftHeight = left == nullptr ? 0 : left->height; // Gets the height of the left subtree
int rightHeight = right == nullptr ? 0 : right->height; // Gets the height of the right subtree
return leftHeight - rightHeight;
}
inline bool isBalanced() {
// judge node Whether the balance
int balanceFactor_ = balanceFactor();
return balanceFactor_ >= -1 && balanceFactor_ <= 1; // Equilibrium factor is -1,0,1 It returns true
}
inline void updateHeight() {
// Update the height of the node
int leftHeight = left == nullptr ? 0 : left->height; // Gets the height of the left subtree
int rightHeight = right == nullptr ? 0 : right->height; // Gets the height of the right subtree
height = 1 + (leftHeight > rightHeight ? leftHeight : rightHeight); // Update the node height to the maximum height of the left and right subtrees +1
}
inline bool isLeftChild() {
// Determines whether a node is the left child of its parent
return parent != nullptr && parent->left == this;
}
inline bool isRightChild() {
// Determines whether a node is the right child of its parent
return parent != nullptr && parent->right == this;
}
inline _Node* tallerChild() {
// Get a higher height subtree
int leftHeight = left == nullptr ? 0 : left->height; // Gets the height of the left subtree
int rightHeight = right == nullptr ? 0 : right->height; // Gets the height of the right subtree
if (leftHeight > rightHeight)
return left;
if (leftHeight < rightHeight)
return right;
return isLeftChild() ? left : right;
}
} NODE;
NODE *root_;
int (*cmp_)(Element e1, Element e2); // To implement a personalized configuration for sorting trees, private members are saved 1 A pointer to a comparison function
NODE* Node(Element e, int (*cmp_)(Element e1, Element e2)) {
// return e The node where the element is located
NODE *node = root_;
while (node != nullptr) {
int cmp = cmp_(e, node->e);
if (cmp == 0) // We find the element
return node;
if (cmp > 0) { // The element to be found is larger than the element stored by the node
node = node->right;
} else { // The element to be found is smaller than the element stored by the node
node = node->left;
}
}
return nullptr;
}
NODE* predecessor(NODE *node) {
// return node Of the precursor nodes
if (node == nullptr)
return nullptr;
// The precursor node is in the left subtree
NODE *tmp = node->left;
if (tmp != nullptr) {
while (tmp->right != nullptr)
tmp = tmp->right;
return tmp;
}
// Look for the precursor node from the parent node and the grandfather node
while (node->parent != nullptr && node == node->parent->left) {
node = node->parent;
}
return node->parent;
}
NODE* successor(NODE *node) {
// return node Successor node
if (node == nullptr)
return nullptr;
// The successor node is in the right subtree
NODE *tmp = node->right;
if (tmp != nullptr) {
while (tmp->left != nullptr)
tmp = tmp->left;
return tmp;
}
// Look for a successor node from a parent node and a grandfather node
while (node->parent != nullptr && node == node->parent->right) {
node = node->parent;
}
return node->parent;
}
void afterRotate(NODE *gNode, NODE *pNode, NODE *child) {
// In left rotation and right rotation system 1 call
pNode->parent = gNode->parent;
if (gNode->isLeftChild())
gNode->parent->left = pNode;
else if (gNode->isRightChild())
gNode->parent->right = pNode;
else
// At this time gNode->parent for nullptr . gNode for root node
root_ = pNode;
if (child != nullptr)
child->parent = gNode;
gNode->parent = pNode;
// The left and right subtrees change, so update the height
gNode->updateHeight();
pNode->updateHeight();
}
void rotateLeft(NODE *gNode) {
// right gNode Rotate to the left
NODE *pNode = gNode->right;
NODE *child = pNode->left;
gNode->right = child;
pNode->left = gNode;
afterRotate(gNode, pNode, child);
}
void rotateRight(NODE *gNode) {
// right gNode Do a right rotation
NODE *pNode = gNode->left;
NODE *child = pNode->right;
gNode->left = child;
pNode->right = gNode;
afterRotate(gNode, pNode, child);
}
void rebalance(NODE *gNode) {
// To restore balance ,grand Is the unbalanced node with the lowest height
NODE *pNode = gNode->tallerChild();
NODE *nNode = pNode->tallerChild();
if (pNode->isLeftChild()) {
if (nNode->isLeftChild()) {
//LL
/*
* gNode
* / right gNode Right hand
* pNode ====> pNode
* / / \
* nNode nNode gNode
*/
rotateRight(gNode);
} else {
//LR
/*
* gNode gNode
* / right pNode left-handed / right gNode Right hand
* pNode ====> nNode ====> nNode
* \ / / \
* nNode pNode pNode gNode
*/
rotateLeft(pNode);
rotateRight(gNode);
}
} else {
if (nNode->isLeftChild()) {
//RL
/*
* gNode gNode
* \ right pNode Right hand \ right gNode left-handed
* pNode ====> nNode ====> nNode
* / \ / \
* nNode pNode gNode pNode
*/
rotateRight(pNode);
rotateLeft(gNode);
} else {
//RR
/*
* gNode
* \ right gNode left-handed
* pNode ====> pNode
* \ / \
* nNode gNode nNode
*/
rotateLeft(gNode);
}
}
}
void afterAdd(NODE *node) {
// add node Subsequent adjustment
if (node == nullptr)
return;
node = node->parent;
while (node != nullptr) {
if (node->isBalanced()) {
// If the node is balanced, update its height
node->updateHeight();
} else {
// At this time of the first 1 An unbalanced node is operated to make it balanced
rebalance(node);
// When the tree is back in balance , Jump out of the loop
break;
}
node = node->parent;
}
}
void add(Element e, int (*cmp_)(Element e1, Element e2)) {
// When the tree is empty, the added node is the root node of the tree
if (root_ == nullptr) {
root_ = new NODE(e, nullptr);
size_++;
// insert 1 The root nodes are then adjusted
afterAdd(root_);
return;
}
// When adding a node that is not a control 1 A node
NODE *parent = root_;
NODE *node = root_;
int cmp = 0; // Compare the results
while (node != nullptr) {
parent = node; // Save the parent node
cmp = cmp_(e, node->e); // Compared by function Pointers
if (cmp > 0) {
node = node->right; // The element added is greater than the element in the node
} else if (cmp < 0) {
node = node->left; // The element added is smaller than the element in the node
} else {
node->e = e; // When it's equal, it covers
return; // The added element is equal to the element in the node , Direct return
}
}
// Determine where to insert the parent node
NODE *newNode = new NODE(e, parent); // Create a node for the new element
if (cmp > 0) {
parent->right = newNode; // The element added is greater than the element in the node
} else {
parent->left = newNode; // The element added is smaller than the element in the node
}
size_++;
// add 1 The new nodes are then adjusted
afterAdd(newNode);
}
void afterRemove(NODE *node) {
// delete node Subsequent adjustment
if (node == nullptr)
return;
node = node->parent;
while (node != nullptr) {
if (node->isBalanced()) {
// If the node is balanced, update its height
node->updateHeight();
} else {
// At this point, the unbalanced node is operated to make it balanced
rebalance(node);
}
node = node->parent;
}
}
void remove(NODE *node_) {
// Delete a 1 node
if (node_ == nullptr)
return;
size_--;
// Priority deletion is 2 The nodes of the
if (node_->hasTwoChildren()) {
NODE *pre = successor(node_); // find node_ Successor node
node_->e = pre->e; // The coverage with the value of subsequent nodes is 2 The value of the node
// Remove successor nodes ( The degree of subsequent nodes can only be zero 1 or 0)
node_ = pre;
}
// At this time node_ The degree of theta must be 0 or 1
NODE *replacement = node_->left != nullptr ? node_->left : node_->right;
if (replacement != nullptr) { //node_ The degree of 1
replacement->parent = node_->parent;
if (node_->parent == nullptr) // Degree of 1 The root node
root_ = replacement;
else if (node_->parent->left == node_)
node_->parent->left = replacement;
else
node_->parent->right = replacement;
// All deletes are ready to complete, balancing before freeing node memory
afterRemove(node_);
delete node_;
} else if (node_->parent == nullptr) { //node_ It's a leaf node, it's a root node
root_ = nullptr;
// All deletes are ready to complete, balancing before freeing node memory
afterRemove(node_);
delete node_;
} else { //node_ It's a leaf node, not a root node
if (node_->parent->left == node_)
node_->parent->left = nullptr;
else
node_->parent->right = nullptr;
// All deletes are ready to complete, balancing before freeing node memory
afterRemove(node_);
delete node_;
}
}
void preorderTraversal(NODE *node, bool &stop,
bool (*visitor)(Element &e)) {
// Recursive implementation of the preorder traversal
if (node == nullptr || stop == true)
return;
stop = visitor(node->e);
preorderTraversal(node->left, stop, visitor);
preorderTraversal(node->right, stop, visitor);
}
void inorderTraversal(NODE *node, bool &stop, bool (*visitor)(Element &e)) {
// Sequential traversal in recursive implementation
if (node == nullptr || stop == true)
return;
inorderTraversal(node->left, stop, visitor);
if (stop == true)
return;
stop = visitor(node->e);
inorderTraversal(node->right, stop, visitor);
}
void postorderTraversal(NODE *node, bool &stop,
bool (*visitor)(Element &e)) {
// Recursive implementation of post-ordered traversal
if (node == nullptr || stop == true)
return;
postorderTraversal(node->left, stop, visitor);
postorderTraversal(node->right, stop, visitor);
if (stop == true)
return;
stop = visitor(node->e);
}
void levelOrderTraversal(NODE *node, bool (*visitor)(Element &e)) {
if (node == nullptr)
return;
using namespace std;
queue<NODE*> q;
q.push(node);
while (!q.empty()) {
NODE *node = q.front();
if (visitor(node->e) == true)
return;
if (node->left != nullptr)
q.push(node->left);
if (node->right != nullptr)
q.push(node->right);
q.pop();
}
}
int height(NODE *node) {
// some 1 Node height
return node->height;
}
bool isComplete(NODE *node) {
if (node == nullptr)
return false;
using namespace std;
queue<NODE*> q;
q.push(node);
bool leaf = false; // Determine if the next node is a leaf node
while (!q.empty()) {
NODE *node = q.front();
if (leaf && !node->isLeaf()) // Determine leaf node
return false;
if (node->left != nullptr) {
q.push(node->left);
} else if (node->right != nullptr) { //node->left == nullptr && node->right != nullptr
return false;
}
if (node->right != nullptr) {
q.push(node->right);
} else { //node->right==nullptr
leaf = true;
}
q.pop();
}
return true;
}
};
template<typename Element>
BinarySearchTree<Element>::BinarySearchTree(int (*cmp)(Element e1, Element e2)) :
size_(0), root_(nullptr), cmp_(cmp) {
// Tree constructor
}
template<typename Element>
BinarySearchTree<Element>::~BinarySearchTree() {
// The destructor
clear();
}
template<typename Element>
inline int BinarySearchTree<Element>::size() {
// Returns the number of elements
return size_;
}
template<typename Element>
inline bool BinarySearchTree<Element>::isEmpty() {
// Determine if it is an empty tree
return size_ == 0;
}
#endif /* SRC_BINARYSEARCHTREE_H_ */
main methods
/*
* main.cpp
*
* Created on: 2020 years 1 month 29 day
* Author: LuYonglei
*/
#include "BinarySearchTree.h"
#include <iostream>
#include <time.h>
using namespace std;
template<typename Element>
int compare(Element e1, Element e2) {
// The comparison function , The same return 0,e1<e2 return -1,e1>e2 return 1
return e1 == e2 ? 0 : (e1 < e2 ? -1 : 1);
}
template<typename Elemnet>
bool visitor(Elemnet &e) {
cout << e << " ";
cout << endl;
return false; // If the return true , the traversal will exit
}
int main(int argc, char **argv) {
BinarySearchTree<double> a(compare);
// a.add(85);
// a.add(19);
// a.add(69);
// a.add(3);
// a.add(7);
// a.add(99);
// a.add(95);
// a.add(2);
// a.add(1);
// a.add(70);
// a.add(44);
// a.add(58);
// a.add(11);
// a.add(21);
// a.add(14);
// a.add(93);
// a.add(57);
// a.add(4);
// a.add(56);
// a.remove(99);
// a.remove(85);
// a.remove(95);
clock_t start = clock();
for (int i = 0; i < 1000000; i++) {
a.add(i);
}
for (int i = 0; i < 1000000; i++) {
a.remove(i);
}
// a.inorderTraversal(visitor);
clock_t end = clock();
cout << end - start << endl;
// cout <<a.height()<< endl;
// cout << a.isComplete() << endl;
// a.remove(7);
// a.clear();
// a.levelOrderTraversal(visitor);
// cout << endl;
// cout<<a.contains(0)<<endl;
}
conclusion
Above is the site to introduce AVLTree (C++ implementation) no 1 rotation problem, I hope to help you!