【C++】AVL树的实现及测试

**AVL树的实现及测试**
=====================###什么是AVL树AVL树是一种自平衡二叉查找树，保证了每个节点的高度相差不超过1。这种结构使得在插入或删除一个元素时，不需要重新构建整个树，而是通过旋转来维持树的平衡。

### AVL树的实现

cpp#include <iostream>
using namespace std;

// 定义AVL树结点结构体struct Node {
 int key;
 Node* left;
 Node* right;
};

// 定义AVL树类class AVLTree {
public:
 // 构造函数 AVLTree() : root(nullptr) {}

 // 销毁函数 ~AVLTree() { destroy(root); }

 // 插入元素函数 void insert(int key);

 // 删除元素函数 void remove(int key);

 // 查找元素函数 Node* find(int key);

 // 打印树结构函数 void print();

private:
 // 根结点指针 Node* root;

 // 销毁子树函数 void destroy(Node* node);
};

// 构造函数实现AVLTree::AVLTree() : root(nullptr) {}

// 销毁函数实现void AVLTree::destroy(Node* node) {
 if (node == nullptr)
 return;
 destroy(node->left);
 destroy(node->right);
 delete node;
}

// 插入元素函数实现void AVLTree::insert(int key) {
 root = insert(root, key);
}

Node* AVLTree::insert(Node* node, int key) {
 if (node == nullptr)
 return new Node{key, nullptr, nullptr};

 if (key < node->key)
 node->left = insert(node->left, key);
 else if (key > node->key)
 node->right = insert(node->right, key);

 // 计算平衡因子 int balanceFactor = getBalanceFactor(node);

 // 左旋转 if (balanceFactor >1 && key < node->left->key) {
 Node* temp = node->left;
 node->left = rotateRight(node->left);
 node->left->right = temp;
 return rotateLeft(node);
 }

 // 右旋转 if (balanceFactor < -1 && key > node->right->key) {
 Node* temp = node->right;
 node->right = rotateLeft(node->right);
 node->right->left = temp;
 return rotateRight(node);
 }

 return node;
}

// 删除元素函数实现void AVLTree::remove(int key) {
 root = remove(root, key);
}

Node* AVLTree::remove(Node* node, int key) {
 if (node == nullptr)
 return node;

 if (key < node->key)
 node->left = remove(node->left, key);
 else if (key > node->key)
 node->right = remove(node->right, key);
 else {
 // 无子树 if (node->left == nullptr && node->right == nullptr) {
 delete node;
 return nullptr;
 }

 // 有一个子树 Node* temp;
 if (node->left == nullptr)
 temp = node->right;
 else if (node->right == nullptr)
 temp = node->left;
 else {
 //两个子树 temp = findMin(node->right);
 node->key = temp->key;
 node->right = remove(node->right, key);
 }
 return temp;
 }

 int balanceFactor = getBalanceFactor(node);

 if (balanceFactor >1 && getBalanceFactor(node->left) >=0)
 return rotateRight(node);

 if (balanceFactor < -1 && getBalanceFactor(node->right) <=0)
 return rotateLeft(node);

 if (balanceFactor >1 && getBalanceFactor(node->left) < 0)
 node->left = rotateLeft(node->left);
 else node->right = rotateRight(node->right);

 return node;
}

// 查找元素函数实现Node* AVLTree::find(int key) {
 Node* node = root;
 while (node != nullptr && key != node->key) {
 if (key < node->key)
 node = node->left;
 else node = node->right;
 }
 return node;
}

// 打印树结构函数实现void AVLTree::print() {
 print(root);
}

void AVLTree::print(Node* node) {
 if (node == nullptr)
 return;

 print(node->right);
 cout << node->key << " ";
 print(node->left);
}

cppint main() {
 AVLTree tree;
 tree.insert(10);
 tree.insert(20);
 tree.insert(30);
 tree.insert(40);
 tree.insert(50);

 cout << "树结构:" << endl;
 tree.print();

 tree.remove(20);
 cout << "
树结构(删除20):" << endl;
 tree.print();

 return0;
}

树结构:
5040302010树结构(删除20):
50403010