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

【c++】avl树

2024-06-26 67 发布于天津
版权
举报
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【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. 按照二叉搜索树的方式插入新节点
  2. 调整节点的平衡因子

更新平衡因子规则：

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++
关键词：
C++ avl
C++ avl树
嘎嘎旺
+关注
92文章
目录
打赏
0
0
0
0
16
分享
相关文章
RossyYan
|
2月前
|
存储 C++
【C++数据结构——树】哈夫曼树（头歌实践教学平台习题） 【合集】
【数据结构——树】哈夫曼树（头歌实践教学平台习题）【合集】目录 任务描述 相关知识 测试说明 我的通关代码： 测试结果：任务描述 本关任务：编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务，你需要掌握： 1.如何构建哈夫曼树， 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试： 测试输入： 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度） 预
RossyYan
72 14
【C++数据结构——树】哈夫曼树（头歌实践教学平台习题） 【合集】
RossyYan
|
2月前
|
Java C++
【C++数据结构——树】二叉树的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数（简单示例，手动构建） TreeNode*create
RossyYan
61 12
RossyYan
|
2月前
|
C++
【C++数据结构——树】二叉树的性质（头歌实践教学平台习题）【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树，并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括： 1. **定义二叉树节点结构体**：定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**：通过解析括号表示串，递归地构建二叉树的各个节点及其子树。 3. **使用示例**：展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**： - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后，提供了测试说明及通关代
RossyYan
60 10
RossyYan
|
2月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法（头歌教学实验平台习题） 【合集】
本任务旨在实现二叉树的遍历，包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义，并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑，以及层次遍历中队列的应用。最后提供了测试用例和预期输出，确保代码正确性。通过这些内容，帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
RossyYan
63 2
chian-ocean
|
4月前
|
存储 C++
【C++】AVL树
AVL树是一种自平衡二叉搜索树，由Georgy Adelson-Velsky和Evgenii Landis提出。它通过确保任意节点的两子树高度差不超过1来维持平衡，支持高效插入、删除和查找操作，时间复杂度为O(log n)。AVL树通过四种旋转操作（左旋、右旋、左-右旋、右-左旋）来恢复树的平衡状态，适用于需要频繁进行数据操作的场景。
chian-ocean
95 2
源码星辰
|
6月前
|
存储 C++
【C++】AVL树
AVL树是一种自平衡二叉搜索树：它以苏联科学家Georgy Adelson-Velsky和Evgenii Landis的名字命名。
源码星辰
54 2
枫叶丹4
|
7月前
|
C++ 容器
【C++航海王：追寻罗杰的编程之路】关联式容器的底层结构——AVL树
【C++航海王：追寻罗杰的编程之路】关联式容器的底层结构——AVL树
枫叶丹4
65 5
დ旧言~
|
8月前
|
C++
【C++】手撕AVL树（下）
【C++】手撕AVL树（下）
დ旧言~
76 1
Eternity._
|
8月前
|
算法 测试技术 C++
【C++高阶】掌握AVL树：构建与维护平衡二叉搜索树的艺术
【C++高阶】掌握AVL树：构建与维护平衡二叉搜索树的艺术
Eternity._
53 2
დ旧言~
|
8月前
|
Java C++ Python
【C++】手撕AVL树（上）
【C++】手撕AVL树（上）
დ旧言~
93 0

热门文章

最新文章

  • 1
    彻底摘明白 C++ 的动态内存分配原理
    5
  • 2
    【C++篇】深度解析类与对象（上）
    5
  • 3
    【c++】多态（多态的概念及实现、虚函数重写、纯虚函数和抽象类、虚函数表、多态的实现过程）
    42
  • 4
    【c++丨STL】priority_queue（优先级队列）的使用与模拟实现
    3
  • 5
    【c++】继承（继承的定义格式、赋值兼容转换、多继承、派生类默认成员函数规则、继承与友元、继承与静态成员）
    23
  • 6
    从集思录可转债数据探秘：Python与C++实现的移动平均算法应用
    4
  • 7
    【C++篇】深度解析类与对象（下）
    5
  • 8
    员工屏幕监控系统之 C++ 图像差分算法
    1
  • 9
    C++ String揭秘：写高效代码的关键
    4
  • 10
    基于 C++ 语言的迪杰斯特拉算法在局域网计算机管理中的应用剖析
    4
  • 1
    【c++丨STL】map/multimap的使用
    92
  • 2
    C/C++右移高位补0还是1？
    16
  • 3
    4步实现C++插件化编程，轻松实现功能定制与扩展（2）
    13
  • 4
    【c++丨STL】set/multiset的使用
    13
  • 5
    Dev-C++保姆级安装教程：Win10/Win11环境配置+避坑指南（附下载验证）
    42
  • 6
    【C++进阶】特殊类设计 && 单例模式
    35
  • 7
    【c++】多态（多态的概念及实现、虚函数重写、纯虚函数和抽象类、虚函数表、多态的实现过程）
    67
  • 8
    公司局域网管理中的哈希表查找优化 C++ 算法探究
    25
  • 9
    【c++】继承（继承的定义格式、赋值兼容转换、多继承、派生类默认成员函数规则、继承与友元、继承与静态成员）
    51
  • 10
    基于 C++ 语言的迪杰斯特拉算法在局域网计算机管理中的应用剖析
    38

    • 相关课程

    更多
  • C++ 入门教程开发文档

    • 相关电子书

    更多
  • 使用C++11开发PHP7扩展
  • GPON Class C++ SFP O;T Transce
  • GPON Class C++ SFP OLT Transce
    • 下一篇
    获取百炼API-KEY
    目录
    AI助理

    你好，我是AI助理

    可以解答问题、推荐解决方案等