AI 助理
备案控制台
开发者社区 云计算 文章 正文

AVLTree——高度平衡二叉搜索树

2024-01-17 154
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： AVLTree——高度平衡二叉搜索树


一、AVLTree的引入

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法——AVLTree。

AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它。

二、概念

1、概念

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

1、它的左右子树都是AVL树。

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

3、平衡因子 = 右子树高度 - 左子树高度。

2、结点实现

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)
  {}
};

3、整体框架

template<class K, class V>
struct AVLTree
{
  typedef AVLTreeNode<K, V> Node;
private:
  Node* _root = nullptr;
}

三、新节点的插入

1、插入

因为AVL树是一颗搜索二叉树，所以它的插入和我们前面讲到的搜索二叉树的插入一样，我们都是小的往左子树插入，大的往右子树插入。代码如下：

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->_left = cur;
    }
    else
    {
      parent->_right = cur;
    }
    cur->_parent = parent;
    //调整平衡
    // 1、更新平衡因子
    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)
      {
        // 说明parent 所在的子树不平衡了，需要旋转处理
        // 1、单旋
        if (parent->_bf == 2 && cur->_bf == 1) // 左单旋
        {
          RotateL(parent);
        }
        else if (parent->_bf == -2 && cur->_bf == -1) //右单旋
        {
          RotateR(parent);
        }
        //2、双旋
        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;
  }

我们在插入一个新的结点后，先要更新平衡因子。而插入新节点后，AVL树可能不会平衡了，所以我们必须根据平衡因子去判断它是否平衡，如果不平衡，我们就需要进行旋转调整。

2、平衡因子更新规则

1、新增在右，parent->bf++，新增在左，parent->bf--。

2、更新后，parent->bf == 1 or -1，说明parent插入前的平衡因子是0，且左右子树高度相等，插入后有一边高，parent高度变了，需要继续往上更新

3、更新后，parent->bf == 0，说明parent插入前的平衡因子是1 or -1,说明左右子树一边高一边低，插入后两边一样高，插入填上了矮的那边，parent所在子树高度不变，不需要往上继续更新

4、更新后，parent->bf == 2 or -2，说明parent插入之前的平衡因子是1 or -1，已是平衡临界值，插入变成 2 or -2，打破平衡，parent所在子树需要旋转处理。

上面的代码中有四个函数涉及到旋转调节平衡。那么下面我们就来详细讲解一下四种情况的旋转调节AVL树的平衡。

四、旋转调平衡

1、左单旋

我们在出现了下面的情况后就必须对树进行左单旋。即新节点插入较高右子树的右侧——左单旋。

一般步骤：

1、subRL成为parent的右子树，然后要更新subRL的父亲为parent，更新parent的右为subRL（注：subRL可能为空）。

2、parent成为subR的左子树，更新parent的父亲为subR，而subR的左为parent。

3、注意parent是不是整棵树的root，如果是，则让subR成为_root，同时让_root->_parent置为空；如果不是，就将subR连接到它父亲的左或者右。最后更新平衡因子。

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

2、右单旋

新节点插入较高左子树的左侧——右单旋。

一般步骤：

1、subLR成为parent的左子树，然后要更新subLR的父亲为parent，更新parent的左为subLR（注：subRL可能为空）。

2、parent成为subR的右子树，更新parent的父亲为subL，而subL的右为parent。

3、注意parent是不是整棵树的root，如果是，则让subL成为_root，同时让_root->_parent置为空；如果不是，就将subL连接到它父亲的左或者右。最后更新平衡因子。

void RotateR(Node* parent) //右单旋
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    Node* pparent = parent->_parent;
    parent->_parent = subL;
    subL->_right = parent;
    parent->_left = subLR;
    if (subLR)
      subLR->_parent = parent;
    if (parent == _root)
    {
      _root = subL;
      subL->_parent = nullptr;
    }
    else
    {
      if (pparent->_left == parent)
        pparent->_left = subL;
      else
        pparent->_right = subL; 
      subL->_parent = pparent;
    }
    subL->_bf = parent->_bf = 0;
  }

3、左右双旋

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

一般步骤：

1、先调用左单旋函数，对parent的左进行左单旋。

2、再调用右单旋函数，对parent进行右单旋。

3、根据原来的subLR的平衡因子的大小，来更新parent和subL的平衡因子。

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

4、右左双旋

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

一般步骤：

