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

从C语言到C++_27(AVL树)概念+插入接口实现(四种旋转)（下）

2024-05-29 53
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 从C语言到C++_27(AVL树)概念+插入接口实现(四种旋转)

从C语言到C++_27(AVL树)概念+插入接口实现(四种旋转)(上）：https://developer.aliyun.com/article/1522261

左右双旋代码：

  void RotateLR(Node* parent)
  {
    Node* subL = parent->_left; // 记录subL的平衡因子
    Node* subLR = subL->_right;
    int bf = subLR->_bf;
 
    RotateL(parent->_left);
    RotateR(parent);
 
    subLR->_bf = 0; // 三种情况一样
    if (bf == -1)
    {
      parent->_bf = 1;
      subL->_bf = 0;
    }
    else if (bf == 1)
    {
      parent->_bf = 0;
      subL->_bf = -1;
    }
    else if (bf == 0)
    {
      parent->_bf = 0;
      subL->_bf = 0;
    }
    else // 理论不应走到这
    {
      assert(false); //在旋转前树的平衡因子就有问题，报错
    }
  }

4.4 右左双旋

思路和左右双旋一样，这里看图就行

右左双旋步骤示意图

1、插入新结点。

2、以90为旋转点进行右单旋。



3、以30为旋转点进行左单旋。

右左双旋的步骤如下：

  1. 以subR为旋转点进行右单旋。
  2. 以parent为旋转点进行左单旋。
  3. 更新平衡因子。

右左双旋后满足二叉搜索树的性质：

       右左双旋后，实际上就是让subRL的左子树和右子树，分别作为parent和subR的右子树和左子树，再让parent和subR分别作为subRL的左右子树，最后让subRL作为整个子树的根（结合图理解）。

subRL的左子树当中的结点本身就比parent的值大，因此可以作为parent的右子树。


subRL的右子树当中的结点本身就比subR的值小，因此可以作为subR的左子树。


       经过步骤1/2后，parent及其子树当中结点的值都就比subRL的值小，而subR及其子树当中结点的值都就比subRL的值大，因此它们可以分别作为subRL的左右子树。右左双旋后，平衡因子的更新随着subRL原始平衡因子的不同分为以下三种情况：

1、当subRL原始平衡因子是1时，左右双旋后subRL、parent、subR的平衡因子分别更新为

0、-1、0。

2、当subRL原始平衡因子是-1时，左右双旋后subRL、parent、subR的平衡因子分别更新为

0、0、1。

3、当subRL原始平衡因子是0时，左右双旋后subRL、parent、subR的平衡因子分别更新为

0、0、0。

经过右左双旋后，树的高度变为插入之前了，即树的高度没有发生变化，

所以右左双旋后一样无需继续往上更新平衡因子。

右左双旋代码：

  void RotateRL(Node* parent)
  {
    Node* subR = parent->_right; // 记录subL的平衡因子
    Node* subRL = subR->_left;
    int bf = subRL->_bf;
 
    RotateR(parent->_right);
    RotateL(parent);
 
    subRL->_bf = 0; // 三种情况一样
    if (bf == -1)
    {
      parent->_bf = 0;
      subR->_bf = 1;
    }
    else if (bf == 1)
    {
      parent->_bf = -1;
      subR->_bf = 0;
    }
    else if (bf == 0)
    {
      parent->_bf = 0;
      subR->_bf = 0;
    }
    else // 理论不应走到这
    {
      assert(false); //在旋转前树的平衡因子就有问题，报错
    }
  }

5. AVL树的验证

       AVL树是在二叉搜索树的基础上加入了平衡性的限制，也就是说AVL树也是二叉搜索树，因此我们可以先获取二叉树的中序遍历序列，来判断二叉树是否为二叉搜索树。

  void InOrder()
  {
    _InOrder(_root)
  }
 
protected:
  void _InOrder(Node* root)
  {
    if (root == nullptr)
    {
      return;
    }
    _InOrder(root->_left);
    cout << root->_kv.first << ":" << root->_kv.second << endl;
    _InOrder(root->_right);
  }


       但中序有序只能证明是二叉搜索树，要证明二叉树是AVL树还需验证二叉树的平衡性，在该过程中我们可以顺便检查每个结点当中平衡因子是否正确。采用后序遍历，变量步骤如下：


从叶子结点处开始计算每课子树的高度。（每棵子树的高度 = 左右子树中高度的较大值 + 1）


求高度函数以前写过了：

  int Height(Node* root)
  {
    if (root == nullptr)
    {
      return 0;
    }
    return max(Height(root->_left), Height(root->_right)) + 1;
  }

       先判断左子树是否是平衡二叉树。再判断右子树是否是平衡二叉树。若左右子树均为平衡二叉树，则返回当前子树的高度给上一层，继续判断上一层的子树是否是平衡二叉树，直到判断到根为止。（若判断过程中，某一棵子树不是平衡二叉树，则该树也就不是平衡二叉树了）

  bool IsBalance()
  {
    return _IsBalance(_root);
  }
 
protected:
  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;
      cout << rightHT << " - " << leftHT << endl;
      return false;
    }
 
    return abs(diff) < 2
      && _IsBalance(root->_left)
      && _IsBalance(root->_right);
  }

