AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

一篇文章教会你什么是高度平衡二叉搜索(AVL)树（下）

2023-10-11 74
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 3.3 新节点插入较高左子树的右侧—左右：先左单旋再右单旋

3.3 新节点插入较高左子树的右侧—左右：先左单旋再右单旋

void RotateLR(Node* parent)
{
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    int bf = subLR->_bf;
    RotateL(parent->_left);
    RotateR(parent);
    subLR->_bf = 0;
    if (bf == 1)//上图为例,新增节点在c下方
    {
        parent->_bf = 0;
        subL->_bf = -1;
    }
    else if (bf == -1)//上图为例,新增节点在b下方
    {
        parent->_bf = 1;
        subL->_bf = 0;
    }
    else if (bf == 0)//上图为例,无其他子树,60为新增节点的情况
    {
        parent->_bf = 0;
        subL->_bf = 0;
    }
    else
    {
        assert(false);
    }
}
  1. 首先，保存父节点 parent 的左子树 subL 和 subL 的右子树 subLR 的指针，以及 subLR 的平衡因子 bf。
  2. 对 parent 的左子树 subL 进行左旋转操作，以调整子树的结构。
  3. 然后，对 parent 进行右旋转操作，以将 subL 成为 parent 的右子树。
  4. 将 subLR 的平衡因子 _bf 设置为0，因为它在旋转后的位置高度没有变化。
  5. 根据subLR的平衡因子bf的不同值来更新节点的平衡因子：
  • 如果 bf 为1，表示 subL 的左子树高度大于右子树，将 parent 的平衡因子设置为0，subL 的平衡因子设置为-1。
  • 如果 bf 为-1，表示 subL 的右子树高度大于左子树，将 parent 的平衡因子设置为1，subL 的平衡因子设置为0。
  • 如果 bf 为0，表示 subL 的左右子树高度相等，将 parent 和 subL 的平衡因子都设置为0。
  1. 如果 bf 不是1、-1或0，那么会触发 assert(false)，表示出现了异常情况。

3.4 新节点插入较高右子树的左侧—右左：先右单旋再左单旋

void RotateRL(Node* parent)
{
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    int bf = subRL->_bf;
    RotateR(parent->_right);
    RotateL(parent);
    subRL->_bf = 0;
    if (bf == 1)
    {
        subR->_bf = 0;
        parent->_bf = -1;
    }
    else if (bf == -1)
    {
        subR->_bf = 1;
        parent->_bf = 0;
    }
    else if (bf == 0)
    {
        parent->_bf = 0;
        subR->_bf = 0;
    }
    else
    {
        assert(false);
    }
}
  1. 首先，保存父节点 parent 的右子树 subR 和 subR 的左子树 subRL 的指针，以及 subRL 的平衡因子 bf。
  2. 对 parent 的右子树 subR 进行右旋转操作，以调整子树的结构。
  3. 然后，对 parent 进行左旋转操作，以将 subR 成为 parent 的左子树。
  4. 将 subRL 的平衡因子 _bf 设置为0，因为它在旋转后的位置高度没有变化。
  5. 根据subRL的平衡因子bf的不同值来更新节点的平衡因子：
  • 如果 bf 为1，表示 subRL 的左子树高度大于右子树，将 subR 的平衡因子设置为0，parent 的平衡因子设置为-1。
  • 如果 bf 为-1，表示 subRL 的右子树高度大于左子树，将 subR 的平衡因子设置为1，parent 的平衡因子设置为0。
  • 如果 bf 为0，表示 subRL 的左右子树高度相等，将 parent 和 subR 的平衡因子都设置为0。
  1. 如果 bf 不是1、-1或0，那么会触发 assert(false)，表示出现了异常情况。

原理同先左单旋再右单旋

总结：

假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑

  1. pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR

当pSubR的平衡因子为1时，执行左单旋

当pSubR的平衡因子为-1时，执行右左双旋

  1. pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pSubL

当pSubL的平衡因子为-1是，执行右单旋

当pSubL的平衡因子为1时，执行左右双旋

旋转完成后，原pParent为根的子树个高度降低，已经平衡，不需要再向上更新。

4.AVL树的验证

4.1 验证其为二叉搜索树

中序遍历可得到一个有序的序列，就说明为二叉搜索树

