当前位置: 首页 > article >正文

数据结构之BST、AVL、红黑树、哈夫曼树与B族树

数据结构之BST、AVL、红黑树、哈夫曼树与B族树

  • 数据结构之BST、AVL、红黑树、哈夫曼树与B族树
    • 一、二叉搜索树(Binary Search Tree, BST)
      • 1. 什么是二叉搜索树?
        • 重要性质
      • 2. 二叉搜索树实现
        • 1. 节点结构定义
        • 2. 核心操作接口
        • 3. 插入算法实现
        • 4. 删除算法实现(重点)
        • 5. 时间复杂度对比
      • 3. 实战测试示例
        • 测试代码
        • 测试树结构变化
    • 二、平衡二叉搜索树(AVL)
      • 1、AVL树的诞生背景
      • 2、核心平衡机制
        • 1. 平衡因子(Balance Factor)
        • 2. 失衡检测流程
      • 3、旋转操作详解
        • **1. LL型失衡(单右旋)**
        • **2. RR型失衡(单左旋)**
        • **3. LR型失衡(先左旋后右旋)**
        • **4. RL型失衡(先右旋后左旋)**
      • 4、完整插入流程
      • 5、时间复杂度分析
      • 6、实战案例:实现AVL树
        • 1. AVL树节点结构
        • 2. 单右旋(LL型失衡)
        • 3. 单左旋(RR型失衡)
        • 4. 获取节点高度、平衡因子
        • 5. 插入操作
        • 6. 完整实例代码
          • 代码说明
            • 1. LL型失衡(左左失衡)- 右旋操作
            • 2. RR型失衡(右右失衡)- 左旋操作
            • 3. LR型失衡(左右失衡)- 先左旋子树再右旋
            • 4. RL型失衡(右左失衡)- 先右旋子树再左旋
          • 测试用例输出
      • 7、典型应用场景
    • 三、哈夫曼树(Huffman Tree)
      • 1. 哈夫曼树定义
      • 2. 哈夫曼树构建过程
      • 3. 树结构流程图
      • 5. 代码实现
      • 6. 关键特性总结
    • 四、红黑树(Red-Black Tree)
      • 1. 什么是红黑树
      • 2. 红黑树插入
      • 3. 红黑树删除
      • 4. 红黑树实现
        • 测试用例输出
        • 红黑树结构流程图
      • 5. 红黑树特性总结
    • 五、B,B+,B*树
      • 1. B树
      • 2. B+树
      • 3. B*树
      • 4. B树实现
      • 4. B树的C++实现

数据结构之BST、AVL、红黑树、哈夫曼树与B族树


一、二叉搜索树(Binary Search Tree, BST)


1. 什么是二叉搜索树?

二叉搜索树(Binary Search Tree,BST)是一种特殊的二叉树数据结构,其中每个节点的值都大于其左子树中的任何节点的值,且小于其右子树中的任何节点的值。它的特点使得在搜索、插入和删除操作上具有高效性。

二叉搜索树是一种具有以下特性的二叉树:

  • 有序性
    • 左子树所有节点值 < 根节点值
    • 右子树所有节点值 > 根节点值
  • 递归性:左右子树也必须是二叉搜索树
  • 中序遍历结果是有序序列
8
3
10
1
6
9
14
4
7
重要性质
特性说明
查找效率平均O(log n),最坏O(n)
插入顺序影响形态有序插入会退化成链表
动态维护有序性无需显式排序,自动维护
支持范围查询通过中序遍历实现

2. 二叉搜索树实现

1. 节点结构定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
2. 核心操作接口
class BST {
private:
    TreeNode* root;
    
    // 递归查找实现
    TreeNode* searchRec(TreeNode* node, int key) {
        if (!node || node->val == key) return node;
        return (key < node->val) ? searchRec(node->left, key) 
                                 : searchRec(node->right, key);
    }
    
public:
    BST() : root(nullptr) {}
    
    // 查找操作
    bool contains(int key) {
        return searchRec(root, key) != nullptr;
    }
    
    // 插入操作
    void insert(int key) {
        root = insertRec(root, key);
    }
    
    // 删除操作
    void remove(int key) {
        root = deleteRec(root, key);
    }
};
3. 插入算法实现
TreeNode* insertRec(TreeNode* node, int key) {
    if (!node) return new TreeNode(key);
    
    if (key < node->val) {
        node->left = insertRec(node->left, key);
    } else if (key > node->val) {
        node->right = insertRec(node->right, key);
    }
    return node;
}
4. 删除算法实现(重点)
TreeNode* deleteRec(TreeNode* root, int key) {
    if (!root) return nullptr;
    
    if (key < root->val) {
        root->left = deleteRec(root->left, key);
    } else if (key > root->val) {
        root->right = deleteRec(root->right, key);
    } else {
        // Case 1: 无左子树
        if (!root->left) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        }
        // Case 2: 无右子树
        else if (!root->right) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        }
        // Case 3: 左右子树均存在
        TreeNode* minNode = findMin(root->right);
        root->val = minNode->val;
        root->right = deleteRec(root->right, minNode->val);
    }
    return root;
}

// 辅助函数:查找子树最小值节点
TreeNode* findMin(TreeNode* node) {
    while (node && node->left) {
        node = node->left;
    }
    return node;
}
5. 时间复杂度对比
操作平均时间复杂度最坏时间复杂度
插入O(log n)O(n)
删除O(log n)O(n)
查找O(log n)O(n)