6. AVL树的删除(了解)和性能

AVL树的删除(了解)

       AVL树的删除和其它接口这里不实现了，如果不是AVL树会考到，工作中是不用学AVL树的，因为实际可以用接下来学的红黑树替代它。因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不错与删除不同的时，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。


具体实现参考《数据结构 - 用面向对象方法与C++描述》殷人昆版。

AVL树的性能

       AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即O(logN)。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。


       因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

7. AVL树插入验证完整代码

AVLTree.h:

#pragma once
 
#include <iostream>
#include <assert.h>
#include <algorithm>
#include <time.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; // balance factor 平衡因子
 
  AVLTreeNode(const pair<K, V>& kv)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _kv(kv)
    , _bf(0)
  {}
};
 
template <class K, class V>
class AVLTree
{
  typedef AVLTreeNode<K, V> Node;
 
public:
  bool Insert(const pair<K, V>& kv)
  {
    if (_root == nullptr)
    {
      _root = new Node(kv);
      return true;
    }
 
    Node* cur = _root;
    Node* parent = nullptr;
    while (cur) // 找要插入的位置
    {
      if (kv.first < cur->_kv.first)
      {
        parent = cur;
        cur = cur->_left;
      }
      else if (kv.first > cur->_kv.first)
      {
        parent = cur;
        cur = cur->_right;
      }
      else
      {
        return false;
      }
    }
 
    cur = new Node(kv);
    if (kv.first < parent->_kv.first) // 插入要插入的位置
    {
      parent->_left = cur;
    }
    else
    {
      parent->_right = cur;
    }
    cur->_parent = parent; // 三叉链多一步
 
    while (parent) // 控制平衡, 更新平衡因子, 如果平衡因子不对, 就要旋转
    {
      if (cur == parent->_left)
      {
        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);
  }
 
protected:
  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;
      cout << rightHT << " - " << leftHT << endl;
      return false;
    }
 
    return abs(diff) < 2
      && _IsBalance(root->_left)
      && _IsBalance(root->_right);
  }
 
  void _InOrder(Node* root)
  {
    if (root == nullptr)
    {
      return;
    }
    _InOrder(root->_left);
    cout << root->_kv.first << ":" << root->_kv.second << endl;
    _InOrder(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不为空才更新
    {
      subRL->_parent = parent;
    }
 
    Node* ppNode = parent->_parent; // 记录parent的parent，防止parent是一颗子树的头结点
 
    subR->_left = parent; // 再更新两个指针
    parent->_parent = subR;
 
    if (_root == parent)  // 最后更新两个指针
    {
      _root = subR;
      subR->_parent = nullptr;
    }
    else // parent是一颗子树的头结点
    {
      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; // 记录subL的平衡因子
    Node* subLR = subL->_right;
    int bf = subLR->_bf;
 
    RotateL(parent->_left);
    RotateR(parent);
 
    subLR->_bf = 0; // 三种情况一样
    if (bf == -1)
    {
      parent->_bf = 1;
      subL->_bf = 0;
    }
    else if (bf == 1)
    {
      parent->_bf = 0;
      subL->_bf = -1;
    }
    else if (bf == 0)
    {
      parent->_bf = 0;
      subL->_bf = 0;
    }
    else // 理论不应走到这
    {
      assert(false); //在旋转前树的平衡因子就有问题，报错
    }
  }
 
  void RotateRL(Node* parent)
  {
    Node* subR = parent->_right; // 记录subL的平衡因子
    Node* subRL = subR->_left;
    int bf = subRL->_bf;
 
    RotateR(parent->_right);
    RotateL(parent);
 
    subRL->_bf = 0; // 三种情况一样
    if (bf == -1)
    {
      parent->_bf = 0;
      subR->_bf = 1;
    }
    else if (bf == 1)
    {
      parent->_bf = -1;
      subR->_bf = 0;
    }
    else if (bf == 0)
    {
      parent->_bf = 0;
      subR->_bf = 0;
    }
    else // 理论不应走到这
    {
      assert(false); //在旋转前树的平衡因子就有问题，报错
    }
  }
 
  Node* _root = nullptr; // 给缺省值直接在初始化列表初始化
};

Test.c:

#include "AVLTree.h"
 
void TestAVLTree1()
{
  //int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };  // 测试单旋平衡因子调节
  int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };  // 测试双旋平衡因子调节
  AVLTree<int, int> t1;
  for (const auto& e : arr)
  {
    t1.Insert(make_pair(e, e));
  }
 
  t1.InOrder();
  cout << "IsBalance:" << t1.IsBalance() << endl;
} 
 
