C++进阶--AVL树

简介: C++进阶--AVL树

概念

AVL树是一种自平衡的二叉查找树,其中任何结点的两个子树的高度最大差别为1,因此也被称为高度平衡树。AVL树的特点是在进行插入和删除操作后,会通过旋转的方式来重新平衡树的结构。

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

  • 它的左右子树都是AVL树;
  • 左右子树高度差的绝对值不超过1(0、1、-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树的结点定义

template<class K,class V>
struct AVLTreeNode
{
  AVLTreeNode<K, V>* _left;
  AVLTreeNode<K, V>* _right;
  AVLTreeNode<K, V>* _parent;
  int _bf;
  pair<K, V> _kv;
  AVLTreeNode(const pair<K, V>& kv)
    :_left(nullptr)
    ,_right(nullptr)
    ,_parent(nullptr)
    ,_bf(0)
    ,_kv(kv)
  {}
};

AVL树的插入

搜索二叉树链接

对于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->_right = cur;
    }
    else
    {
      parent->_left = 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)
        {
          RoteteL(parent);
        }
        else if (parent->_bf == -2 && cur->_bf == -1)
        {
          RorareR(parent);
        }
        else if (parent->_bf == -2 && cur->_bf == 1)
        {
          RotateLR(parent);
        }
        else 
        {
          RotateRL(parent);
        }
        break;
      }
      else
      {
        assert(false);
      }
    }
    
  }

AVL树的旋转

当插入一个结点时,可能会使原本的父节点的平衡因子失去平衡,这时,就需要通过调整,来进行重新平衡;主要有4种情况:

左单旋

void RoteteL(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)
    {
      if (ppnode->_left == parent)
      {
        ppnode->_left = subR;
      }
      else
      {
        ppnode->_right = subR;
      }
      subR->_parent = ppnode;
    }
    else
    {
      _root = subR;
      subR->_parent = __nullptr;
    }
    parent->_bf = 0;
    subR->_bf = 0;
  }

右单旋

void RorareR(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 (parent == _root)
    {
      _root = subL;
      subL->_parent = nullptr;
    }
    else
    {
      if (ppnode->_left == parent)
      {
        ppnode->_left = subL;
      }
      else
      {
        ppnode->_right = subL;
      }
      subL->_parent = ppnode;
    }
    subL->_bf = 0;
    parent->_bf = 0;
  }

左右旋

void RotateLR(Node* parent)
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    int bf = subLR->_bf;
    RoteteL(parent->_left);
    RorareR(parent);
    if (bf == -1)
    {
      subLR->_bf = 0;
      subL->_bf = 0;
      parent->_bf = 1;
    }
    else if (bf == 1)
    {
      subLR->_bf = 0;
      subL->_bf = -1;
      parent->_bf = 0;
    }
    else if (bf == 0)
    {
      subLR->_bf = 0;
      subL->_bf = 0;
      parent->_bf = 0;
    }
    else
    {
      assert(false);
    }
  }

右左旋

void RotateRL(Node* parent)
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    int bf = subRL->_bf;
    RorareR(subR);
    RoteteL(parent);
    if (bf == 1)
    {
      subRL->_bf = 0;
      subR->_bf = 0;
      parent->_bf = -1;
    }
    else if (bf == -1)
    {
      subR->_bf = 1;
      subRL->_bf = 0;
      parent->_bf = 0;
    }
    else if (bf == 0)
    {
      subR->_bf = 0;
      subRL->_bf = 0;
      parent->_bf = 0;
    }
    else
    {
      assert(false);
    }
  }

旋转验证

AVL树的验证

bool _IsBanlance(Node* root,int& height)
  {
    if (root == nullptr)
    {
      return true;
    }
    //计算左右子树高度差
    int leftHeight = 0, rightHeight = 0;
    if (!_IsBanlance(root->_left, leftHeight) || !_IsBanlance(root->_right, rightHeight))
    {
      return false;
    }
    if (abs(rightHeight - leftHeight) >= 2)
    {
      cout << "不平衡" << endl;
      return false;
    }
    if (rightHeight - leftHeight != root->_bf)
    {
      cout << "平衡因子异常" << endl;
      return false;
    }
    height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    return true;
  }
  bool IsBanlance()
  {
    int height = 0;
    return _IsBanlance(_root,height);
  }

观察验证:

AVL树的查找

AVL树的性能

AVL树的性能主要体现下面几个方面:

  • 平衡性:AVL树保持了高度的平衡,即任何结点的两个子树的高度差不超过1.这就保证了树的深度相对较小,使得查找、插入、删除操作的平均时间复杂度为O(logN);
  • 查找操作:由于AVL树是搜索二叉树的变种,它具有搜索二叉树的性质,可以在O(logN)的时间复杂度内进行查找操作。
  • 插入和删除操作:当进行插入或删除时,AVL树会根据需要进行平衡调整,以保持树的平衡性。则可能需要通过旋转来重新平衡树的结构。但这个旋转次数影响不大,插入和删除操作的时间复杂度为O(logN);
  • 内存消耗:AVL树相比于其他平衡二叉树(如红黑树)可能会消耗更多的内存空间,因为每个结点需要存储额外的平衡因子信息。平衡因子通常由一个整数表示;但在大多数应用场景中,AVL树的性能仍然是非常好的。
相关文章
|
2月前
|
存储 C++
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
68 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
2月前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
59 12
|
2月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
53 10
|
2月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
55 2
|
4月前
|
存储 C++
【C++】AVL树
AVL树是一种自平衡二叉搜索树,由Georgy Adelson-Velsky和Evgenii Landis提出。它通过确保任意节点的两子树高度差不超过1来维持平衡,支持高效插入、删除和查找操作,时间复杂度为O(log n)。AVL树通过四种旋转操作(左旋、右旋、左-右旋、右-左旋)来恢复树的平衡状态,适用于需要频繁进行数据操作的场景。
90 2
|
6月前
|
存储 C++
【C++】AVL树
AVL树是一种自平衡二叉搜索树:它以苏联科学家Georgy Adelson-Velsky和Evgenii Landis的名字命名。
52 2
|
7月前
|
C++ 容器
【C++航海王:追寻罗杰的编程之路】关联式容器的底层结构——AVL树
【C++航海王:追寻罗杰的编程之路】关联式容器的底层结构——AVL树
63 5
|
8月前
|
C++
【C++】手撕AVL树(下)
【C++】手撕AVL树(下)
71 1
|
8月前
|
算法 测试技术 C++
【C++高阶】掌握AVL树:构建与维护平衡二叉搜索树的艺术
【C++高阶】掌握AVL树:构建与维护平衡二叉搜索树的艺术
52 2
|
8月前
|
Java C++ Python
【C++】手撕AVL树(上)
【C++】手撕AVL树(上)
80 0