1、先调用右单旋函数，对parent的右进行右单旋。

2、再调用左单旋函数，对parent进行左单旋。

3、根据原来的subRL的平衡因子的大小，来更新parent和subR的平衡因子。

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

五、AVL树的验证

首先我们验证它是一棵二叉搜索树，如果一棵树的中序遍历的结果是有序的，那么他就是一棵二叉搜索树。用下面的代码：

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

一棵树在满足它是一棵二叉搜索树后，再去判断它是否是AVL树。

bool IsBalance()
  {
    return _IsBalance(_root);
  }
    int Height(Node* root)
  {
    if (root == nullptr)
      return 0;
    int leftHeight = Height(root->_left);
    int rightHeight = Height(root->_right);
    return max(leftHeight, rightHeight) + 1;
  }
  bool _IsBalance(Node* root)
  {
    if (root == nullptr)
      return true;
    int left = Height(root->_left);
    int right = Height(root->_right);
    int diff(right - left);
    if (diff != root->_bf)
    {
      cout << root->_kv.first << "平衡因子异常" << endl;
    }
    return abs(diff) < 2
      && _IsBalance(root->_left)
      && _IsBalance(root->_right);
  }

验证结果代码：

void test_AVLTree2()
{
  //测试双旋平衡因子的调节
  int b[] = { 4,2,6,1,3,515,7,16,14 };
  AVLTree<int, int> t;
  for (auto e : b)
  {
    t.insert(make_pair(e, e));
  }
  t.InOrder();
  cout << "IsBalance: " << t.IsBalance() << endl;
}

运行结果：

六、总代码

1、AVLTree.h

#pragma once
#include<iostream>
#include<cassert>
#include<cstdbool>
#include<algorithm>
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>
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->_left = cur;
    }
    else
    {
      parent->_right = cur;
    }
    cur->_parent = parent;
    //调整平衡
    // 1、更新平衡因子
    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)
      {
        // 说明parent 所在的子树不平衡了，需要旋转处理
        // 1、单旋
        if (parent->_bf == 2 && cur->_bf == 1) // 左单旋
        {
          RotateL(parent);
        }
        else if (parent->_bf == -2 && cur->_bf == -1) //右单旋
        {
          RotateR(parent);
        }
        //2、双旋
        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:
  void RotateL(Node* parent) //左单旋
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    Node* pparent = parent->_parent;
    subR->_left = parent;
    parent->_parent = subR;
    parent->_right = subRL;
    if (subRL)
      subRL->_parent = parent;
    if (parent == _root)
    {
      _root = subR;
      subR->_parent = nullptr;
    }
    else
    {
      if (pparent->_left == parent)
        pparent->_left = subR;
      else
        pparent->_right = subR;
      subR->_parent = pparent;
    }
    parent->_bf = subR->_bf = 0;
  }
  void RotateR(Node* parent) //右单旋
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    Node* pparent = parent->_parent;
    parent->_parent = subL;
    subL->_right = parent;
    parent->_left = subLR;
    if (subLR)
      subLR->_parent = parent;
    if (parent == _root)
    {
      _root = subL;
      subL->_parent = nullptr;
    }
    else
    {
      if (pparent->_left == parent)
        pparent->_left = subL;
      else
        pparent->_right = subL; 
      subL->_parent = pparent;
    }
    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);
    if (bf == -1)
    {
      parent->_bf = 1;
      subL->_bf = subLR->_bf = 0;
    }
    else if (bf == 1)
    {
      parent->_bf = 0;
      subL->_bf = -1;
      subLR->_bf = 0;
    }
    else if (bf == 0)
    {
      parent->_bf = subL->_bf = subLR->_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);
    if (bf == 1)
    {
      subRL->_bf = 0;
      parent->_bf = -1;
      subR->_bf = 0;
    }
    else if (bf == -1)
    {
      parent->_bf = 0;
      subR->_bf = 1;
      subRL->_bf = 0;
    }
    else if (bf == 0)
    {
      parent->_bf = 0;
      subR->_bf = 0;
      subRL->_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);
  }
  int Height(Node* root)
  {
    if (root == nullptr)
      return 0;
    int leftHeight = Height(root->_left);
    int rightHeight = Height(root->_right);
    return max(leftHeight, rightHeight) + 1;
  }
  bool _IsBalance(Node* root)
  {
    if (root == nullptr)
      return true;
    int left = Height(root->_left);
    int right = Height(root->_right);
    int diff(right - left);
    if (diff != root->_bf)
    {
      cout << root->_kv.first << "平衡因子异常" << endl;
    }
    return abs(diff) < 2
      && _IsBalance(root->_left)
      && _IsBalance(root->_right);
  }
