【数据结构c++】（学习笔记）AVL树（二叉平衡树）与哈夫曼树

定义：满足BST树性质的同时，具有平衡性质（任意节点左右子树的高度差不超过1）

SlashYe

997人浏览 · 2025-11-01 16:19:24

SlashYe · 2025-11-01 16:19:24 发布

AVL树（二叉平衡搜索树）

基本概念

定义：满足BST树性质的同时，具有平衡性质（任意节点左右子树的高度差不超过1）

AVL树的旋转操作

为了维持AVL树平衡的特性，其拥有一种独特的操作：旋转

本文基于以下四种情况进行讨论：

1. 左孩子的左子树过高

操作：右旋 `rightRotate(node)

在这里插入图片描述
操作步骤：

// 1.初始化 child
child = node->left;
// 2.处理 child 的右孩子
node->left = child->right;
// 3.把 node 转下去
child->right = node;

// 需要更新 node 和 child 的高度值
// 先更新 node 的高度（因为从下往上计算）
node->height_ = max(height(node->left_),height(node->right_)) + 1;
child->height_ = max(height(child->left_),height(child->right_)) + 1;

// 返回子节点
return child;

2. 右孩子的右子树过高

操作：左旋 leftRotate(node)
在这里插入图片描述
操作步骤：

// 1.初始化 child
child  = node->right;
// 2.处理 child 的左孩子
node->right = child->left;
// 3.把 node 转下去
child->left = node;

// 需要更新 node 和 child 的高度值
// 先更新 node 的高度（因为从下往上计算）
node->height_ = max(height(node->left_),height(node->right_)) + 1;
child->height_ = max(height(child->left_),height(child->right_)) + 1;

// 返回子节点
return child;

3. 左孩子的右子树过高

操作：左-右旋（左平衡） leftBalance(node)

在这里插入图片描述

操作步骤：

调用1,2两种旋转，先以20(child)为轴左旋，再以40(node)为轴右旋

node->left_ = leftRotate(node->left_);
return rightRotate(node);

4. 右孩子的左子树过高

操作：右-左旋（右平衡） rightBalance(node)

在这里插入图片描述
操作步骤：

调用1,2两种旋转，先以60(child)为轴右旋，再以40(node)为轴左旋

node->left_ = rightRotate(node->left_);
return leftRotate(node);

基本操作

插入

在BST树插入操作的基础上，添加判定代码

左子树过高
右子树过高
更新节点高度

代码实现：

public:
	// 插入公有接口
    void insert(const T &val)
    {
        root_ = insert(root_, val);
    }

private:
	// 插入私有接口
    Node *insert(Node *node, const T &val)
    {
        if (node == nullptr)
        {
            return new Node(val);
        }

        if (node->data_ > val)
        {
            node->left_ = insert(node->left_, val);

            // 朝左子树添加节点后，左子树过高
            if (height(node->left_) - height(node->right_) > 1)
            {
                // 左孩子的左子树过高
                if (height(node->left_->left_) >= height(node->left_->right_)) // 取等
                {
                    node = rightRotate(node);
                }
                // 左孩子的左子树过高
                else
                {
                    node = leftBalance(node);
                }
            }
        }
        else if (node->data_ < val)
        {
            node->right_ = insert(node->right_, val);

            // 朝右子树添加节点后，右子树过高
            if (height(node->right_) - height(node->left_) > 1)
            {
                // 右孩子的右子树过高
                if (height(node->right_->right_) >= height(node->right_->left_)) // 取等
                {
                    node = leftRotate(node);
                }
                // 右孩子的右子树过高
                else
                {
                    node = rightBalance(node);
                }
            }
        }

        // 更新父节点高度（所有祖先节点在此回溯，重新计算高度）
        // 例如 node 的父节点，没有被调用旋转函数，高度要手动更新
        node->height_ = max(height(node->left_), height(node->right_)) + 1;

        return node;
    }

测试用例：

由1到10构成的AVL树
在这里插入图片描述

代码实现：

int main()
{
    AVLTree<int> avl;

    for (int i = 1; i <= 10; i++)
    {
        avl.insert(i);
    }

    avl.print_levelOrder();

    return 0;
}

注：print_levelOrder()与层序遍历非递归实现代码几乎一模一样，故不再介绍

输出结果：

层序遍历打印：4 2 8 1 3 6 9 5 7 10

删除

在BST删除的递归实现代码的基础上，增加以下内容：

有两个孩子的节点，删除时判断高度，避免不平衡
删完子树回溯时调整平衡
更新节点高度

代码实现：

public:
	// 删除（公有）
    void remove(const T &val)
    {
        root_ = remove(root_, val);
    }

private:
	// 删除（私有）
    Node *remove(Node *node, const T &val)
    {
        if (node == nullptr)
        {
            return nullptr;
        }

        if (node->data_ > val)
        {
            node->left_ = remove(node->left_, val);
            // 左子树删除节点，导致右子树过高
            if (height(node->right_) - height(node->left_) > 1)
            {
                // 右孩子的右子树过高
                if (height(node->right_->right_) >= height(node->right_->left_)) // 取等
                {
                    node = leftRotate(node);
                }
                // 右孩子的右子树过高
                else
                {
                    node = rightBalance(node);
                }
            }
        }
        else if (node->data_ < val)
        {
            node->right_ = remove(node->right_, val);
            // 右子树删除节点，导致左子树过高
            if (height(node->left_) - height(node->right_) > 1)
            {
                // 左孩子的左子树过高
                if (height(node->left_->left_) >= height(node->left_->right_)) // 取等
                {
                    node = rightRotate(node);
                }
                // 左孩子的左子树过高
                else
                {
                    node = leftBalance(node);
                }
            }
        }
        else // 找到了
        {
            if (node->left_ != nullptr && node->right_ != nullptr)
            {
                // 为了避免删除前驱或后继造成节点失衡
                // 我们选择谁高删除谁
                if (height(node->left_) >= height(node->right_))
                {
                    // 删除前驱节点
                    Node *pre = node->left_;
                    while (pre->right_ != nullptr)
                    {
                        pre = pre->right_;
                    }
                    node->data_ = pre->data_;
                    node->left_ = remove(node->left_, pre->data_);
                }
                else
                {
                    // 删除后继节点
                    Node *post = node->right_;
                    while (post->right_ != nullptr)
                    {
                        post = post->right_;
                    }
                    node->data_ = post->data_;
                    node->left_ = remove(node->left_, post->data_);
                }
            }
            else // 最多有一个孩子
            {
                if (node->left_ != nullptr)
                {
                    Node *left = node->left_;
                    delete node;
                    return left;
                }
                else if (node->right_ != nullptr)
                {
                    Node *right = node->right_;
                    delete node;
                    return right;
                }
                else
                {
                    return nullptr;
                }
            }
        }

        node->height_ = max(height(node->left_), height(node->right_)) + 1;

        return node;
    }

测试用例：
在这里插入图片描述
代码实现：

int main()
{
    AVLTree<int> avl;

    for (int i = 1; i <= 10; i++)
    {
        avl.insert(i);
    }

    avl.print_levelOrder();

    avl.remove(9);
    avl.print_levelOrder();

    avl.remove(10);
    avl.print_levelOrder();

    return 0;
}

运行结果：

层序遍历打印：4 2 8 1 3 6 9 5 7 10
层序遍历打印：4 2 8 1 3 6 10 5 7
层序遍历打印：4 2 6 1 3 5 8 7

哈夫曼树与哈夫曼编码

基本概念

哈夫曼树

又称为最佳判定树、最优二叉树，是一种带权路径长度最短的二叉树，常用于数据压缩

树的路径长度指的是从根到所有叶子节点的路径长度之和。

树的带权路径长度是从根到所有叶子节点的带权路径长度之和，计算方法为：
$wpl=\sum_{k=1}^{n} w_k l_k$
其中， $w_k$ 表示第 $k$ 哥叶子节点的权值， $l_k$ 表示第 $k$ 个叶子节点的路径长度

给定权值的情况下（给定的权值一定处于叶子节点），构造哈夫曼树的算法如下：

取出权值中最小的两个数，作为孩子节点，生成父节点，父节点的权值等于两个孩子节点权值之和
被取出作为孩子节点的两个权值移出权值列表，新生成的父节点加入权值列表
重复上述步骤，直到权值列表中仅含有一个元素

在这里插入图片描述

哈夫曼编码

分析：数据压缩时，应该希望出现频率高的编码短一些，频率低的编码长一些

举例：ABACDAEFDEG

统计字母频数：

字母	频数	字母	频数
A	3	E	2
B	1	F	1
C	1	G	1
D	2

以频数为权值，构建哈夫曼树，构建时左分支记作0，右分支记作1，得到如下的树：

在这里插入图片描述
得出编码表：

字母	编码	字母	编码
A	01	E	11
B	0000	F	0010
C	0001	G	0011
D	10

ABACDAEFDEG最终编码为：

010000010001100111001010110011

哈夫曼编码的特点

变长编码（每个字符编码的长度都不同）
立刻可解码性（任意字符的编码都不会是另一个字符编码的前缀）

魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

全家桶集齐！Qwen3.5四款小模型上线魔乐社区，附昇腾全套实践教程

魔乐社区

Pont - 搭建前后端之桥：高效、灵活的接口管理工具

Pont 是一款强大的数据服务层解决方案，它能够帮助开发者快速搭建前后端之间的桥梁，实现接口的高效管理和代码自动生成。无论是新手还是有经验的开发者，都能通过 Pont 轻松处理接口文档、生成类型安全的 API 代码，从而显著提升开发效率。[![Pont 工具标志](https://raw.gitcode.com/gh_mirrors/po/pont/raw/3f1b7d4bbba3fd2dda

魔乐社区

如何快速上手 hvac：HashiCorp Vault Python 客户端零基础入门指南

**hvac** 是 HashiCorp Vault 的 Python 3.X 客户端库，专为开发者提供简单高效的 Vault 交互方式。无论你是需要管理密钥、配置身份验证，还是实现安全的秘密数据存储，hvac 都能帮助你轻松搞定 Vault 的各项操作。本文将带你零基础快速入门，从安装到基础操作，让你在几分钟内即可上手使用这个强大的工具。[![hvac 客户端 Logo](https://r

魔乐社区

所有评论(0)

查看更多评论

SlashYe

@SlashYe

已为社区贡献1条内容