平衡二叉树

介绍：平衡二叉树（AVL树）是一种自平衡的二叉搜索树，具有以下特点：任意节点的左右子树高度差不超过1。这种性质通过旋转操作来维持，以保持树的平衡性。

以下是一个简单的平衡二叉树的示例图表：         10        /  \       5    15      / \  /  \     3   7 13  17

在C++中，我们可以使用类来实现平衡二叉树。下面是一个简单的示例代码：

```cpp #include <iostream>

class Node { public:     int key;     Node* left;     Node* right;     int height;

    Node(int k) : key(k), left(nullptr), right(nullptr), height(1) {} };

class AVLTree { private:     Node* root;

    int getHeight(Node* node) {         return (node == nullptr) ? 0 : node->height;     }

    int getBalance(Node* node) {         return (node == nullptr) ? 0 : getHeight(node->left) - getHeight(node->right);     }

    Node* rightRotate(Node* y) {         Node* x = y->left;         Node* T = x->right;

        x->right = y;         y->left = T;

        y->height = 1 + std::max(getHeight(y->left), getHeight(y->right));         x->height = 1 + std::max(getHeight(x->left), getHeight(x->right));

        return x;     }

    Node* leftRotate(Node* x) {         Node* y = x->right;         Node* T = y->left;

        y->left = x;         x->right = T;

        x->height = 1 + std::max(getHeight(x->left), getHeight(x->right));         y->height = 1 + std::max(getHeight(y->left), getHeight(y->right));

        return y;     }

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

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

        node->height = 1 + std::max(getHeight(node->left), getHeight(node->right));         int balance = getBalance(node);

        // Left Left Case         if (balance > 1 && key < node->left->key) {             return rightRotate(node);         }         // Right Right Case         if (balance < -1 && key > node->right->key) {             return leftRotate(node);         }         // Left Right Case         if (balance > 1 && key > node->left->key) {             node->left = leftRotate(node->left);             return rightRotate(node);         }         // Right Left Case         if (balance < -1 && key < node->right->key) {             node->right = rightRotate(node->right);             return leftRotate(node);         }

        return node;     }

public:     AVLTree() : root(nullptr) {}

    void insert(int key) {         root = insert(root, key);     }

    void display(Node* node) {         if (node != nullptr) {             display(node->left);             std::cout << node->key << " ";             display(node->right);         }     }

    void displayTree() {         display(root);     } };

int main() {     AVLTree tree;     tree.insert(10);     tree.insert(5);     tree.insert(15);     tree.insert(3);     tree.insert(7);     tree.insert(13);     tree.insert(17);

    std::cout << "AVL Tree: ";     tree.displayTree();     std::cout << std::endl;

    return 0; } ```

以上代码演示了如何实现一个简单的平衡二叉树，并在其中插入一些节点。在实践中，还可以扩展这些基本操作以满足更多需求。