void InOrder()
{
    _InOrder(_root);
    cout << endl;
}
private:
    void _InOrder(Node* root)
    {
        if (root == nullptr)
        {
            return;
        }
        _InOrder(root->_left);
        cout << root->_kv.first << ":" << root->_kv.second << endl;
        _InOrder(root->_right);
    }
  1. 首先，检查当前节点 root 是否为空（即树是否为空）。如果为空，则返回，结束递归。
  2. 接着，递归地调用 _InOrder 函数，遍历左子树 root->_left。这将按照升序访问左子树中的节点。
  3. 然后，输出当前节点 root 的关键字和关联的值，通常使用 cout 输出到控制台。
  4. 最后，再次递归调用 _InOrder 函数，遍历右子树 root->_right。这将按照升序访问右子树中的节点。

4.2 验证其为平衡树

  1. 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
  2. 节点的平衡因子是否计算正确

高度成员函数

int Height(Node* root)
{
    if (root == nullptr)
        return 0;
    return max(Height(root->_left), Height(root->_right)) + 1;
}
  1. 首先，检查当前节点 root 是否为空（即树是否为空）。如果为空，则返回高度0，表示空树的高度为0。
  2. 如果当前节点 root 不为空，那么递归地调用 Height 函数来计算左子树的高度和右子树的高度。
  3. 使用 max 函数比较左子树和右子树的高度，然后加上1（当前节点的高度），得到整棵树的高度。
  4. 返回树的高度作为函数的结果。

平衡树检测函数

bool IsBalance()
{
    return _IsBalance(_root);
}
private:
  bool _IsBalance(Node* root)
  {
    if (root == nullptr)
    {
      return true;
    }
    int leftHT = Height(root->_left);
    int rightHT = Height(root->_right);
    int diff = rightHT - leftHT;
    if (diff != root->_bf)
    {
      cout << root->_kv.first << "平衡因子异常" << endl;
      return false;
    }
    return abs(diff) < 2
      && _IsBalance(root->_left)
      && _IsBalance(root->_right);
  }
  1. 首先，检查当前节点 root 是否为空（即树是否为空）。如果为空，则返回 true，因为空树是平衡的。
  2. 如果当前节点 root 不为空，那么首先计算左子树和右子树的高度，分别存储在 leftHT 和 rightHT 中。
  3. 然后，计算左子树和右子树高度差（右子树高度减去左子树高度），存储在 diff 变量中。
  4. 检查当前节点的平衡因子 _bf 是否等于 diff，如果不相等，表示平衡因子异常，输出错误信息并返回 false。
  5. 继续检查当前节点是否满足AVL树的平衡条件，即平衡因子的绝对值不超过1，以及递归检查左子树和右子树是否也是平衡的（调用 _IsBalance 函数）。
  6. 如果所有条件都满足，返回 true 表示当前子树是平衡的。

4.3 验证用例

常规场景1

{16, 3, 7, 11, 9, 26, 18, 14, 15}

特殊场景2

{4, 2, 6, 1, 3, 5, 15, 7, 16, 14}

AVL树实现及验证所有代码

1.AVL代码实现

AVL.hpp

#pragma once
#include <iostream>
#include <algorithm>
#include <assert.h>
using namespace std;
template<class K, class V>
struct AVLTreeNode
{
  AVLTreeNode<K, V>* _left;
  AVLTreeNode<K, V>* _right;
  AVLTreeNode<K, V>* _parent;
  pair<K, V> _kv;
  int _bf;
  AVLTreeNode(const pair<K, V>& kv)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _kv(kv)
    , _bf(0)
  {}
};
template<class K, class V>
struct AVLTree
{
  typedef AVLTreeNode<K, V> Node;
public:
  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->_right)
      {
        parent->_bf++;
      }
      else
      {
        parent->_bf--;
      }
      if (parent->_bf == 0)
      {
        break;
      }
      else if (abs(parent->_bf) == 1)
      {
        parent = parent->_parent;
        cur = cur->_parent;
      }
      else if (abs(parent->_bf) == 2)
      {
        if (parent->_bf == 2 && cur->_bf == 1)
        {
          RotateL(parent);
        }
        else if ((parent->_bf == -2 && cur->_bf == -1))
        {
          RotateR(parent);
        }
        else if (parent->_bf == -2 && cur->_bf == 1)
        {
          RotateLR(parent);
        }
        else if (parent->_bf == 2 && cur->_bf == -1)
        {
          RotateRL(parent);
        }
        else
        {
          assert(false);
        }
        break;
      }
      else
      {
        assert(false);
      }
    }
    return true;
  }
  void InOrder()
  {
    _InOrder(_root);
    cout << endl;
  }
  bool IsBalance()
  {
    return _IsBalance(_root);
  }
