平衡二叉搜索树--AVL详解剖析

**平衡二叉搜索树—AVL详解**

平衡二叉搜索树（Balanced Binary Search Tree）是计算机科学中一个重要的数据结构，它能够保证在插入、删除操作后，树的高度始终保持相对稳定的状态。这使得它成为许多应用场景中的首选选择。

本文将详细介绍AVL树（Adelson-Velskii and Landis），一种最著名的平衡二叉搜索树。我们将讨论其定义、性质、构造方法以及插入和删除操作的实现。

**定义**

AVL树是一种自平衡的二叉搜索树，每个节点都有一个高度（height），它是从根到该节点的最大深度。对于任何结点，左子树和右子树都是平衡的，即它们的高度差不超过1。

**性质**

AVL树具有以下重要性质：

* **自平衡性**：AVL树保证在插入或删除操作后，树的高度始终保持相对稳定的状态。
* **搜索效率**：由于AVL树是二叉搜索树，每次查找都能以O(log n)时间复杂度完成。
* **插入和删除效率**：虽然AVL树在插入或删除操作时可能需要进行旋转来维持平衡，但其平均时间复杂度仍然为O(log n)。

**构造方法**

AVL树的构造方法非常简单。我们可以将其视为一个普通的二叉搜索树，然后在每次插入或删除操作后，通过检查当前结点及其子结点的高度差来决定是否需要进行旋转。

**插入操作**

当我们向AVL树中插入一个新结点时，我们首先将其作为叶结点添加到树中。然后，我们从根结点开始向下遍历，直到找到一个位置可以插入新结点的父结点。

在这个过程中，我们需要检查当前结点及其子结点的高度差。如果高度差超过1，我们就需要进行旋转来维持平衡。

**删除操作**

当我们从AVL树中删除一个结点时，我们首先找到该结点的父结点，然后将其替换为其孩子结点之一。然后，我们再次向上遍历，直到找到一个位置可以更新高度差的父结点。

在这个过程中，我们需要检查当前结点及其子结点的高度差。如果高度差超过1，我们就需要进行旋转来维持平衡。

**示例代码**

下面是AVL树的示例代码：

cpp#include <iostream>
using namespace std;

// 结点结构体struct Node {
 int key;
 Node* left;
 Node* right;
};

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

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

 // 插入函数 void insert(int key) {
 Node* newNode = new Node();
 newNode->key = key;
 newNode->left = nullptr;
 newNode->right = nullptr;

 root = insertNode(root, newNode);
 }

 // 删除函数 void remove(int key) {
 root = removeNode(root, key);
 }

 // 查找函数 bool search(int key) {
 return searchNode(root, key);
 }

private:
 Node* root; // 根结点 // 插入结点函数 Node* insertNode(Node* node, Node* newNode) {
 if (node == nullptr) {
 return newNode;
 }

 if (newNode->key < node->key) {
 node->left = insertNode(node->left, newNode);
 } else if (newNode->key > node->key) {
 node->right = insertNode(node->right, newNode);
 } else {
 // 重复键值 return node;
 }

 // 更新高度差 int leftHeight = getHeight(node->left);
 int rightHeight = getHeight(node->right);

 if (abs(leftHeight - rightHeight) >1) {
 // 左子树高于右子树 if (leftHeight > rightHeight) {
 return rotateRight(node, newNode);
 } else {
 return rotateLeft(node, newNode);
 }
 }

 return node;
 }

 // 删除结点函数 Node* removeNode(Node* node, int key) {
 if (node == nullptr) {
 return node;
 }

 if (key < node->key) {
 node->left = removeNode(node->left, key);
 } else if (key > node->key) {
 node->right = removeNode(node->right, key);
 } else {
 // 找到结点 Node* temp = node;
 if (node->left == nullptr && node->right == nullptr) {
 return nullptr; // 无孩子结点 }

 if (node->left == nullptr) {
 return node->right; // 只有右孩子结点 }

 if (node->right == nullptr) {
 return node->left; // 只有左孩子结点 }

 // 有两个孩子结点 Node* temp = findMin(node->right);
 node->key = temp->key;
 node->right = removeNode(node->right, key);
 }

 // 更新高度差 int leftHeight = getHeight(node->left);
 int rightHeight = getHeight(node->right);

 if (abs(leftHeight - rightHeight) >1) {
 // 左子树高于右子树 if (leftHeight > rightHeight) {
 return rotateRight(node, nullptr);
 } else {
 return rotateLeft(node, nullptr);
 }
 }

 return node;
 }

 // 查找结点函数 bool searchNode(Node* node, int key) {
 if (node == nullptr) {
 return false; // 未找到 }

 if (key < node->key) {
 return searchNode(node->left, key);
 } else if (key > node->key) {
 return searchNode(node->right, key);
 } else {
 return true; // 找到结点 }
 }

 // 旋转函数 Node* rotateLeft(Node* node, Node* newNode) {
 Node* temp = node->right;
 node->right = temp->left;
 temp->left = node;

 if (newNode != nullptr) {
 newNode->key = temp->key;
 }

 return temp;
 }

 Node* rotateRight(Node* node, Node* newNode) {
 Node* temp = node->left;
 node->left = temp->right;
 temp->right = node;

 if (newNode != nullptr) {
 newNode->key = temp->key;
 }

 return temp;
 }

 // 获取高度函数 int getHeight(Node* node) {
 if (node == nullptr) {
 return0; // 高度为0 }

 return1 + max(getHeight(node->left), getHeight(node->right));
 }

 // 销毁函数 void destroy(Node* node) {
 if (node != nullptr) {
 destroy(node->left);
 destroy(node->right);
 delete node;
 }
 }
};

int main() {
 AVLTree tree;

 tree.insert(5);
 tree.insert(3);
 tree.insert(7);
 tree.insert(2);
 tree.insert(4);
 tree.insert(6);
 tree.insert(8);

 cout << "是否存在键值5: " << (tree.search(5) ? "是" : "否") << endl;
 cout << "是否存在键值9: " << (tree.search(9) ? "是" : "否") << endl;

 tree.remove(3);
 cout << "是否存在键值3: " << (tree.search(3) ? "是" : "否") << endl;

 return0;
}