树

整理得吐血了，二叉树、红黑树、B&B+树超齐全，快速搞定数据结构 - 知乎 (zhihu.com)

通俗易懂的图文 红黑树,B树,B+树 本质区别及应用场景 - 知乎 (zhihu.com)

AVL树

属性

1. 左右子树的高度差小于等于 1。

2. 其每一个子树均为平衡二叉树。

平衡的原理

• 引入了监督机制，平衡因子（Balance Factor）

图解

详解 AVL 树（基础篇） - 知乎 (zhihu.com)

实现

#include <iostream>

// AVL树节点
struct AVLNode {
    int key;
    int height;
    AVLNode* left;
    AVLNode* right;

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

// 获取节点的高度
int getHeight(AVLNode* node) {
    if (node == nullptr)
        return 0;
    return node->height;
}

// 获取节点的平衡因子
int getBalanceFactor(AVLNode* node) {
    if (node == nullptr)
        return 0;
    return getHeight(node->left) - getHeight(node->right);
}

// 更新节点的高度
void updateHeight(AVLNode* node) {
    int leftHeight = getHeight(node->left);
    int rightHeight = getHeight(node->right);
    node->height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

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

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

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

    return x;
}

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

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

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

    return y;
}

// 插入节点
AVLNode* insertNode(AVLNode* root, int key) {
    // 执行标准的BST插入
    if (root == nullptr)
        return new AVLNode(key);

    if (key < root->key)
        root->left = insertNode(root->left, key);
    else if (key > root->key)
        root->right = insertNode(root->right, key);
    else
        return root; // 不允许插入重复节点

    // 更新节点高度
    updateHeight(root);

    // 检查是否平衡
    int balanceFactor = getBalanceFactor(root);

    // 进行平衡调整
    // 左左情况
    if (balanceFactor > 1 && key < root->left->key)
        return rightRotate(root);

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

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

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

    return root;
}

// 中序遍历AVL树
void inorderTraversal(AVLNode* root) {
    if (root == nullptr)
        return;

    inorderTraversal(root->left);
    std::cout << root->key << " ";
    inorderTraversal(root->right);
}

// 测试代码
int main() {
    AVLNode* root = nullptr;

    root = insertNode(root, 10);
    root = insertNode(root, 20);
    root = insertNode(root, 30);
    root = insertNode(root, 40);
    root = insertNode(root, 50);
    root = insertNode(root, 25);

    std::cout << "中序遍历结果: ";
    inorderTraversal(root);
    std::cout << std::endl;

    return 0;
}

红黑树

B树

B+树

B-树