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

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

2024-01-17 66
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 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
目录
相关文章
爱学习的鱼佬
|
存储 算法 C++
一篇文章教会你什么是高度平衡二叉搜索(AVL)树（上）
AVL树的概念 AVL树（Adelson-Velsky and Landis Tree）是计算机科学中最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此
爱学习的鱼佬
86 0
椰椰椰耶
|
1月前
【数据结构】翻转、平衡、对称二叉树，最大深度、判断两棵树是否相等、另一棵树的子树
【数据结构】翻转、平衡、对称二叉树，最大深度、判断两棵树是否相等、另一棵树的子树
椰椰椰耶
43 0
wjq++
|
5月前
深入解析AVL树：高效实现二叉平衡搜索树（2）
深入解析AVL树：高效实现二叉平衡搜索树
wjq++
25 1
wjq++
|
5月前
|
存储
深入解析AVL树：高效实现二叉平衡搜索树
深入解析AVL树：高效实现二叉平衡搜索树
wjq++
24 1
行十万里人生
|
5月前
平衡二叉搜索树（AVL）旋转
平衡二叉搜索树（AVL）旋转
行十万里人生
19 0
三哥一起来编程
|
人工智能 BI
LeetCode-310 最小高度树
LeetCode-310 最小高度树
三哥一起来编程
63 0
三哥一起来编程
LeetCode-1664 生成平衡数组的方案树
LeetCode-1664 生成平衡数组的方案树
三哥一起来编程
54 0
想当开心果哦
|
6月前
|
调度
红黑树（平衡）
红黑树（平衡）
想当开心果哦
49 0
爱学习的鱼佬
|
存储 测试技术
一篇文章教会你什么是高度平衡二叉搜索(AVL)树（下）
3.3 新节点插入较高左子树的右侧—左右：先左单旋再右单旋
爱学习的鱼佬
71 0
我的代码爱吃辣
|
算法 C++
AVL——平衡搜索树
AVL树是对二叉搜索树的严格高度控制，所以AVL树的搜索效率很高，但是这是需要付出很大的代价的，要维护父亲指针，和平衡因子。
我的代码爱吃辣
76 0