3. 实战测试示例

测试代码
int main() {
    BST tree;
    
    // 插入测试
    vector<int> nums = {8, 3, 10, 1, 6, 14, 4, 7, 13};
    for (int num : nums) tree.insert(num);
    
    // 查找测试
    cout << "Contains 7: " << boolalpha << tree.contains(7) << endl;  // true
    cout << "Contains 5: " << boolalpha << tree.contains(5) << endl;  // false
    
    // 删除测试
    tree.remove(6);
    cout << "After delete 6, contains 6: " << tree.contains(6) << endl; // false
    cout << "Now contains 4: " << tree.contains(4) << endl; // true
    
    return 0;
}
测试树结构变化
删除前:
        8
      /   \
     3     10
    / \     \
   1   6     14
      / \   /
     4  7 13

删除6后:
        8
      /   \
     3     10
    / \     \
   1   7     14
      /     /
     4     13

二、平衡二叉搜索树(AVL)

1、AVL树的诞生背景

核心问题:二叉搜索树在极端情况下会退化为链表结构,导致操作时间复杂度退化为O(n)

解决方案
1962年由Adelson-Velsky和Landis提出,通过动态平衡机制确保树的高度始终保持在O(log n)级别


2、核心平衡机制

1. 平衡因子(Balance Factor)
  • 定义BF(node) = height(left) - height(right)
  • 平衡条件:所有节点的平衡因子绝对值必须 ≤ 1
2. 失衡检测流程
BF > 1
BF < -1
插入/删除节点
向上回溯路径
检查BF值
左子树过高
右子树过高
执行旋转调整

3、旋转操作详解

1. LL型失衡(单右旋)

结构特征

  • 新节点插入在左子树的左子树
  • 失衡节点的平衡因子为 +2,其左子节点的平衡因子为 +1

文字示意图

    A (BF=+2)       → 右旋 →      B
   /                             / \
  B (BF=+1)                     C   A
 /
C (新插入节点)

操作步骤

  1. 将失衡节点 A 的左子节点 B 提升为新根
  2. 原根节点 A 成为 B 的右子节点
  3. B 的原有右子树(如果有)变为 A 的左子树

2. RR型失衡(单左旋)

结构特征

  • 新节点插入在右子树的右子树
  • 失衡节点的平衡因子为 -2,其右子节点的平衡因子为 -1

文字示意图

A (BF=-2)           → 左旋 →      B
 \                               / \
  B (BF=-1)                     A   C
   \
    C (新插入节点)

操作要点

  • 镜像操作与 LL 型相反
  • 注意右子树可能存在的左子树需要重新挂载

3. LR型失衡(先左旋后右旋)

结构特征

  • 新节点插入在左子树的右子树
  • 失衡节点的平衡因子为 +2,其左子节点的平衡因子为 -1

文字示意图

     A (BF=+2)       → 对 B 左旋 →   A (BF=+2)    → 对 A 右旋 →    C
    /                               /                            / \
   B (BF=-1)                       C                            B   A
    \                             /
     C (新插入节点)              B

关键步骤

  1. 先对失衡节点的左子节点 B 执行左旋(转换为 LL 型)
  2. 再对根节点 A 执行右旋

4. RL型失衡(先右旋后左旋)

结构特征

  • 新节点插入在右子树的左子树
  • 失衡节点的平衡因子为 -2,其右子节点的平衡因子为 +1

文字示意图

A (BF=-2)           → 对 B 右旋 →   A (BF=-2)    → 对 A 左旋 →     C
 \                                   \                           / \
  B (BF=+1)                           C                         A   B
 /                                     \
C (新插入节点)                           B

操作要点

  1. 先对失衡节点的右子节点 B 执行右旋(转换为 RR 型)
  2. 再对根节点 A 执行左旋

4、完整插入流程

BF>1
BF<-1
LL型
LR型
RR型
RL型
插入新节点
标准BST插入
更新路径节点高度
回溯检查平衡因子
检查左子树结构
检查右子树结构
执行右旋
执行左右双旋
执行左旋
执行右左双旋

5、时间复杂度分析

操作时间复杂度说明
查找O(log n)严格平衡保证树高
插入O(log n)最多两次旋转操作
删除O(log n)可能传播旋转到根节点
空间复杂度O(n)每个节点需存储高度/平衡因子

6、实战案例:实现AVL树

1. AVL树节点结构
struct AVLNode {
    int val;
    AVLNode* left;
    AVLNode* right;
    int height;  // 新增高度字段
    
    AVLNode(int x) : val(x), left(nullptr), right(nullptr), height(1) {}
};
2. 单右旋(LL型失衡)
AVLNode* rightRotate(AVLNode* y) {
    AVLNode* x = y->left;
    AVLNode* T2 = x->right;

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

    // 更新高度
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    return x; // 返回新的根节点
}
3. 单左旋(RR型失衡)
AVLNode* leftRotate(AVLNode* x) {
    AVLNode* y = x->right;
    AVLNode* T2 = y->left;

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

    // 更新高度
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    return y; // 返回新的根节点
}
4. 获取节点高度、平衡因子
// 获取节点高度
int height(AVLNode* node) {
    return node ? node->height : 0;
}