private:
  int BalanceFactor(Node* node)
  {
    if (node == nullptr)
    {
      return 0;
    }
    return Height(node->_left) - Height(node->_right);
  }
  bool _IsBalance(Node* root)
  {
    if (root == nullptr)
    {
      return true;
    }
    int leftHT = Height(root->_left);
    int rightHT = Height(root->_right);
    int diff = rightHT - leftHT;
    if (diff != root->_bf)
    {
      cout << root->_kv.first << "平衡因子异常" << endl;
      return false;
    }
    return abs(diff) < 2
      && _IsBalance(root->_left)
      && _IsBalance(root->_right);
  }
  int Height(Node* root)
  {
    if (root == nullptr)
      return 0;
    return max(Height(root->_left), Height(root->_right)) + 1;
  }
  void RotateL(Node* parent)
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    parent->_right = subRL;
    if (subRL)
      subRL->_parent = parent;
    Node* ppNode = parent->_parent;
    subR->_left = parent;
    parent->_parent = subR;
    if (_root == parent)
    {
      _root = subR;
      subR->_parent = nullptr;
    }
    else
    {
      if (ppNode->_left == parent)
      {
        ppNode->_left = subR;
      }
      else
      {
        ppNode->_right = subR;
      }
      subR->_parent = ppNode;
    }
    subR->_bf = parent->_bf = 0;
  }
  void RotateR(Node* parent)
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    parent->_left = subLR;
    if (subLR)
      subLR->_parent = parent;
    Node* ppNode = parent->_parent;
    subL->_right = parent;
    parent->_parent = subL;
    if (_root == parent)
    {
      _root = subL;
      subL->_parent = nullptr;
    }
    else
    {
      if (ppNode->_left == parent)
      {
        ppNode->_left = subL;
      }
      else
      {
        ppNode->_right = subL;
      }
      subL->_parent = ppNode;
    }
    subL->_bf = parent->_bf = 0;
  }
  void RotateLR(Node* parent)
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    int bf = subLR->_bf;
    RotateL(parent->_left);
    RotateR(parent);
    subLR->_bf = 0;
    if (bf == 1)
    {
      parent->_bf = 0;
      subL->_bf = -1;
    }
    else if (bf == -1)
    {
      parent->_bf = 1;
      subL->_bf = 0;
    }
    else if (bf == 0)
    {
      parent->_bf = 0;
      subL->_bf = 0;
    }
    else
    {
      assert(false);
    }
  }
  void RotateRL(Node* parent)
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    int bf = subRL->_bf;
    RotateR(parent->_right);
    RotateL(parent);
    subRL->_bf = 0;
    if (bf == 1)
    {
      subR->_bf = 0;
      parent->_bf = -1;
    }
    else if (bf == -1)
    {
      subR->_bf = 1;
      parent->_bf = 0;
    }
    else if (bf == 0)
    {
      parent->_bf = 0;
      subR->_bf = 0;
    }
    else
    {
      assert(false);
    }
  }
  void _InOrder(Node* root)
  {
    if (root == nullptr)
    {
      return;
    }
    _InOrder(root->_left);
    cout << root->_kv.first << ":" << root->_kv.second << endl;
    _InOrder(root->_right);
  }
private:
  Node* _root = nullptr;
};

2.AVL验证代码实现

AVLTEST.cpp

#include "AVL.hpp"
int main()
{
    //int a[]={16, 3, 7, 11, 9, 26, 18, 14, 15};
    int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    AVLTree<int, int> avl1;
    for (auto e : a)
        avl1.Insert(make_pair(e, e));
    avl1.InOrder();
    cout << "IsBlance:" << avl1.IsBalance() << endl;
    return 0;
}


