C++进阶 AVL树的讲解以及实现

news/2024/10/16 22:13:50 标签: c++, 开发语言, 数据结构, 二叉树, 二叉搜索树

   你好，欢迎阅读我的文章~

个人主页：@Mike

  所属专栏：C++进阶

目录

1. AVL的概念

2.AVL树的实现

2.1AVL树的结构

2.2AVL树的插入

2.2.1 插入的过程

2.2.2 平衡因子的更新

2.2.3 更新停止的条件

插入节点以及更新平衡因子的源码

3.AVL的旋转

3.1 右单旋

3.2 左单旋

3.3 左右双旋

3.4 右左双旋

1. AVL的概念

(1).AVL树是最先发明的自平衡二叉查找树，AVL是一颗空树，或者具备下列性质的二叉搜索树：它的左右子树都是AVL树，且左右子树的高度差的绝对值不超过1。AVL树是一颗高度平衡搜索二叉树，通过控制高度差去控制平衡。

(2).AVL树实现这里我们引入一个平衡因子(balance factor)的概念，每个结点都有一个平衡因子，任何结点的平衡因子等于右子树的高度减去左子树的高度，也就是说任何结点的平衡因子等于0/1/-1，AVL树并不是必须要平衡因子，但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡。

(3).AVL树整体结点数量和分布和完全二叉树类似，高度可以控制在 log_{N}^{}，那么增删查改的效率也可以控制在O(log{_{N}}^{}) ，相比二叉搜索树有了本质的提升。

(4).AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis是两个前苏联的科学家，他们在1962年的论文《An algorithm for the organization of information》中发表了它。

2.AVL树的实现

2.1AVL树的结构

template <class K, class V>
struct AVLTreeNode
{
    // 需要parent指针，后续更新平衡因子可以看到
    pair<K, V> _kv;
    AVLTreeNode<K, V> *_left;   // 左节点
    AVLTreeNode<K, V> *_right;  // 右节点
    AVLTreeNode<K, V> *_parent; // 父节点
    int _bf;                    // 平衡因子

    AVLTreeNode(const pair<K, V> &kv) // 构造
        : _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0)
    {
    }
};
template <class K, class V>
class AVLTree
{
    typedef AVLTreeNode<K, V> Node;

public:
    //........
private:
    Node *_root = nullptr;
};

2.2AVL树的插入

2.2.1 插入的过程

(1).插入一个值首先按二叉搜索树的规则进行插入。

(2).新增节点后，只会影响祖宗节点的高度，所以更新从新节点到根节点路径上的平衡因子，最坏情况下要更新到根，有些情况更新到中间即可。

(3).更新平衡因子过程中没有出现问题则插入结束。

(4).更新平衡因子过程中出现不平衡，对不平衡子树旋转，旋转后本质调平衡的同时，本质降低了子树的高度，不会再影响上一层，所以插入结束。

2.2.2 平衡因子的更新

更新规则:

(1).平衡因子=右子树高度-左子树高度

(2).只有子树高度发生变化才会影响当前节点的平衡因子。

(3).插入节点，高度增加。所以新增节点在parent的右子树，parent的平衡因子++，新增节点在parent的左子树，parent的平衡因子--。

(4).parent所在子树的高度是否变化决定了是否会继续往上更新

2.2.3 更新停止的条件

(1).更新后parent的平衡因子等于0，更新中parent的平衡因子变化为-1->0 或者 1->0，说明更新前
parent子树一边高一边低，新增的结点插入在低的那边，插入后parent所在的子树高度不变，不会
影响parent的父亲结点的平衡因子，更新结束。

(2).更新后parent的平衡因子等于1 或 -1，更新前更新中parent的平衡因子变化为0->1 或者 0->-1，说明更新前parent子树两边一样高，新增的插入结点后，parent所在的子树一边高一边低，parent所在的子树符合平衡要求，但是高度增加了1，会影响parent的父亲结点的平衡因子，所以要继续向上更新。

(3).更新后parent的平衡因子等于2 或 -2，更新前更新中parent的平衡因子变化为1->2 或者 -1->-2，说明更新前parent子树一边高一边低，新增的插入结点在高的那边，parent所在的子树高的那边更高了，破坏了平衡，parent所在的子树不符合平衡要求，需要旋转处理，旋转的目标有两个：1、把parent子树旋转平衡。2、降低parent子树的高度，恢复到插入结点以前的高度。所以旋转后也不需要继续往上更新，插入结束。