// 获取平衡因子
int getBalance(AVLNode* node) {
    return node ? height(node->left) - height(node->right) : 0;
}
5. 插入操作
AVLNode* insert(AVLNode* node, int key) 
{
    // 标准BST插入
    if (!node) return new AVLNode(key);
    
    if (key < node->val)
        node->left = insert(node->left, key);
    else if (key > node->val)
        node->right = insert(node->right, key);
    else 
        return node; // 不允许重复值

    // 更新高度
    node->height = 1 + max(height(node->left), height(node->right));
    
    // 获取平衡因子
    int balance = getBalance(node);
    
    // LL型失衡
    if (balance > 1 && key < node->left->val)
        return rightRotate(node);
    
    // RR型失衡
    if (balance < -1 && key > node->right->val)
        return leftRotate(node);
    
    // LR型失衡
    if (balance > 1 && key > node->left->val) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
    
    // RL型失衡
    if (balance < -1 && key < node->right->val) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
    
    return node;
}
6. 完整实例代码

以下是完整的 AVL树C++实现,包含插入、删除、遍历等功能,并附带测试用例:

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

struct AVLNode {
    int val;
    AVLNode* left;
    AVLNode* right;
    int height;

    AVLNode(int x) : val(x), left(nullptr), right(nullptr), height(1) {}
};

class AVLTree {
private:
    AVLNode* root;

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

    // 计算平衡因子
    int getBalance(AVLNode* node) {
        return node ? height(node->left) - height(node->right) : 0;
    }

    // 单右旋(LL型)
    AVLNode* rightRotate(AVLNode* y) {
        AVLNode* x = y->left;
        AVLNode* T2 = x->right;

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

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

        return x;
    }

    // 单左旋(RR型)
    AVLNode* leftRotate(AVLNode* x) {
        AVLNode* y = x->right;
        AVLNode* T2 = y->left;

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

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

        return y;
    }

    // 查找最小节点
    AVLNode* minValueNode(AVLNode* node) {
        AVLNode* current = node;
        while (current->left)
            current = current->left;
        return current;
    }

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

    // 插入操作(外部接口)
    void insert(int val) {
        root = insert(root, val);
    }

    // 删除操作(外部接口)
    void remove(int val) {
        root = remove(root, val);
    }

    // 搜索功能
    bool search(int val) {
        return search(root, val);
    }

    // 中序遍历
    void inOrder() {
        inOrder(root);
        cout << endl;
    }

    // 前序遍历
    void preOrder() {
        preOrder(root);
        cout << endl;
    }

