【c++】avl树-阿里云开发者社区

avl树的概念

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

它的左右子树都是AVL树

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

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在

O ( l o g 2 n ) O(log_2 n)O(log2n)，搜索时间复杂度O(l o g 2 n log_2 nlog2n)。

当插入，高度差不符合要求时，通过旋转变成avl树

avl树节点定义

template<class  K>
struct avltreenode
{
  avltreenode<K>* _left;
  avltreenode<K>* _right;
  avltreenode<K>* _parent;//使用三叉链，方便更新祖先的平衡因子
  K _key;
  int _bf;//平衡因子
  avltreenode(const K& key)
    :_left(nullptr)
    , _right(nullptr)
    ,_parent(nullptr)
    , _key(key)
    ,_bf(0)//新插入节点，因为没有左右子树，所以他的平衡因子是0
  {}
};

需要操作一个树，我们只需要知道该树的根节点即可

所以我们avl树的类成员变量为根节点地址

template<class  K>
class avltree
{
  typedef  avltreenode<K> node;
private:
  
  node* _root = nullptr;
};

avl树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么

AVL树的插入过程可以分为两步：

按照二叉搜索树的方式插入新节点
调整节点的平衡因子

更新平衡因子规则：

1.新增在右，父亲的_bf+1;(根据平衡因子定义)

2.新增在左，父亲的_bf-1;(根据平衡因子定义)

3.如果更新后，父亲的_bf=1/-1,这样会影响父亲祖先的平衡因子，所以要向上继续更新父亲祖先的平衡因子.

4.父亲的平衡因子更新后变为0后，不用往上更新平衡因子

5.父亲的平衡因子为2/-2时，需要通过旋转来维持avl树的平衡

插入操作和平衡二叉树一样