插入节点以及更新平衡因子的源码

bool Insert(const pair<K, V> &kv)
{

    // 二叉搜索树的插入
    if (_root == nullptr)
    {
        _root = new Node(kv);
        return true;
    }
    Node *parent = nullptr;
    Node *cur = _root;
    while (cur)
    {
        if (cur->_kv.first < kv.first)
        {
            parent = cur;
            cur = cur->_right;
        }
        else if (cur->_kv.first > kv.first)
        {
            parent = cur;
            cur = cur->_left;
        }
        else
        {
            return false;
        }
    }

    cur = new Node(kv);
    if (parent->_kv.first < kv.first)
    {
        parent->_right = cur;
    }
    else
    {
        parent->_left = cur;
    }
    cur->_parent = parent;

    // 更新平衡因子
    while (parent)
    {
        // 更新平衡因子
        if (cur == parent->_left)
        {
            parent->_bf--;
        }
        else
        {
            parent->_bf++;
        }

        if (parent->_bf == 0)
        {
            // 更新结束
            break;
        }
        else if (parent->_bf == 1 || parent->_bf == -1)
        {
            // 继续往上更新
            cur = parent;
            parent = parent->_parent;
        }
        else if (parent->_bf == 2 || parent->_bf == -2)
        {
            // 不平衡了，旋转处理
            break;
        }
        else
        {
            assert(false);
        }
    }
    return true;
}

3.AVL的旋转

3.1 右单旋

如图：

代码实现：

void RotateR(Node *parent)
{
    Node *subL = parent->_left;
    Node *subLR = subL->_right;
    // 需要注意除了要修改孩子指针指向，还是修改父亲
    parent->_left = subLR;
    if (subLR)
        subLR->_parent = parent;
    Node *parentParent = parent->_parent;
    subL->_right = parent;
    parent->_parent = subL;
    // parent有可能是整棵树的根，也可能是局部的子树
    // 如果是整棵树的根，要修改_root
    // 如果是局部的指针要跟上一层链接
    if (parentParent == nullptr)
    {
        _root = subL;
        subL->_parent = nullptr;
    }
    else
    {
        if (parent == parentParent->_left)
        {
            parentParent->_left = subL;
        }
        else
        {
            parentParent->_right = subL;
        }
        subL->_parent = parentParent;
    }
    parent->_bf = subL->_bf = 0;
}

3.2 左单旋

代码实现:

void RotateL(Node *parent)
{
    Node *subR = parent->_right;
    Node *subRL = subR->_left;
    parent->_right = subRL;
    if (subRL)
        subRL->_parent = parent;
    Node *parentParent = parent->_parent;
    subR->_left = parent;
    parent->_parent = subR;
    if (parentParent == nullptr)
    {
        _root = subR;
        subR->_parent = nullptr;
    }
    else
    {
        if (parent == parentParent->_left)
        {
            parentParent->_left = subR;
        }
        else
        {
            parentParent->_right = subR;
        }
        subR->_parent = parentParent;
    }
    parent->_bf = subR->_bf = 0;
}

3.3 左右双旋

当parent的平衡因子和cur的平衡因子正负不相同时，就要进行双旋。先对parent->left左旋，再对parent右旋。

代码实现:

void RotateLR(Node *parent)
{
    Node *subL = parent->_left;
    Node *subLR = subL->_right;
    int bf = subLR->_bf;
    RotateL(parent->_left);
    RotateR(parent);
    if (bf == 0)
    {
        subL->_bf = 0;
        subLR->_bf = 0;
        parent->_bf = 0;
    }
    else if (bf == -1)
    {
        subL->_bf = 0;
        subLR->_bf = 0;
        parent->_bf = 1;
    }
    else if (bf == 1)
    {
        subL->_bf = -1;
        subLR->_bf = 0;
        parent->_bf = 0;
    }
    else
    {
        assert(false);
    }
}

3.4 右左双旋

当parent的平衡因子和cur的平衡因子正负不相同时，就要进行双旋。先对parent->right右旋，再对parent左旋。

代码实现:

void RotateRL(Node *parent)
{
    Node *subR = parent->_right;
    Node *subRL = subR->_left;
    int bf = subRL->_bf;
    RotateR(parent->_right);
    RotateL(parent);
    if (bf == 0)
    {
        subR->_bf = 0;
        subRL->_bf = 0;
        parent->_bf = 0;
    }
    else if (bf == 1)
    {
        subR->_bf = 0;
        subRL->_bf = 0;
        parent->_bf = -1;
    }
    else if (bf == -1)
    {
        subR->_bf = 1;
        subRL->_bf = 0;
        parent->_bf = 0;
    }
    else
    {
        assert(false);
    }
}


http://www.niftyadmin.cn/n/5708612.html

相关文章

Unity3D模型消融方法（一）

Unity3D模型消融方法（一）

系列文章目录 unity工具 文章目录 系列文章目录👉前言👉一、消融效果👉二、使用步骤👉2-1.交互代码2-2. 完整shader代码👉2-3 新建材质球👉壁纸分享👉总结👉前言 今天介绍一下模型消融效果(shader实现) 还有另外一种换shader实现 大家好，我是心疼你的一切，…
阅读更多...
使用tgz包下载安装clickhouse低版本

使用tgz包下载安装clickhouse低版本

1.下载安装包 官方下载地址&#xff1a;https://packages.clickhouse.com/tgz/stable 阿里云下载地址&#xff1a;clickhouse-tgz-stable安装包下载_开源镜像站-阿里云 共需要下载四个文件 clickhouse-common-static-20.3.10.75.tgz clickhouse-common-static-dbg-20.3.10.7…
阅读更多...
大数据-174 Elasticsearch Query DSL - 全文检索 full-text query 匹配、短语、多字段 详细操作

大数据-174 Elasticsearch Query DSL - 全文检索 full-text query 匹配、短语、多字段 详细操作

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; 目前已经更新到了&#xff1a; Hadoop&#xff08;已更完&#xff09;HDFS&#xff08;已更完&#xff09;MapReduce&#xff08;已更完&am…
阅读更多...
【项目经验分享】Stable Diffusion生成式扩散模型毕业设计项目案例定制

【项目经验分享】Stable Diffusion生成式扩散模型毕业设计项目案例定制

关于Stable Diffusion生成式扩散模型的毕业设计题目&#xff0c;这些题目涵盖了该模型的应用、优化、创新以及与其他领域的结合&#xff1a; 基础应用与优化 Stable Diffusion生成效果与风格控制技术研究Stable Diffusion模型在图片去噪中的应用基于Stable Diffusion的高分辨…
阅读更多...
人工智能学习框架

人工智能学习框架

人工智能学习框架是指用于开发和训练机器学习和深度学习模型的软件库和工具集。这些框架帮助开发者更高效地构建、训练和部署模型&#xff0c;加速人工智能应用的开发进程。 常见的人工智能学习框架 TensorFlow 由Google开发&#xff0c;是一个开源的深度学习框架&#xff0c;…
阅读更多...
python中else使用汇总

python中else使用汇总

在 Python 中&#xff0c; else 有多种用法&#xff1a; 一、与 if 语句搭配 通常与 if 、 elif 一起使用&#xff0c;当所有条件都不满足时执行 else 中的代码块。 num 5 if num > 10: print("大于 10") elif num 5: print("等于 5") else…
阅读更多...
构建 debug 版本的 openmpi with ucx； ucx with-CUDA

构建 debug 版本的 openmpi with ucx； ucx with-CUDA

0&#xff0c;文件结构 ./repo$ ls build_openmpi.sh build_ucx.sh autoreconf: not foundsudo apt-get update sudo apt-get install autoconfsudo apt install libtoolsudo apt install valgrind valgrind-mpi valgrind-dbg 1, DEBUG UCX build_ucx.sh git clone https…
阅读更多...
标杆案例 | 蓝卓携手金鸡强磁打造金鸡强磁企业级工业互联网平台

标杆案例 | 蓝卓携手金鸡强磁打造金鸡强磁企业级工业互联网平台

磁性材料是宁波传统优势产业之一&#xff0c;没有原材料稀土&#xff0c;却集聚了全国约22%的稀土永磁材料企业&#xff0c;产量占全国总产量的40%以上。 金鸡强磁成立于1998年&#xff0c;专业致力于高品质的烧结钕铁硼的研发、生产和销售&#xff0c;是高新技术企业之一&…
阅读更多...
最新文章

Copyright @ 2022~2023