void TestAVLTree2()
{
  size_t N = 10000;
  srand(time(0));
  AVLTree<int, int> t1;
  for (size_t i = 0; i < N; ++i)
  {
    int x = rand();
    t1.Insert(make_pair(x, i));
    //bool ret = t1.IsBalance();
    //if (ret == false)
    //{
    //  int u = 1; // 查bug打断点用
    //}
    //else
    //{
    //  cout << "Insert:" << x << " IsBalance:" << ret << endl;
    //}
  }
  cout << "IsBalance:" << t1.IsBalance() << endl;
}
 
int main()
{
  TestAVLTree1();
 
  return 0;
}

8. AVL树笔试选择题

1. 下面关于AVL树说法不正确的是（）

A.AVL树也是二叉搜索树

B.极端情况下，AVL树可能也会退化成单支树


C.AVL查询的时间复杂度是O(log_2N)


D.AVL树是通过平衡因子限制保证其平衡性的


2. 现有一棵无重复关键字的平衡二叉树（AVL树），对其进行中序遍历可得到一个降序序列。


下列关于该平衡二叉树的叙述中，正确的是（）


A.根结点的度一定为2


B.树中最小元素一定是叶结点


C.最后插入的元素一定是叶结点


D.树中最大元素一定是无左子树


3. 关于AVL树的旋转说法正确的是（）


A.插入时，AVL树最多只需要旋转两次


B.删除时，只要某个节点的平衡因子不满足特性时 ，只需要对该棵子树进行旋转，就可以使AVL树再次平衡


C.AVL树的节点中必须维护平衡因子，因为要依靠其平衡因子是否需要旋转以维护其平衡性


D.AVL树的双旋转只需要直接使用对应的单旋转即可

答案：

1. B

 AVL树：一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树


  1. 它的左右子树都是AVL树


  2. 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)


 故：如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O(logN)，搜索时间复杂度O(logN)


 A：正确，参考上述概念


 B：错误，AVL树没有极端情况，其是为了防止二叉搜索树的极端情况二给出的


 C：正确，参考上述概念


 D：正确，平衡因子：左右子树高度之间，其绝对值如果不超过1，则认为树就是平衡的


2. D


题目中说：中序遍历得到一个降序序列，则说明：根小于左子树中节点，大于右子树中节点


 A：错误，根可以没有左子树，比如树中只有两个节点，即根以及根的右子树


 B：错误，树中最小的元素一定是最左侧或者最右侧节点，但不一定是叶子节点


 C：错误，最后插入的元素不一定是叶子节点，因为新节点插入后，为了保证其平衡性，还要对树 进行旋转处理，旋    转之后，就不一定在叶子的位置


 D：正确，因为最大元素如果存在左子树，中序遍历就不可能是降序序列


3. A


 A：正确，即双旋


 B：错误，可能需要旋转多次，子树旋转后，其高度降低了一层，其上层可能也需要跟着旋转


 C：错误，平衡因子不是必须要维护的，在操作时也可以直接通过高度函数来算，只不过比较麻烦


 D：错误，不能直接使用单旋转，因为两个单旋转完成后，还需要对部分节点的平衡因子进行更新


本篇完。

本篇完。

下一篇：红黑树概念和实现。然后是set和map的模拟实现。