bool insert(const K& key)
  {
    if (_root == nullptr)
    {
      _root = new node(key);
      return true;
    }
    node* cur = _root;
    node* parent = nullptr;
    while (cur)
    {
      if (cur->_key > key)
      {
        parent = cur;
        cur = cur->_left;
      }
      else if (cur->_key < key)
      {
        parent = cur;
        cur = cur->_right;
      }
      else
      {
        return false;
      }
    }
    cur = new node(key);
    if (parent->_key > key)
    {
      parent->_left = cur;
    }
    else
    {
      parent->_right = cur;
    }
    cur->_parent = parent;//这里区别二叉搜索树，avl树需要记录插入节点的父节点
//后序操作处理平衡因子和旋转问题

平衡因子的处理

根据更新平衡因子的规则

根据规则1,2

if (cur == parent->_left)
      {
        parent->_bf--;
      }
      else
      {
        parent->_bf++;
      }

cur为新插入节点的指针

更新完成后，如果父亲的平衡因子==0，停止更新

if (parent->_bf == 0)
      {
        break;
      }

更新完成后，如果父亲的平衡因子为1/-1，需要继续往上更新，

else if (parent->_bf == 1 || parent->_bf == -1)
      {
        cur = cur->_parent;
        parent = parent->_parent;
      }

更新完成后，如果父亲的平衡因子为2/-2的话，需要进行旋转，，但是旋转的逻辑先不处理

else if (parent->_bf == -2 || parent->_bf == 2)
      {
        //旋转逻辑
        break;
      }

一直往上更新，直到父亲为空为止，说明更新父亲祖先的平衡因子已经更新完了

while (parent)
    {
      if (cur == parent->_left)
      {
        parent->_bf--;
      }
      else
      {
        parent->_bf++;
      }
      if (parent->_bf == 0)
      {
        break;
      }
      else if (parent->_bf == 1 || parent->_bf == -1)
      {
        cur = cur->_parent;
        parent = parent->_parent;
      }
      else if (parent->_bf == -2 || parent->_bf == 2)
      {
        
  
        break;
      }
    
    }

旋转逻辑

左旋：

右旋：

左旋处理：

先对需要旋转的结点命名，方便操作.

//由于旋转封装函数，我们会传入以哪个点旋转的指针
void spinleft(node* parent)//图中的30就是parent

命名

node* subr = parent->_right;
node* subrl = subr->_left;

此时只处理了旋转之后子节点的变化情况，父节点的未处理，导致结果如下

需要更新的父链有：

subr->_parent;
parent->_parent;
subrl->_parent;

由图可以得出：

subrl->_parent = parent;
parent->_parent = subr;

但是当h=0时，subrl是不存在的，所以

if (subrl)
subrl->_parent = parent;

这里的subr->_parent怎么更新

分两种情况：

1.parent就是根节点（更新前）

所以更新后subr就是根节点，

_root=subr; subr->_parent=nullptr;

2.parent不是根节点，所以我们要在改变parent->_parent之前需要记录一下，因为subr->_parent=parent->_parent;

node* ppnode = parent->_parent;//记录
parent->_parent = subr;//在改变之前

如果旋转前parent=ppnode->_left,

就有

ppnode->_left=subr;
subr->_parent=ppnode;

如果旋转前是parent=ppnode->_right;

就有

ppnode->_right=subr;
subr->_parent=ppnode;

最后需要更新一下subr和parent的平衡因子

subr->_bf=0;
parent->_bf=0;

左旋整体代码：

void spinleft(node* parent)
  {
    node* subr = parent->_right;
    node* subrl = subr->_left;
    
    parent->_right = subrl;
    if (subrl)
      subrl->_parent = parent;
    subr->_left = parent;
    node* ppnode = parent->_parent;
    parent->_parent = subr;
    
    if (ppnode == nullptr)
    {
      _root = subr;
      subr->_parent = nullptr;
    }
    else
    {
      if (ppnode->_left == parent)
      {
        ppnode->_left=subr;
        subr->_parent = ppnode;
      }
      else
      {
        ppnode->_right=subr;
        subr->_parent = ppnode;
      }
    }
  
  
  
    subr->_bf = 0;
    parent->_bf = 0;
  
  }

右旋：

void spinright(node* parent)
  {
  
    node* subl = parent->_left;
    node* sublr = subl->_right;
    
    parent->_left = sublr;
    if (sublr)
      sublr->_parent = parent;
    subl->_right = parent;
    node* ppnode = parent->_parent;
    parent->_parent = subl;
    if (ppnode == nullptr)
    {
      _root = subl;
      subl->_parent = nullptr;
    }
    else
    {
      if (ppnode->_left == parent)
      {
        ppnode->_left=subl;
        subl->_parent = ppnode;
      }
      else
      {
        ppnode->_right=subl;
        subl->_parent = ppnode;
      }
    }
  
  
  
    subl->_bf = 0;
    parent->_bf = 0;
  
  
  
  }

我们可以观察到，如果parent->_bf=2,cur->_bf=1
说明整体右边偏高，需要左旋

如果parent->_bf=-2,cur->_bf=-1
说明整体左边偏高，需要右旋

左右旋：

当parent->_bf=-2,cur->_bf=1

cur的右边高，而parent是左边高，此时我们需要对cur进行左旋，这样以来只变成了左边高，然后使用右旋即可

对30（cur）进行左旋，对parent(90)右旋

void spinlr(node* parent)
  { 
    spinleft(parent->_left);
    spinright(parent);
     
  }

如果只这样写的话，我们会发现平衡因子和图中是不同的

只会把

subl->_bf = 0;
  sublr->_bf = 0;
  parent->_bf = 0;

所以我们要分情况讨论：

我们应该按什么分呢？

这里我们需要按照插入结点后，sublr的平衡因子来区分

如果插入节点在sublr右边，sublr->_bf=1

得到的平衡因子的更新为

subl->_bf = -1;
sublr->_bf = 0;
parent->_bf = 0;

如果插入在sublr的左边，sublr->_bf=-1；

得到的平衡因子的更新为

subl->_bf = 0;
sublr->_bf = 0;
parent->_bf = 1;

如果sublr是新插入的结点的话，得到的平衡因子的更新为

subl->_bf = 0;
  sublr->_bf = 0;
  parent->_bf = 0;

因为在左右旋转之后会改变sublr的平衡因子，所以我们必须在插入结点之后，在旋转之前保存一下我们的sublr的平衡因子

int bf = subrl->_bf;

为了方便更新平衡因子，我们将旋转需要更新的平衡因子的结点标记

node* subr = parent->_right;
node* subrl = subr->_left;

左右旋整体代码：

void spinrl(node* parent)
  {
    node* subr = parent->_right;
    node* subrl = subr->_left;
    int bf = subrl->_bf;
  
  
    spinright(subr);
    spinleft(parent);
    if (bf == 1)
    {
      parent->_bf = -1;
      subr->_bf = 0;
      subrl->_bf = 0;
    }
    else if (bf == -1)
    {
    
      parent->_bf = 0;
      subr->_bf = 1;
      subrl->_bf = 0;
    
    }
    else
    {
      subr->_bf = 0;
      subrl->_bf = 0;
      parent->_bf = 0;
    }
  }

右左旋：

根据左右旋，以及右左旋的图，可以写出代码，思路基本和左右旋一样

void spinrl(node* parent)
  {
    node* subr = parent->_right;
    node* subrl = subr->_left;
    int bf = subrl->_bf;
  
  
    spinright(subr);
    spinleft(parent);
    if (bf == 1)
    {
      parent->_bf = -1;
      subr->_bf = 0;
      subrl->_bf = 0;
    }
    else if (bf == -1)
    {
    
      parent->_bf = 0;
      subr->_bf = 1;
      subrl->_bf = 0;
    
    }
    else
    {
      subr->_bf = 0;
      subrl->_bf = 0;
      parent->_bf = 0;
    }
  }

avl树的验证

需要检测每个节点左右子树的高度差<2,所以我们需要求树高度的函数

int treeheight(node* root)
  {
    if (root == nullptr)
      return 0;
    int leftheight = treeheight(root->_left);
    int rightheight = treeheight(root->_right);
    return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
  
  }

这个在二叉树那节有讲

平衡树验证：（这是力扣上的一个题，大家可以去刷一下）

平衡二叉树

bool _IsBalanceTree(node*root)
  {
    if (root == nullptr)
      return true;
    int leftheight = treeheight(root->_left);
    int rightheight = treeheight(root->_right);
      return (abs(rightheight - leftheight) < 2) && _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
  }

整体代码：

#include<iostream>
#include<string>
using namespace std;
template<class  K>
struct avltreenode
{
  avltreenode<K>* _left;
  avltreenode<K>* _right;
  avltreenode<K>* _parent;
  K _key;
  int _bf;
  avltreenode(const K& key)
    :_left(nullptr)
    , _right(nullptr)
    ,_parent(nullptr)
    , _key(key)
    ,_bf(0)
  {}
};
template<class  K>
class avltree
{
  typedef  avltreenode<K> node;
public:
  void spinleft(node* parent)
  {
    node* subr = parent->_right;
    node* subrl = subr->_left;
    
    parent->_right = subrl;
    if (subrl)
      subrl->_parent = parent;
    subr->_left = parent;
    node* ppnode = parent->_parent;
    parent->_parent = subr;
    
    if (ppnode == nullptr)
    {
      _root = subr;
      subr->_parent = nullptr;
    }
    else
    {
      if (ppnode->_left == parent)
      {
        ppnode->_left=subr;
        subr->_parent = ppnode;
      }
      else
      {
        ppnode->_right=subr;
        subr->_parent = ppnode;
      }
    }
  
  
  
    subr->_bf = 0;
    parent->_bf = 0;
  
  }
  void spinright(node* parent)
  {
  
    node* subl = parent->_left;
    node* sublr = subl->_right;
    
    parent->_left = sublr;
    if (sublr)
      sublr->_parent = parent;
    subl->_right = parent;
    node* ppnode = parent->_parent;
    parent->_parent = subl;
    if (ppnode == nullptr)
    {
      _root = subl;
      subl->_parent = nullptr;
    }
    else
    {
      if (ppnode->_left == parent)
      {
        ppnode->_left=subl;
        subl->_parent = ppnode;
      }
      else
      {
        ppnode->_right=subl;
        subl->_parent = ppnode;
      }
    }
  
  
  
    subl->_bf = 0;
    parent->_bf = 0;
  
  
  
  }
  void spinlr(node* parent)
  { 
    node* subl = parent->_left;
    node* sublr = subl->_right;
    int bf = sublr->_bf;
    spinleft(parent->_left);
    spinright(parent);
      
    if (bf == 1)
    {
      subl->_bf = -1;
      sublr->_bf = 0;
      parent->_bf = 0;
    }
    else if (bf == -1)
    {
      subl->_bf = 0;
      sublr->_bf = 0;
      parent->_bf = 1;
    }
    else
    {
      subl->_bf = 0;
      sublr->_bf = 0;
      parent->_bf = 0;
    }
        
  }
  void spinrl(node* parent)
  {
    node* subr = parent->_right;
    node* subrl = subr->_left;
    int bf = subrl->_bf;
  
  
    spinright(subr);
    spinleft(parent);
    if (bf == 1)
    {
      parent->_bf = -1;
      subr->_bf = 0;
      subrl->_bf = 0;
    }
    else if (bf == -1)
    {
    
      parent->_bf = 0;
      subr->_bf = 1;
      subrl->_bf = 0;
    
    }
    else
    {
      subr->_bf = 0;
      subrl->_bf = 0;
      parent->_bf = 0;
    }
  }
  bool insert(const K& key)
  {
    if (_root == nullptr)
    {
      _root = new node(key);
      return true;
    }
    node* cur = _root;
    node* parent = nullptr;
    while (cur)
    {
      if (cur->_key > key)
      {
        parent = cur;
        cur = cur->_left;
      }
      else if (cur->_key < key)
      {
        parent = cur;
        cur = cur->_right;
      }
      else
      {
        return false;
      }
    }
    cur = new node(key);
    if (parent->_key > key)
    {
      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 (parent->_bf == 1 || parent->_bf == -1)
      {
        cur = cur->_parent;
        parent = parent->_parent;
      }
      else if (parent->_bf == -2 || parent->_bf == 2)
      {
        if (parent->_bf == 2 && cur->_bf == 1)//左旋
        {
          spinleft(parent);
        }
        else if (parent->_bf == 2 && cur->_bf == -1)//先左旋后右旋
        {
          spinrl(parent);
          
        }
        else if (parent->_bf == -2 && cur->_bf == -1)//右旋
        {
           spinright(parent);
        }
        else//先右旋后左旋
        {
          spinlr(parent);
        }
        break;
      }
    
    }
    return true;
  }
   
  bool IsBalanceTree()
  {
  
    return _IsBalanceTree(_root);
  
  
  
  
  }
  void inorder()
  {
    _inorder(_root);
  }
  void _inorder(node* root)
  {
    if (root == nullptr)
      return;
    _inorder(root->_left);
    cout << root->_key << " :"<<root->_bf<<endl;
    _inorder(root->_right);
  }
  
private:
  int treeheight(node* root)
  {
    if (root == nullptr)
      return 0;
    int leftheight = treeheight(root->_left);
    int rightheight = treeheight(root->_right);
    return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
  
  }
  bool _IsBalanceTree(node*root)
  {
    if (root == nullptr)
      return true;
    int leftheight = treeheight(root->_left);
    int rightheight = treeheight(root->_right);
     
    return (abs(rightheight - leftheight) < 2) && _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
    
  }
  node* _root = nullptr;
};
int main()
{
  avltree<int>st;
  int a[] = //{ 16,3,1 };//测试右旋
            //{ 16,32,58 };//测试左旋
    //{ 8,3,1,10,6,4};//测试右左旋
    { 4, 2, 6, 1, 3, 5, 15, 7, 16,14};
    // { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
  //{ 8,3,1,10,6,4,7,14,13 };
  for (auto e : a)
  {
    st.insert(e);
    
    
  }
    st.inorder();
  int ret=st.IsBalanceTree();
  cout << endl;
  cout << ret;
}

【c++】avl树

avl树的概念

avl树的插入

旋转逻辑

左旋：

右旋：

左右旋：

右左旋：

avl树的验证

热门文章

最新文章

相关课程

相关电子书