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

运行结果：

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

一、AVLTree的引入

二、概念

1、概念

2、结点实现

3、整体框架

三、新节点的插入

1、插入

2、平衡因子更新规则

四、旋转调平衡

1、左单旋

2、右单旋

3、左右双旋

4、右左双旋

五、AVL树的验证

六、总代码

1、AVLTree.h

2、test.cpp

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

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

一、AVLTree的引入

二、概念

1、概念

2、结点实现

3、整体框架

三、新节点的插入

1、插入

2、平衡因子更新规则

四、旋转调平衡

1、左单旋

2、右单旋

3、左右双旋

4、右左双旋

五、AVL树的验证

六、总代码

1、AVLTree.h

2、test.cpp

热门文章

最新文章

相关电子书