private:
  Node* _root = nullptr;
};
void test_AVLTree1()
{
  int a[] = { 16,3,7,11,9,26,18,14,15 };
  AVLTree<int, int> t1;
  for (auto e : a)
  {
    t1.insert(make_pair(e, e));
  }
  t1.InOrder();
  cout << "IsBalance: " << t1.IsBalance() << endl;
}
void test_AVLTree2()
{
  //测试双旋平衡因子的调节
  int b[] = { 4,2,6,1,3,515,7,16,14 };
  AVLTree<int, int> t;
  for (auto e : b)
  {
    t.insert(make_pair(e, e));
  }
  cout << "IsBalance: " << t.IsBalance() << endl;
}

2、test.cpp

#include"AVLTree.h"
int main()
{
  test_AVLTree1();
  cout << "——————————————" << endl;
  test_AVLTree2();
  return 0;
}

运行结果：

dbln
目录
相关文章
南迦FourFish
|
缓存 监控 小程序
App性能测试揭秘（Android篇）
性能测试在移动测试领域一直是一个大难题，它最直观的表现是用户在前台使用 App 时的主观体验，然而决定体验优劣的背后，涉及到了许许多多的技术变迁。阅读此文，带你揭秘App性能测试。
南迦FourFish
5698 0
App性能测试揭秘（Android篇）
啦啦啦191
|
4月前
|
算法 Java 测试技术
适合新手小白的史上最强 Java 学习路线图从基础到进阶全程指南
本Java学习路线图涵盖从基础语法、面向对象、集合框架到进阶编程、JVM原理、Spring Boot框架，再到数据库操作与实战项目开发，内容系统全面，适合零基础新手入门与进阶提升，助力掌握Java全栈开发技能。
啦啦啦191
457 4
蚝油菜花
|
11月前
|
机器学习/深度学习 人工智能 搜索推荐
PaSa：字节跳动开源学术论文检索智能体，自动调用搜索引擎、浏览相关论文并追踪引文网络
PaSa 是字节跳动推出的基于强化学习的学术论文检索智能体，能够自动调用搜索引擎、阅读论文并追踪引文网络，帮助用户快速获取精准的学术文献。
蚝油菜花
804 15
弹性计算小冉
|
机器学习/深度学习 弹性计算 缓存
阿里云服务器经济型e实例与通用算力型u1实例对比分析与选择指南
在阿里云服务器的实例规格中，经济型e实例和通用算力型u1实例是很多个人和普通企业级用户常见的选择，经济型e实例与通用算力型u1实例的主要区别在于性能、应用场景及价格策略。本文将详细对比这两种实例的性能、应用场景及价格策略，以供参考。
弹性计算小冉
576 2
爱发白日梦的后端
|
Ubuntu Linux 数据安全/隐私保护
Windows就是Linux：WSL带来全新Linux开发体验
Windows就是Linux：WSL带来全新Linux开发体验
爱发白日梦的后端
1176 7
走在努力路上的自己
|
存储 编译器 BI
内存函数​（memcpy、memmove、memset、memcmp）
内存函数​（memcpy、memmove、memset、memcmp）
走在努力路上的自己
1242 6
ST小智
|
网络协议 Linux
嵌入式单片机开源的串口示波器实现方法
嵌入式单片机开源的串口示波器实现方法
ST小智
292 0
果果小师弟
|
Shell Go 开发工具
项目分享|小师弟手把手教你用蓝牙模块
嵌入式蓝牙串口通讯模块（简称蓝牙模块）具有两种工作模式：命令响应工作模式和自动连接工作模式。
果果小师弟
745 0
项目分享|小师弟手把手教你用蓝牙模块
南方者
|
Java
【学习笔记】【JAVA】Map.toString()后的字符串转换回Map类型
参考地址】：Map.toString()后字符串转换回Map
南方者
1152 0
【学习笔记】【JAVA】Map.toString()后的字符串转换回Map类型
狗尾巴呢
|
Kubernetes 网络协议 安全
本地k8s运行总结
本机上运行k8s的各种不同软件的对比和结构图
狗尾巴呢
836 0