    // 层序遍历显示函数(用于验证树结构)
    void printLevelOrder() {
        if (!root) {
            cout << "空树" << endl;
            return;
        }

        queue<AVLNode*> q;
        q.push(root);

        while (!q.empty()) {
            int size = q.size();
            while (size--) {
                AVLNode* node = q.front();
                q.pop();
                cout << node->val << " "; 
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            cout << endl;
        }
    }

private:
    // 递归插入实现
    AVLNode* insert(AVLNode* node, int val) {
        if (!node) return new AVLNode(val);

        if (val < node->val)
            node->left = insert(node->left, val);
        else if (val > node->val)
            node->right = insert(node->right, val);
        else
            return node; // 不允许重复值

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

        // LL型失衡(直接右旋)
        if (balance > 1 && val < node->left->val)
            return rightRotate(node);

        // RR型失衡(直接左旋)
        if (balance < -1 && val > node->right->val)
            return leftRotate(node);

        // LR型失衡(先左旋左子树,再右旋当前节点)
        if (balance > 1 && val > node->left->val) {
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }

        // RL型失衡(先右旋右子树,再左旋当前节点)
        if (balance < -1 && val < node->right->val) {
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }

        return node;
    }


    // 递归删除实现
    AVLNode* remove(AVLNode* node, int val) {
        if (!node) return nullptr;

        // 1. 标准BST删除
        if (val < node->val) {
            node->left = remove(node->left, val);
        }
        else if (val > node->val) {
            node->right = remove(node->right, val);
        }
        else {
            // 找到要删除的节点
            if (!node->left || !node->right) {
                AVLNode* temp = node->left ? node->left : node->right;
                if (!temp) { // 无子节点情况
                    temp = node;
                    node = nullptr;
                }
                else { // 单子节点情况
                    delete node;
                    return temp; 
                }
                delete temp;
            }
            else { // 双子节点情况
                AVLNode* temp = minValueNode(node->right);
                node->val = temp->val;
                node->right = remove(node->right, temp->val);
            }
        }

        if (!node) return nullptr;
        // 2. 更新高度
        node->height = 1 + max(height(node->left), height(node->right));

        // 3. 检查平衡因子
        int balance = getBalance(node);

        // 4. 处理四种失衡情况(关键修改点)
        // 左左失衡
        if (balance > 1 && getBalance(node->left) >= 0)
            return rightRotate(node);

        // 左右失衡
        if (balance > 1 && getBalance(node->left) < 0) {
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }

        // 右右失衡
        if (balance < -1 && getBalance(node->right) <= 0)
            return leftRotate(node);

        // 右左失衡
        if (balance < -1 && getBalance(node->right) > 0) {
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }

        return node;
    }

    // 中序遍历实现
    void inOrder(AVLNode* node) {
        if (!node) return;
        inOrder(node->left);
        cout << node->val << " ";
        inOrder(node->right);
    }
    // 前序遍历实现
    void preOrder(AVLNode* node) {
        if (!node) return;
        cout << node->val << " ";
        preOrder(node->left);
        preOrder(node->right);
    }

    // 搜索功能实现
    bool search(AVLNode* node, int val) {
        if (!node) return false;
        if (val < node->val) return search(node->left, val);
        if (val > node->val) return search(node->right, val);
        return true;
    }

};

// 测试用例
void testAVLTree() {
    AVLTree tree;

    // LL型失衡测试
    cout << "LL型失衡测试:" << endl;
    int ll_test[] = { 30, 20, 10 };
    for (int num : ll_test) {
        tree.insert(num);
    }
    cout << "中序遍历结果: ";
    tree.inOrder();
    cout << "层序遍历结果: " << endl;
    tree.printLevelOrder();

    // 清空树
    tree = AVLTree();

    // RR型失衡测试
    cout << "\nRR型失衡测试:" << endl;
    int rr_test[] = { 10, 20, 30 };
    for (int num : rr_test) {
        tree.insert(num);
    }
    cout << "中序遍历结果: ";
    tree.inOrder();
    cout << "层序遍历结果: " << endl;
    tree.printLevelOrder();

    // 清空树
    tree = AVLTree();

    // LR型失衡测试
    cout << "\nLR型失衡测试:" << endl;
    int lr_test[] = { 30, 10, 20 };
    for (int num : lr_test) {
        tree.insert(num);
    }
    cout << "中序遍历结果: ";
    tree.inOrder();
    cout << "层序遍历结果: " << endl;
    tree.printLevelOrder();

    // 清空树
    tree = AVLTree();

    // RL型失衡测试
    cout << "\nRL型失衡测试:" << endl;
    int rl_test[] = { 10, 30, 20 };
    for (int num : rl_test) {
        tree.insert(num);
    }
    cout << "中序遍历结果: ";
    tree.inOrder();
    cout << "层序遍历结果: " << endl;
    tree.printLevelOrder();
}

int main() {
    testAVLTree();
    return 0;
}
代码说明
1. LL型失衡(左左失衡)- 右旋操作

插入序列: 30, 20, 10

插入30: 
   30

插入20:
   30
  /
20

插入10后(失衡):       右旋后:
      30             20
     /              /  \
   20      →      10    30
   /
 10
2. RR型失衡(右右失衡)- 左旋操作

插入序列: 10, 20, 30

插入10:
10

插入20:
  10
    \
     20

插入30后(失衡):       左旋后:
  10                  20
    \                /  \
     20      →     10    30
       \
        30
3. LR型失衡(左右失衡)- 先左旋子树再右旋

插入序列: 30, 10, 20

插入30:
   30

插入10:
   30
  /
10

插入20后(失衡):      左旋子树后:        右旋根节点后:
      30                30                 20
     /                 /                  /  \
   10        →       20         →       10    30
     \               /
      20           10
4. RL型失衡(右左失衡)- 先右旋子树再左旋

插入序列: 10, 30, 20

插入10:
10

插入30:
  10
    \
     30

插入20后(失衡):      右旋子树后:        左旋根节点后:
  10                  10                  20
    \                  \                 /  \
     30       →         20      →      10    30
    /                     \
   20                      30
测试用例输出
LL型失衡测试:
中序遍历结果: 10 20 30 
层序遍历结果: 
20 
10 30 

RR型失衡测试:
中序遍历结果: 10 20 30 
层序遍历结果: 
20 
10 30 

LR型失衡测试:
中序遍历结果: 10 20 30 
层序遍历结果: 
20 
10 30 

RL型失衡测试:
中序遍历结果: 10 20 30 
层序遍历结果: 
20 
10 30 

7、典型应用场景

  1. 数据库索引:MySQL的MEMORY存储引擎
  2. 文件系统:Windows NT内核的地址空间管理
  3. 内存受限系统:嵌入式设备的快速查询
  4. 3D图形计算:场景图的空间划分管理

三、哈夫曼树(Huffman Tree)


1. 哈夫曼树定义

哈夫曼树(Huffman Tree),又称最优二叉树,是一种带权路径长度(WPL, Weighted Path Length)最短的二叉树。

其特点是:

  • 带权路径最小:叶子节点的权值(如字符频率)乘以路径长度(根到叶子的边数)的总和最小。

  • 应用场景:广泛用于数据压缩,如哈夫曼编码,通过为高频字符分配短编码、低频字符分配长编码,减少整体数据量。

  • 核心特性:权重越大的叶子节点距离根节点越近。

  • 核心应用:数据压缩(哈夫曼编码)、文件编码、加密算法等。


2. 哈夫曼树构建过程

以权值集合 {5, 9, 12, 13, 16, 45} 为例:

  1. 初始化森林

    将每个权值视为独立的单节点树,组成森林:
    [5], [9], [12], [13], [16], [45]

  2. 合并最小两子树

    • 第1次合并:选择最小权值 59,生成父节点 14
      森林更新:[14], [12], [13], [16], [45]
    • 第2次合并:选择 1213,生成父节点 25
      森林更新:[14], [16], [25], [45]
    • 第3次合并:选择 1416,生成父节点 30
      森林更新:[25], [30], [45]
    • 第4次合并:选择 2530,生成父节点 55
      森林更新:[45], [55]
    • 第5次合并:合并 4555,生成父节点 100
      最终得到哈夫曼树,根节点权值为 100
  3. 验证特性