文章标签：
存储
测试技术
爱学习的鱼佬
目录
相关文章
爱学习的鱼佬
|
存储 算法 C++
一篇文章教会你什么是高度平衡二叉搜索(AVL)树（上）
AVL树的概念 AVL树（Adelson-Velsky and Landis Tree）是计算机科学中最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此
爱学习的鱼佬
104 0
Eternity._
|
5月前
|
算法 测试技术 C++
【C++高阶】掌握AVL树：构建与维护平衡二叉搜索树的艺术
【C++高阶】掌握AVL树：构建与维护平衡二叉搜索树的艺术
Eternity._
42 2
wjq++
|
6月前
深入解析AVL树：高效实现二叉平衡搜索树（2）
深入解析AVL树：高效实现二叉平衡搜索树
wjq++
36 1
wjq++
|
6月前
|
存储
深入解析AVL树：高效实现二叉平衡搜索树
深入解析AVL树：高效实现二叉平衡搜索树
wjq++
31 1
sky_qiyi
|
6月前
数据结构学习记录——平衡二叉树的调整（基本介绍、右单旋、左单旋、左右双旋、右左双旋、平衡因子的计算）
数据结构学习记录——平衡二叉树的调整（基本介绍、右单旋、左单旋、左右双旋、右左双旋、平衡因子的计算）
sky_qiyi
108 1
Yawesh
|
7月前
|
存储 机器学习/深度学习 算法
【C++入门到精通】C++入门 —— AVL 树（自平衡二叉搜索树）
【C++入门到精通】C++入门 —— AVL 树（自平衡二叉搜索树）
Yawesh
51 2
sky_qiyi
|
6月前
|
算法
数据结构和算法学习记录——平衡二叉树（基本介绍、平衡因子、平衡二叉树的定义、平衡二叉树的高度）
数据结构和算法学习记录——平衡二叉树（基本介绍、平衡因子、平衡二叉树的定义、平衡二叉树的高度）
sky_qiyi
138 0
Miss小远
|
存储 算法 程序员
深入解析红黑树：自平衡的二叉搜索艺术
深入解析红黑树：自平衡的二叉搜索艺术
Miss小远
73 0
三哥一起来编程
LeetCode-1664 生成平衡数组的方案树
LeetCode-1664 生成平衡数组的方案树
三哥一起来编程
59 0
luck++
学习平衡搜索二叉树(AVL树)【日志】
学习平衡搜索二叉树(AVL树)【日志】
luck++
92 0

热门文章

最新文章

  • 1
    RDS入门——Excel文件转存到RDS数据库实践
  • 2
    3、Python与设计模式--建造者模式
  • 3
    PostgreSQL SQL HINT的使用
  • 4
    跟阿里云技术专家阙寒一起深度了解视频直播CDN技术
  • 5
    流批一体的近实时数仓的思考与设计
  • 6
    带你读《存储漫谈Ceph原理与实践》第三章接入层3.3.文件存储 CephFS（一）
  • 7
    java split()
  • 8
    （转载） 数组a[]={3,5,2,4,1,8}，要求从a中找出所有“和”等于10的子集
  • 9
    linux下java 调用 c jni 实现 HelloWorld
  • 10
    ASP.NET MVC Music Store教程（3)：视图和视图模型
  • 1
    《人工智能知识图谱构建与应用的最新突破与成果》
    32
  • 2
    《零样本学习：突破瓶颈，开启智能新征程》
    25
  • 3
    《知识表示：开启人工智能学习与推理的密钥》
    26
  • 4
    《信息传播：人工智能助力驱散虚假信息阴霾》
    24
  • 5
    《多模态融合：开启智能新时代的钥匙》
    34
  • 6
    自学记录鸿蒙 API 13：实现人脸检测 Core Vision Face Detector
    25
  • 7
    阿里云先知安全沙龙(武汉站) ——AI赋能软件漏洞检测，机遇, 挑战与展望
    440
  • 8
    在线使用：Poe Ai网页版_pc版_poe ai中文官网入口
    19
  • 9
    java项目中jar启动执行日志报错：no main manifest attribute, in /www/wwwroot/snow-server/z-server.jar-jar打包的大小明显小于正常大小如何解决
    21
  • 10
    新手指南：人工智能poe ai 怎么用？国内使用poe记住这个方法就够了！
    33

    • 相关电子书

    更多
  • 「D2之夜」探究高性能的海量节点树
  • 探究高性能的海量节点树
  • 低代码开发师（初级）实战教程
    • 下一篇
    手把手教你白嫖阿里云服务器(免费领服务器)