备案控制台
探索云世界
开发者社区 开发与运维 文章 正文

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

2023-10-11 35
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 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;
}


文章标签：
存储
测试技术
爱学习的鱼佬
目录
相关文章
爱学习的鱼佬
|
6月前
|
存储 算法 C++
一篇文章教会你什么是高度平衡二叉搜索(AVL)树（上）
AVL树的概念 AVL树（Adelson-Velsky and Landis Tree）是计算机科学中最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此
爱学习的鱼佬
41 0
时雨h
|
12天前
|
存储 机器学习/深度学习 人工智能
树和森林 查找
树和森林 查找
时雨h
11 2
Miss小远
|
8月前
|
存储 算法 程序员
深入解析红黑树：自平衡的二叉搜索艺术
深入解析红黑树：自平衡的二叉搜索艺术
Miss小远
44 0
三哥一起来编程
|
8月前
LeetCode-1664 生成平衡数组的方案树
LeetCode-1664 生成平衡数组的方案树
三哥一起来编程
33 0
小李の踢踏舞步
|
8月前
|
算法
算法训练Day18|● 110.平衡二叉树 ● 257. 二叉树的所有路径 ● 404.左叶子之和
算法训练Day18|● 110.平衡二叉树 ● 257. 二叉树的所有路径 ● 404.左叶子之和
小李の踢踏舞步
23 0
Fox!
|
8月前
【AVL树的模拟实现】
【AVL树的模拟实现】
Fox!
28 0
luck++
|
10月前
学习平衡搜索二叉树(AVL树)【日志】
学习平衡搜索二叉树(AVL树)【日志】
luck++
56 0
游客6nmtzqmqofvbk
|
11月前
|
存储 C++
【C++】AVL树模拟实现
当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1，达到高度平衡，即可降低树的高度，从而减少平均搜索长度。即如果一棵二叉搜索树的任意节点左右子树高度差绝对值都<=1，它就是AVL树。 空树也算AVL树
游客6nmtzqmqofvbk
39 0
林寻星辰
|
存储 算法 Java
高度平衡的二叉搜索树简介
什么是一个高度平衡的二叉搜索树? 树结构中的常见用语: 节点的深度 - 从树的根节点到该节点的边数 节点的高度 - 该节点和叶子之间最长路径上的边数 树的高度 - 其根节点的高度 一个高度平衡的二叉搜索树（平衡二叉搜索树）是在插入和删除任何节点之后，可以自动保持其高度最小。也就是说，有 N 个节点的平衡二叉搜索树，它的高度是 logN 。并且，每个节点的两个子树的高度不会相差超过 1。 为什么是 logN 呢? 一个高度为 h 的二叉树 .换言之，一个有 N 个节点，且高度为 h 的二叉树 所以根据定义, 我们可以判断出一个二叉搜索树是否是高度平衡的 (平衡二叉树)。 正如我们之前提到的
林寻星辰
107 0
k5qlxezsphxku
Leedcode二叉搜索树中的搜索[层序遍历+利用性质]
Leedcode二叉搜索树中的搜索[层序遍历+利用性质]
k5qlxezsphxku
63 0
Leedcode二叉搜索树中的搜索[层序遍历+利用性质]

热门文章

最新文章

  • 1
    Linux查看进程的内存占用情况
  • 2
    大咖云集，技术宅开趴倒计时 —— 2017 Kubernetes Meetup | 成都站
  • 3
    ubuntu安装KVM虚拟机管理virt-manager
  • 4
    OpenCV4之C++入门详解 （上）
  • 5
    vue2中computed中无法获取到this
  • 6
    Visual Basic快速入门
  • 7
    HDU 4968 Improving the GPA
  • 8
    这56家公司共同发力智慧城市
  • 9
    书写高质量JavaScript代码的要义（The Essentials of Writing High Quality JavaScript）翻译
  • 10
    linux驱动开发--字符设备：信号量
  • 1
    【软件工程】融通未来的工艺：深度解析统一过程在软件开发中的角色
    13
  • 2
    IBM SPSS Modeler分类决策树C5.0模型分析空气污染物数据
    13
  • 3
    【软件工程】走进瀑布模型：传统软件开发的经典之路
    13
  • 4
    数据分享|R语言用lme4多层次（混合效应）广义线性模型（GLM），逻辑回归分析教育留级调查数据（下）
    11
  • 5
    【软件工程】走近演化过程模型：软件开发的不断进化之路
    84
  • 6
    【Mybatis】深入学习MyBatis：概述、主要特性以及配置与映射
    13
  • 7
    【MySQL】数据库规范化的三大法则 — 一探范式设计原则
    15
  • 8
    r语言中对LASSO回归，Ridge岭回归和弹性网络Elastic Net模型实现（下）
    12
  • 9
    【MySQL】数据库中为什么使用B+树不用B树
    8
  • 10
    【MySQL】SQL优化
    10

    • 相关课程

    更多
  • 【算法实战】10. 树回归算法

    • 相关电子书

    更多
  • 探究高性能的海量节点树
  • 低代码开发师（初级）实战教程
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）