文章标签：
C语言
C++
关键词：
C语言C++
C++ avl
C++ c语言
C++概念
C语言树
GR鲸鱼
目录
相关文章
土木林森
|
4月前
|
存储 算法 C语言
"揭秘C语言中的王者之树——红黑树：一场数据结构与算法的华丽舞蹈，让你的程序效率飙升，直击性能巅峰！"
【8月更文挑战第20天】红黑树是自平衡二叉查找树，通过旋转和重着色保持平衡，确保高效执行插入、删除和查找操作，时间复杂度为O(log n)。本文介绍红黑树的基本属性、存储结构及其C语言实现。红黑树遵循五项基本规则以保持平衡状态。在C语言中，节点包含数据、颜色、父节点和子节点指针。文章提供了一个示例代码框架，用于创建节点、插入节点并执行必要的修复操作以维护红黑树的特性。
土木林森
106 1
chian-ocean
|
8天前
|
存储 C++
【C++】AVL树
AVL树是一种自平衡二叉搜索树，由Georgy Adelson-Velsky和Evgenii Landis提出。它通过确保任意节点的两子树高度差不超过1来维持平衡，支持高效插入、删除和查找操作，时间复杂度为O(log n)。AVL树通过四种旋转操作（左旋、右旋、左-右旋、右-左旋）来恢复树的平衡状态，适用于需要频繁进行数据操作的场景。
chian-ocean
24 2
ephemerals__
|
25天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
63 16
LuckiBit
|
1天前
|
算法 编译器 C语言
【C语言】C++ 和 C 的优缺点是什么？
C 和 C++ 是两种强大的编程语言，各有其优缺点。C 语言以其高效性、底层控制和简洁性广泛应用于系统编程和嵌入式系统。C++ 在 C 语言的基础上引入了面向对象编程、模板编程和丰富的标准库，使其适合开发大型、复杂的软件系统。 在选择使用 C 还是 C++ 时，开发者需要根据项目的需求、语言的特性以及团队的技术栈来做出决策。无论是 C 语言还是 C++，了解其优缺点和适用场景能够帮助开发者在实际开发中做出更明智的选择，从而更好地应对挑战，实现项目目标。
LuckiBit
14 0
c的前世今生
|
2月前
|
C语言 C++
C 语言的关键字 static 和 C++ 的关键字 static 有什么区别
在C语言中，`static`关键字主要用于变量声明，使得该变量的作用域被限制在其被声明的函数内部，且在整个程序运行期间保留其值。而在C++中，除了继承了C的特性外，`static`还可以用于类成员，使该成员被所有类实例共享，同时在类外进行初始化。这使得C++中的`static`具有更广泛的应用场景，不仅限于控制变量的作用域和生存期。
c的前世今生
59 10
小徐在进步
|
3月前
|
C语言
数据结构基础详解(C语言):图的基本概念_无向图_有向图_子图_生成树_生成森林_完全图
本文介绍了图的基本概念，包括图的定义、无向图与有向图、简单图与多重图等，并解释了顶点度、路径、连通性等相关术语。此外还讨论了子图、生成树、带权图及几种特殊形态的图，如完全图和树等。通过这些概念，读者可以更好地理解图论的基础知识。
小徐在进步
138 8
Codelinghu
|
2月前
|
C语言 C++
实现两个变量值的互换[C语言和C++的区别]
实现两个变量值的互换[C语言和C++的区别]
Codelinghu
23 0
小徐在进步
|
3月前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手，详细介绍了先序、中序和后序遍历方法，并探讨了如何构建二叉树及线索二叉树的概念。接着，文章讲解了树和森林的存储结构，特别是如何将树与森林转换为二叉树形式，以便利用二叉树的遍历方法。最后，讨论了树和森林的遍历算法，包括先根、后根和层次遍历。通过这些内容，读者可以全面了解二叉树及其相关概念。
小徐在进步
52 6
小徐在进步
|
3月前
|
存储 机器学习/深度学习 C语言
数据结构基础详解(C语言): 树与二叉树的基本类型与存储结构详解
本文介绍了树和二叉树的基本概念及性质。树是由节点组成的层次结构，其中节点的度为其分支数量，树的度为树中最大节点度数。二叉树是一种特殊的树，其节点最多有两个子节点，具有多种性质，如叶子节点数与度为2的节点数之间的关系。此外，还介绍了二叉树的不同形态，包括满二叉树、完全二叉树、二叉排序树和平衡二叉树，并探讨了二叉树的顺序存储和链式存储结构。
小徐在进步
42 3
小徐在进步
|
3月前
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用，涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用；接着介绍了并查集的基本概念、存储结构及优化方法；随后探讨了二叉排序树的定义、查找、插入和删除操作；最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文，读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
小徐在进步
57 2