    • WPL计算(5+9)*3 + (12+13+16)*2 + 45*1 = 146
    • 权重越大越靠近根:最大权值 45 直接作为根的子节点。

3. 树结构流程图

5
9
12
13
14
16
25
30
45
55
100

流程图说明:

  1. 根节点权值为 100(所有原始权值之和:5+9+12+13+16+45)。
  2. 叶子节点为原始权值,内部节点为合并生成的权值。
  3. 路径关系:父节点到子节点的连接体现合并顺序。

5. 代码实现

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 哈夫曼树节点定义
struct HuffmanNode {
    int weight;
    HuffmanNode *left, *right;
    HuffmanNode(int w) : weight(w), left(nullptr), right(nullptr) {}
};

// 优先队列比较规则(最小堆)
struct Compare {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->weight > b->weight;
    }
};

// 构建哈夫曼树函数
HuffmanNode* buildHuffmanTree(vector<int>& weights) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> minHeap;

    // 初始化所有单节点树
    for (int w : weights) {
        minHeap.push(new HuffmanNode(w));
    }

    // 循环合并最小两树
    while (minHeap.size() > 1) {
        HuffmanNode* left = minHeap.top();
        minHeap.pop();
        HuffmanNode* right = minHeap.top();
        minHeap.pop();

        HuffmanNode* parent = new HuffmanNode(left->weight + right->weight);
        parent->left = left;
        parent->right = right;
        minHeap.push(parent);
    }

    return minHeap.empty() ? nullptr : minHeap.top();
}

// 辅助函数:打印先序遍历结果
void printHuffmanTree(HuffmanNode* root) {
    if (!root) return;
    cout << root->weight << " ";
    printHuffmanTree(root->left);
    printHuffmanTree(root->right);
}

int main() {
    vector<int> weights = {5, 9, 12, 13, 16, 45};
    HuffmanNode* root = buildHuffmanTree(weights);
    cout << "哈夫曼树先序遍历(权值):";
    printHuffmanTree(root);  // 输出示例:100 45 55 25 12 13 30 14 5 9 16
    return 0;
}

6. 关键特性总结

特性说明
时间复杂度O(n log n),优先队列操作主导
空间复杂度O(n),存储所有节点
唯一性同一权值集合可能有不同形态的哈夫曼树,但WPL一定最小
验证方法根节点权值等于初始权值总和,且权重大的节点靠近根


四、红黑树(Red-Black Tree)


1. 什么是红黑树

红黑树是一种自平衡的二叉搜索树(BST),通过颜色属性维护树的平衡性,确保插入、删除、查找的最坏时间复杂度为 O(log n)

核心性质:

  1. 颜色属性:每个节点是红色或黑色。
  2. 根节点:根节点必须为黑色。
  3. 叶子节点:所有叶子(NIL节点,空节点)为黑色。
  4. 红色节点规则:红色节点的子节点必须为黑色(即不能有连续红色节点)。
  5. 黑高一致:从任意节点到其所有叶子节点的路径上,黑色节点的数量相同。

2. 红黑树插入

插入新节点时默认设为红色(避免破坏黑高),可能违反红黑树规则,需通过旋转和颜色调整修复。

插入步骤:

  1. 标准BST插入:按二叉搜索树规则插入节点,颜色设为红色。
  2. 颜色修复
    • Case 1:父节点是黑色 → 无需调整。
    • Case 2:父节点是红色 → 需要进一步判断叔叔节点颜色:
      • 叔叔为红色:父和叔变黑,祖父变红,递归处理祖父节点。
      • 叔叔为黑色或NIL
        • LL/RR型:单旋转(父节点上升,祖父下沉)。
        • LR/RL型:双旋转(先子节点旋转,再父节点旋转)。

示例(插入后修复连续红色冲突):

G:黑
P:红
U:红
新节点:红

修复操作:将P和U变黑,G变红,然后以G为起点继续检查。


3. 红黑树删除

删除节点可能导致黑高被破坏,需通过旋转和颜色调整修复。

删除步骤:

  1. 标准BST删除:找到待删除节点,若有两个子节点则用后继节点替代。
  2. 颜色修复
    • 若删除节点是红色 → 直接删除,无需调整。
    • 若删除节点是黑色 → 需从兄弟节点“借”黑色或调整颜色。

修复策略(设当前节点为N,父为P,兄弟为S):

  • Case 1:S为红色 → 旋转使S变黑,转化为其他情况。
  • Case 2:S为黑色,且S的子节点均为黑色 → S变红,N上移至P递归处理。
  • Case 3:S为黑色,且S的远子节点为红色 → 旋转并重新着色,恢复平衡。
  • Case 4:S为黑色,且S的近子节点为红色 → 旋转调整,转为Case 3。

示例(删除黑色节点后的修复):

P:黑
N:黑
S:红
SL:黑
SR:黑

修复操作:旋转使S成为新的父节点,并调整颜色。


4. 红黑树实现

#include <iostream>
using namespace std;

enum Color { RED, BLACK };

struct Node {
    int val;
    Color color;
    Node* left, * right, * parent;
    Node(int v) : val(v), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};

class RedBlackTree {
private:
    Node* root;
    Node* nil; // 哨兵节点(代表NIL叶子节点)

