平衡二叉树

平衡二叉树（Balanced Binary Tree）是一种特殊的二叉树，它在结构上保持一定的平衡，以确保在最坏情况下依然具有较好的查找、插入和删除性能。

平衡二叉树的定义

平衡的具体定义可以根据不同类型的平衡树略有不同。一般来说，一个二叉树是平衡的，当其任意节点的左右子树高度差的绝对值不超过某个特定值（通常是1）时。

常见类型的平衡二叉树

AVL树：

每个节点的左右子树高度差（平衡因子）只允许为 -1、0 或 1。

在插入或删除节点后，如果导致不平衡，会通过旋转操作来恢复平衡。

#include <iostream>
#include <algorithm> // 用于 std::max
using namespace std;

// 节点结构
struct Node {
    int key;       // 节点值
    Node* left;    // 左子节点
    Node* right;   // 右子节点
    int height;    // 节点高度

    Node(int k) : key(k), left(nullptr), right(nullptr), height(1) {} // 初始化节点
};

// 获取节点的高度
int getHeight(Node* node) {
    return node ? node->height : 0;
}

// 获取平衡因子
int getBalanceFactor(Node* node) {
    return node ? getHeight(node->left) - getHeight(node->right) : 0;
}

// 更新节点的高度
void updateHeight(Node* node) {
    node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
}

// 右旋操作
Node* rightRotate(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;

    // 右旋转
    x->right = y;
    y->left = T2;

    // 更新高度
    updateHeight(y);
    updateHeight(x);

    // 返回新的根节点
    return x;
}

// 左旋操作
Node* leftRotate(Node* x) {
    Node* y = x->right;
    Node* T2 = y->left;

    // 左旋转
    y->left = x;
    x->right = T2;

    // 更新高度
    updateHeight(x);
    updateHeight(y);

    // 返回新的根节点
    return y;
}

// 插入节点并保持平衡
Node* insert(Node* node, int key) {
    // 1. 标准的二叉搜索树插入
    if (!node) 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;
    }

    // 2. 更新当前节点的高度
    updateHeight(node);

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

    // 4. 根据平衡因子进行相应的旋转操作
    // 左左情况
    if (balanceFactor > 1 && key < node->left->key) {
        return rightRotate(node);
    }

    // 右右情况
    if (balanceFactor < -1 && key > node->right->key) {
        return leftRotate(node);
    }

    // 左右情况
    if (balanceFactor > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // 右左情况
    if (balanceFactor < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    // 返回不变的节点指针
    return node;
}

// 中序遍历树以显示结果
void inOrder(Node* root) {
    if (root) {
        inOrder(root->left);
        cout << root->key << " ";
        inOrder(root->right);
    }
}

// 主函数测试AVL树
int main() {
    Node* root = nullptr;

    // 插入一些节点
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25);

    // 中序遍历 AVL 树
    cout << "中序遍历 AVL 树: ";
    inOrder(root);
    cout << endl;

    return 0;
}

红黑树：
- 是一种自平衡的二叉搜索树，每个节点都有一个颜色属性（红色或黑色），并遵循特定的颜色规则。
- 保证从根到叶的路径上的黑色节点数量相同，从而保持树的平衡性。

平衡二叉树的特点

时间复杂度：
- 查找、插入和删除操作的时间复杂度通常为 O(\log n)，这使得平衡二叉树非常高效，特别是在大量数据的情况下。
空间复杂度：
- 平衡二叉树的空间复杂度为 O(n)，与普通的二叉树相同。
自我平衡：
- 在插入或删除节点时，通过旋转和调整树的结构，保持树的平衡，从而避免退化成链表。

旋转操作是平衡二叉树（如 AVL 树和红黑树）中的重要技术，用于在插入或删除节点后恢复树的平衡。旋转操作可以分为两种类型：左旋（Left Rotation）和右旋（Right Rotation）。以下是这两种旋转的详细介绍及其实现。

平衡二叉树的调整

首先注意，右旋（L）实际上是将树向左旋转，左旋则是将树向右旋转

1. 右旋（Right Rotation）

右旋操作是将某个节点（称为“失衡节点”）的左子节点提升为新的根节点，同时将失衡节点降为新根节点的右子节点。

右旋的步骤

设失衡节点为 y，其左子节点为 x。
将 x 的右子节点（如果存在）连接到 y 的左子节点。
将 x 提升为新的根节点。
将 y 设为 x 的右子节点。

右旋的伪代码

struct TreeNode {
    int key;
    TreeNode* left;
    TreeNode* right;
    int height; // 用于 AVL 树的高度
};

// 右旋操作
TreeNode* rightRotate(TreeNode* y) {
    TreeNode* x = y->left;           // 让 x 指向 y 的左子节点
    TreeNode* T2 = x->right;         // 保存 x 的右子节点

    // 进行旋转
    x->right = y;                    // 将 y 设置为 x 的右子节点
    y->left = T2;                    // 将 T2 设置为 y 的左子节点

    // 更新高度（如果需要）
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    return x; // 返回新的根节点
}

2. 左旋（Left Rotation）

左旋操作是将某个节点的右子节点提升为新的根节点，同时将失衡节点降为新根节点的左子节点。

左旋的步骤

设失衡节点为 x，其右子节点为 y。
将 y 的左子节点（如果存在）连接到 x 的右子节点。
将 y 提升为新的根节点。
将 x 设为 y 的左子节点。

左旋的伪代码

// 左旋操作
TreeNode* leftRotate(TreeNode* x) {
    TreeNode* y = x->right;         // 让 y 指向 x 的右子节点
    TreeNode* T2 = y->left;         // 保存 y 的左子节点

    // 进行旋转
    y->left = x;                    // 将 x 设置为 y 的左子节点
    x->right = T2;                  // 将 T2 设置为 x 的右子节点

    // 更新高度（如果需要）
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    return y; // 返回新的根节点
}