    // 初始化哨兵节点
    void initializeNil() {
        nil = new Node(0);
        nil->color = BLACK;
        nil->left = nil->right = nil->parent = nullptr;
    }

    // 左旋
    void leftRotate(Node* x) {
        Node* y = x->right;
        x->right = y->left;
        if (y->left != nil) y->left->parent = x;
        y->parent = x->parent;
        if (x->parent == nil) {
            root = y;
        }
        else if (x == x->parent->left) {
            x->parent->left = y;
        }
        else {
            x->parent->right = y;
        }
        y->left = x;
        x->parent = y;
    }

    // 右旋
    void rightRotate(Node* x) {
        Node* y = x->left;
        x->left = y->right;
        if (y->right != nil) y->right->parent = x;
        y->parent = x->parent;
        if (x->parent == nil) {
            root = y;
        }
        else if (x == x->parent->right) {
            x->parent->right = y;
        }
        else {
            x->parent->left = y;
        }
        y->right = x;
        x->parent = y;
    }

    // 插入修复
    void fixInsert(Node* z) {
        while (z->parent->color == RED) {
            if (z->parent == z->parent->parent->left) { // 父节点是左孩子
                Node* y = z->parent->parent->right; // 叔叔节点
                if (y->color == RED) { // Case 1: 叔叔为红
                    z->parent->color = BLACK;
                    y->color = BLACK;
                    z->parent->parent->color = RED;
                    z = z->parent->parent;
                }
                else {
                    if (z == z->parent->right) { // Case 2: z是右孩子,转Case3
                        z = z->parent;
                        leftRotate(z);
                    }
                    // Case 3: z是左孩子
                    z->parent->color = BLACK;
                    z->parent->parent->color = RED;
                    rightRotate(z->parent->parent);
                }
            }
            else { // 对称处理父节点是右孩子的情况
                Node* y = z->parent->parent->left;
                if (y->color == RED) {
                    z->parent->color = BLACK;
                    y->color = BLACK;
                    z->parent->parent->color = RED;
                    z = z->parent->parent;
                }
                else {
                    if (z == z->parent->left) {
                        z = z->parent;
                        rightRotate(z);
                    }
                    z->parent->color = BLACK;
                    z->parent->parent->color = RED;
                    leftRotate(z->parent->parent);
                }
            }
        }
        root->color = BLACK;
    }

    // 删除修复
    void fixDelete(Node* x) {
        while (x != root && x->color == BLACK) {
            if (x == x->parent->left) {
                Node* w = x->parent->right; // 兄弟节点
                if (w->color == RED) { // Case 1: 兄弟为红
                    w->color = BLACK;
                    x->parent->color = RED;
                    leftRotate(x->parent);
                    w = x->parent->right;
                }
                if (w->left->color == BLACK && w->right->color == BLACK) { // Case 2
                    w->color = RED;
                    x = x->parent;
                }
                else {
                    if (w->right->color == BLACK) { // Case 3: 兄弟的右子为黑
                        w->left->color = BLACK;
                        w->color = RED;
                        rightRotate(w);
                        w = x->parent->right;
                    }
                    // Case 4: 兄弟的右子为红
                    w->color = x->parent->color;
                    x->parent->color = BLACK;
                    w->right->color = BLACK;
                    leftRotate(x->parent);
                    x = root;
                }
            }
            else { // 对称处理x是右孩子的情况
                Node* w = x->parent->left;
                if (w->color == RED) {
                    w->color = BLACK;
                    x->parent->color = RED;
                    rightRotate(x->parent);
                    w = x->parent->left;
                }
                if (w->right->color == BLACK && w->left->color == BLACK) {
                    w->color = RED;
                    x = x->parent;
                }
                else {
                    if (w->left->color == BLACK) {
                        w->right->color = BLACK;
                        w->color = RED;
                        leftRotate(w);
                        w = x->parent->left;
                    }
                    w->color = x->parent->color;
                    x->parent->color = BLACK;
                    w->left->color = BLACK;
                    rightRotate(x->parent);
                    x = root;
                }
            }
        }
        x->color = BLACK;
    }

    // 辅助函数:用v替换u的父节点连接
    void transplant(Node* u, Node* v) {
        if (u->parent == nil) {
            root = v;
        }
        else if (u == u->parent->left) {
            u->parent->left = v;
        }
        else {
            u->parent->right = v;
        }
        v->parent = u->parent;
    }

    // 找到最小节点
    Node* minimum(Node* node) {
        while (node->left != nil) {
            node = node->left;
        }
        return node;
    }

public:
    RedBlackTree() {
        initializeNil();
        root = nil;
    }

    // 查找节点
    Node* search(int val) {
        Node* current = root;
        while (current != nil) {
            if (val == current->val) return current;
            else if (val < current->val) current = current->left;
            else current = current->right;
        }
        return nil;
    }

    // 插入节点
    void insert(int val) {
        Node* z = new Node(val);
        Node* y = nil;
        Node* x = root;
        while (x != nil) {
            y = x;
            if (z->val < x->val) x = x->left;
            else x = x->right;
        }
        z->parent = y;
        if (y == nil) {
            root = z;
        }
        else if (z->val < y->val) {
            y->left = z;
        }
        else {
            y->right = z;
        }
        z->left = z->right = nil;
        z->color = RED;
        fixInsert(z);
    }

    // 删除节点
    void deleteNode(int val) {
        Node* z = search(val);
        if (z == nil) return;

        Node* y = z;
        Color yOriginalColor = y->color;
        Node* x;

        if (z->left == nil) {
            x = z->right;
            transplant(z, z->right);
        }
        else if (z->right == nil) {
            x = z->left;
            transplant(z, z->left);
        }
        else {
            y = minimum(z->right);
            yOriginalColor = y->color;
            x = y->right;
            if (y->parent == z) {
                x->parent = y;
            }
            else {
                transplant(y, y->right);
                y->right = z->right;
                y->right->parent = y;
            }
            transplant(z, y);
            y->left = z->left;
            y->left->parent = y;
            y->color = z->color;
        }
        delete z;
        if (yOriginalColor == BLACK) {
            fixDelete(x);
        }
    }

    // 中序遍历(测试用)
    void inorder(Node* node) {
        if (node != nil) {
            inorder(node->left);
            cout << node->val << "(" << (node->color == RED ? "R" : "B") << ") ";
            inorder(node->right);
        }
    }

    void printTree() {
        inorder(root);
        cout << endl;
    }
};

// 测试代码
int main() {
    RedBlackTree rbt;
    rbt.insert(10);
    rbt.insert(20);
    rbt.insert(5);
    rbt.insert(15);
    rbt.insert(25);
    cout << "插入后: ";
    rbt.printTree();

    rbt.deleteNode(15);
    cout << "删除15后: ";
    rbt.printTree();

    rbt.deleteNode(10);
    cout << "删除10后: ";
    rbt.printTree();

    return 0;
} 
测试用例输出
插入后: 5(B) 10(B) 15(R) 20(B) 25(R)
删除15后: 5(B) 10(B) 20(B) 25(R)
删除10后: 5(B) 20(B) 25(B)

红黑树结构流程图
  1. 插入操作后(10,20,5,15,25)
        10(B)
       /     \
    5(B)     20(B)
           /     \
        15(R)   25(R)
  • 根节点:10(黑色)
  • 20的左子节点:15(红色)
  • 20的右子节点:25(红色)
  • 所有叶子节点(nil)均为黑色

  1. 删除15(红色叶子节点)后
        10(B)
       /     \
    5(B)     20(B)
               \
               25(R)
  • 15被删除,20的右子树仅剩25(红色)
  • 无需调整颜色/旋转(删除红色节点不破坏性质)

  1. 删除10(根节点)后
        20(B)
       /     \
    5(B)     25(B)
  • 根节点替换为20,颜色保持原黑色
  • 5和25调整为黑色(保持黑高平衡)

5. 红黑树特性总结

特性说明
平衡性通过颜色和旋转规则保证树高近似 log n,避免BST退化成链表
时间复杂度插入、删除、查找均为 O(log n)
应用场景C++ STL的map/set,Java的TreeMap,数据库索引等
与AVL树对比红黑树插入/删除更快(旋转次数少),AVL查询更快(更严格平衡)

五、B,B+,B*树

B树族核心概念对比

特性B树B+树B*树
数据存储位置所有节点存储数据仅叶子节点存储数据仅叶子节点存储数据
叶子节点链接有双向链表连接所有叶子节点有双向链表连接所有叶子节点
非叶节点键数量m/2 ≤ keys ≤ mm/2 ≤ keys ≤ m(2m-1)/3 ≤ keys ≤ m
节点分裂策略直接分裂分裂时向兄弟节点借数据分裂时与兄弟节点共享数据
空间利用率约50%约50%约66%
适用场景文件系统数据库索引高并发数据库系统
B*树
子节点1
非叶节点
键数下限更高
子节点2
叶子节点
存储数据
共享键区域
B+树
子节点1
非叶节点
仅存储键
子节点2
叶子节点
存储数据
双向链表连接
叶子节点
存储数据
双向链表连接
B树
子节点1
非叶节点
存储键和数据
子节点2
数据块
数据块

1. B树

B树(B-Tree) 是一种自平衡的多路搜索树,广泛应用于数据库和文件系统。其核心特性如下:

非叶节点
键: 20, 40
数据: D1, D2
子节点
键: 10,15
数据: D3,D4
子节点
键: 25,30
数据: D5,D6
子节点
键: 50,60
数据: D7,D8
  • 阶数:B树的阶数 m 表示每个节点最多拥有 m 个子节点。
  • 键数量:每个节点最多包含:m - 1 个键,最少包含 ⌈m/2⌉ - 1 个键(根节点除外)。
  • 平衡性:所有叶子节点位于同一层,保证查询效率稳定。
  • 操作:插入和删除可能引发节点分裂或合并,通过递归调整保持平衡。

2. B+树

B+树 是B树的变体,优化了范围查询:

双向链表
双向链表
非叶节点
键: 20, 40
叶子节点
键: 10,15,20
数据: D1,D2,D3
叶子节点
键: 25,30,40
数据: D4,D5,D6
叶子节点
键: 50,60,70
数据: D7,D8,D9
  • 数据存储:所有数据仅存于叶子节点,内部节点仅存键和子节点指针。
  • 链表连接:叶子节点通过指针形成有序链表,便于遍历区间数据。
  • 查询特性:查询必须到叶子节点,但内部节点更紧凑,树高更低。

3. B*树

B*树 进一步优化空间利用率:

共享键
共享键
节点A
键: 10,20,30
子节点B
子节点C
新节点D
  • 节点分裂策略:节点满时,优先将部分键转移至兄弟节点,延迟分裂。
  • 填充率:节点最小键数从 ⌈m/2⌉ 提高至 ⌈2m/3⌉,减少空间浪费。

4. B树实现

4. B树的C++实现

以下为简化版B树实现(仅插入和查找):

#include <iostream>
using namespace std;

class BTree {
private:
    struct Node {
        int *keys;
        Node **children;
        int num_keys;
        bool is_leaf;
        int t;  // 最小度数

        Node(int degree, bool leaf) : t(degree), is_leaf(leaf), num_keys(0) {
            keys = new int[2 * t - 1];
            children = new Node*[2 * t]();
        }

        ~Node() {
            delete[] keys;
            for (int i = 0; i <= 2 * t; ++i) delete children[i];
            delete[] children;
        }
    };

    Node *root;
    int t;  // 最小度数

    void splitChild(Node *parent, int idx) {
        Node *fullChild = parent->children[idx];
        Node *newChild = new Node(t, fullChild->is_leaf);
        newChild->num_keys = t - 1;

        // 复制后t-1个键和子节点
        for (int i = 0; i < t - 1; ++i)
            newChild->keys[i] = fullChild->keys[i + t];
        if (!fullChild->is_leaf)
            for (int i = 0; i < t; ++i)
                newChild->children[i] = fullChild->children[i + t];

        fullChild->num_keys = t - 1;

        // 调整父节点
        for (int i = parent->num_keys; i > idx; --i)
            parent->keys[i] = parent->keys[i - 1];
        for (int i = parent->num_keys + 1; i > idx + 1; --i)
            parent->children[i] = parent->children[i - 1];

        parent->keys[idx] = fullChild->keys[t - 1];
        parent->children[idx + 1] = newChild;
        parent->num_keys++;
    }

    void insertNonFull(Node *node, int key) {
        int i = node->num_keys - 1;
        if (node->is_leaf) {
            while (i >= 0 && key < node->keys[i]) {
                node->keys[i + 1] = node->keys[i];
                i--;
            }
            node->keys[i + 1] = key;
            node->num_keys++;
        } else {
            while (i >= 0 && key < node->keys[i]) i--;
            i++;
            if (node->children[i]->num_keys == 2 * t - 1) {
                splitChild(node, i);
                if (key > node->keys[i]) i++;
            }
            insertNonFull(node->children[i], key);
        }
    }

public:
    BTree(int degree) : t(degree), root(nullptr) {}

    void insert(int key) {
        if (!root) {
            root = new Node(t, true);
            root->keys[0] = key;
            root->num_keys = 1;
        } else {
            if (root->num_keys == 2 * t - 1) {
                Node *newRoot = new Node(t, false);
                newRoot->children[0] = root;
                splitChild(newRoot, 0);
                root = newRoot;
            }
            insertNonFull(root, key);
        }
    }

    bool search(int key) {
        return search(root, key);
    }

    bool search(Node *node, int key) {
        if (!node) return false;
        int i = 0;
        while (i < node->num_keys && key > node->keys[i]) i++;
        if (i < node->num_keys && key == node->keys[i]) return true;
        return node->is_leaf ? false : search(node->children[i], key);
    }
};

int main() {
    BTree t(3); // 最小度数t=3
    t.insert(10);
    t.insert(20);
    t.insert(5);
    t.insert(6);
    t.insert(12);
    cout << (t.search(6) ? "Found" : "Not Found") << endl; // Found
    cout << (t.search(15) ? "Found" : "Not Found") << endl; // Not Found
    return 0;
}

代码解析

  • 节点结构:每个节点包含键数组、子节点指针数组、键数量及叶子标记。
  • 插入逻辑:根节点满时先分裂,确保插入始终从非满节点开始。
  • 分裂操作:满子节点分裂为二,中间键提升至父节点。
  • 查找逻辑:递归遍历节点,逐层比较键值。

http://www.kler.cn/a/551553.html

相关文章:

  • leetcode:942. 增减字符串匹配(python3解法)
  • 23种设计模式 - 装饰器模式
  • 深度解析——Vue与React的核心差异
  • 解锁观察者模式:Java编程中的高效事件管理之道
  • FBD电插锁硬件,如何通过C++ 控制低电压高低电压实现控制开关锁,通过磁吸检查是否开门操作
  • 单纯禁用Cookie能否保证隐私安全?
  • 探秘 DeepSeek R1 模型:跨越多领域的科技奇迹,引领智能应用新浪潮
  • 视觉相关问题总结
  • 地表放置机场和飞机(十)
  • 深入内存调试:Valgrind工具的终极指南(转)
  • Oracle Rac 多路径链路不稳定引发IO降速-光弱
  • 关于使用雪花算法生成唯一ID,返回给前端ID不一致的问题
  • 内容中台重构企业内容管理流程驱动智能协作升级
  • 个人系统架构技术分享
  • 沃丰科技大模型标杆案例 | 索尼大模型智能营销机器人建设实践
  • 【笔记】LLM|Ubuntu22服务器极简本地部署DeepSeek+API使用方式
  • ubuntu下载和编译Android源码
  • SOME/IP--协议英文原文讲解6
  • UE5控件组件显示UMG文本不正常
  • 【Python项目】文件销毁工具文档