【数据结构】—AVL树(C++实现)

简介: 【数据结构】—AVL树(C++实现)

一、前言          

     本文是基于二叉搜索树的知识前提下对于AVL树进行叙述的,主要叙述的方面在于AVL树的插入方面,因为AVL树同二叉搜索树的最大区别就在于插入的操作和删除操作,删除操作也是类似的,但是难就难在更新平衡因子,后续会补上。而对于其他的操作如:二叉搜索树的查找操作等等都是相似的,因此本文主要介绍AVL树的插入操作。

AVL树的概念

AVL树是一种自平衡二叉搜索树,它的特点是保证了每个节点的左右子树的高度差不超过1。它在插入和删除时会自动平衡,以保持树的高度始终在log N的范围内,从而保证了查找、插入、删除等操作的高效性。AVL树的名字来源于其发明者G.M.Adelson-Velsky和E.M.Landis的姓氏缩写。以下为一颗AVL树

  AVL树同二叉搜索树的异同

AVL树和二叉搜索树有很多相似之处,但也有许多不同之处。以下是它们的主要异同点:

相同点:

  1. 它们都是自平衡二叉搜索树,也就是说,在插入和删除节点后,它们能够保持一定的平衡性,从而保证查询操作的时间复杂度始终保持在O(logn)级别。
  2. 它们都遵循二叉搜索树的基本性质,即左子树中的所有节点都小于根节点,右子树中的所有节点都大于根节点。

不同点:

  1. 在AVL树中,除了左右子树高度差不能超过1之外,每个叶子节点还必须在左右子树的高度之间,而在二叉搜索树中则没有这样的限制。(AVL中通常定义一个bf值(balance factor)用于记录节点左右子树的高度差
  2. 在AVL树中,任何路径上的节点数差异不能超过1,而在二叉搜索树中则没有这样的要求。
  3. 在插入和删除节点后,AVL树需要进行更多的旋转操作来恢复平衡,而二叉搜索树则不需要这样的步骤。
  4. AVL树更适合于查找操作,因为它通过严格的平衡性保证了查询操作的效率,而二叉搜索树更适合于插入和删除操作,因为它可以通过简单的旋转操作来快速调整树结构。

二、AVL树的实现

节点的定义

通过KV模型定义AVL树节点,定义三叉链的结构储存父节点以及左右子树节点的地址,定义了bf(平衡因子)用于记录节点右子树与左子树之差(右-左),通过构造函数初始化列表,特别要将bf置为0,如果不置0后续操作可能会出错(别问作者怎么知道的(〃>皿<))。

vtemplate<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)
  {}
};

AVL树的初始化定义

// AVL: 二叉搜索树 + 平衡因子的限制
template<class K, class V>
class AVLTree
{
  typedef AVLTreeNode<K, V> Node;
public:
    // 在AVL树中插入节点
  bool Insert(const pair<K, V>& kv);
    // AVL树的验证
    bool _IsBalance(Node* root)
    {
        return _IsBalance(_root);
    }
private:
    // 右单旋
  void RotateR(Node* parent);
    // 左单旋
  void RotateL(Node* parent);
    // 右左双旋
  void RotateRL(Node* parent);
    // 左右双旋
  void RotateLR(Node* parent);
    // 求高度
  int _Height(Node* root );
    // 根据AVL树的概念验证pRoot是否为有效的AVL树
    bool _IsBalance(Node* root);
private:
  Node* _root = nullptr;
};

AVL树的插入(重点及难点!!!)

插入大致步骤

AVL树的插入操作可以分为以下几步:

  1. 向AVL树中插入一个新节点,首先找到该节点的位置。这可以通过比较新节点的值与当前节点的值来完成,直到找到一个空位置或者到达一个叶子节点为止。按照大往左,小往右,相等返回false的规则
  2. 依次向下搜索直到找到相应的位置,就将新节点插入到这个位置,并且更新该节点的父节点和兄弟节点的指针。就将新节点插入到这个位置,然后向上更新节点的bf值。
  3. 插入完成后,需要检查新插入的节点是否破坏了AVL树的平衡性。如果破坏了平衡性,就需要执行一系列旋转操作来修复不平衡状态。具体来说,如果新插入的节点使得某个分支的深度增加了一级,那么可以执行一次相应的旋转操作:左旋、右旋、左右旋、右左旋,最后按要求更新各个节点的bf值。

以上就是AVL树的插入操作步骤。需要注意的是,每次插入操作都需要按照这些步骤来进行,才能保证AVL树的平衡性。

根据规则找节点

如果_root为空(即空树)则新建节点并返回。比较节点的值,如果插入节点大则往右子树遍历,小则往左子树遍历,如果与节点值相同则无需插入直接返回。后续找到相应的位置后就可跳出循环进行下一步操作。

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;
  }
}
插入并且链接节点

更新节点信息,新插入节点的_parent值,以及父节点链接他在左子树还是右子树的判断,链入AVL树中。

    cur = new Node(kv);
    if (parent->_kv.first < kv.first)
    {
      parent->_right = cur;
      cur->_parent = parent;
    }
    else
    {
      parent->_left = cur;
      cur->_parent = parent;
    }
向上更新bf(平衡因子)的值

在插入之前,parent的平衡因子分为三种情况:-1,0, 1, 分以下两种情况:

       1. 如果cur插入到parent的左侧,只需给parent的平衡因子-1即可。

       2. 如果cur插入到parent的右侧,只需给parent的平衡因子+1即可。

此时:parent的平衡因子可能有三种情况:0,正负1, 正负2

       1. 如果parent的平衡因子为0,说明插入之前parent的平衡因子为正负1,插入后被调整成0,此时满足AVL树的性质,插入成功。

       2. 如果parent的平衡因子为正负1,说明插入前parent的平衡因子一定为0,插入后被更新成正负1,此时以parent为根的树的高度增加,需要继续向上更新。

       3. 如果parent的平衡因子为正负2,则parent的平衡因子违反平衡树的性质,需要对其进行旋转处理。

while (parent)
{
  if (cur == parent->_left)//根据在左还是右改变bf值
  {
    parent->_bf--;
  }
  else
  {
    parent->_bf++;
  }
  if (parent->_bf == 0)//bf=0则向上都无需变化
  {
    break;
  }
  else if (parent->_bf == 1 || parent->_bf == -1)//bf变化向上遍历改变bf值
  {
    cur = parent;
    parent = parent->_parent;
  }
  else if (parent->_bf == 2 || parent->_bf == -2)//破坏了bf值需要-1<=bf<=1的区间,需要旋转矫正
  {
    if (parent->_bf == 2 && cur->_bf == 1)//左旋情况
    {
      RotateL(parent);
    }
    else if (parent->_bf == -2 && cur->_bf == -1)//右旋情况
    {
      RotateR(parent);
    }
    else if (parent->_bf == 2 && cur->_bf == -1)//右旋再左旋情况
    {
      RotateRL(parent);
    }
    else if (parent->_bf == -2 && cur->_bf == 1)//左旋再右旋情况
    {
      RotateLR(parent);
    }
    // 1、旋转让这颗子树平衡了
    // 2、旋转降低了这颗子树的高度,恢复到跟插入前一样的高度,所以对上一层没有影响,不用继续更新
    break;
  }
  else
  {
    assert(false);//其它情况的bf值表示这颗avl树本身就有问题
  }
}

左单旋

由于我们每次插入都会进行调整操作,对此AVL树在新的节点插入前都是合法的,也就是说bf值只会在-1~1之间波动。 当 parent->_bf == 2 && cur->_bf == 1时,我们需要进行左单旋的操作以确保AVL树的合法性(也就是当父节点的右子树高时需要进行左单旋),以下为对此以下为大致的操作图:

 详细旋转过程:

对于左单旋操作,我们需要先记录几个节点,分别如下为parent、subR、subRL,因为我们主要是改变这三个的位置。在旋转完成后我们也通过图清晰可见,parent和subR的bf值都是0。

  void RotateL(Node* parent)//左旋
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    parent->_right = subRL;
    subR->_left = parent;
    Node* parentParent = parent->_parent;
    parent->_parent = subR;
    if (subRL)//判断节点subRL是否为空,防止出错
      subRL->_parent = parent;
    if (_root == parent)
    {
      _root = subR;
      subR->_parent = nullptr;
    }
    else
    {
      if (parentParent->_left == parent)
      {
        parentParent->_left = subR;
      }
      else
      {
        parentParent->_right = subR;
      }
      subR->_parent = parentParent;
    }
    parent->_bf = subR->_bf = 0;
  }

右单旋

  对于右单旋,操作同左单旋相似,也是需要记录三个节点:parent、subL、subLR,只不过此时我们是向右旋转。当 parent->_bf == -2 && cur->_bf == -1时,我们需要进行右单旋的操作以确保AVL树的合法性(也就是当父节点的左子树高时需要进行右单旋)。在旋转完成后我们也通过图清晰可见,parent和subR的bf值都是0。以下为对此以下为大致的操作图:

  void RotateR(Node* parent)//右旋
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    parent->_left = subLR;
    if (subLR)
      subLR->_parent = parent;
    subL->_right = parent;
    Node* parentParent = parent->_parent;
    parent->_parent = subL;
    if (_root == parent)
    {
      _root = subL;
      subL->_parent = nullptr;
    }
    else
    {
      if (parentParent->_left == parent)
      {
        parentParent->_left = subL;
      }
      else
      {
        parentParent->_right = subL;
      }
      subL->_parent = parentParent;
    }
    parent->_bf = subL->_bf = 0;
  }

左右双旋

当parent->_bf == -2 && cur->_bf == 1时,也就意味着我们的插入操作在如下的b的位置,插入后的图为第二张图,对此我们仅仅只进行一次旋转是远远不够的,如下第三张图为以30为父节点(即subL)只进行了一次左单旋后所变化的图,如果我们仔细观察可以发现这非常符合需要右单旋的操作,因此,此时我们以90为父节点再进行一次右单旋操作。 当然双旋最重要的其实是bf值的确定,我们需要根据最开始的subLR的bf值来确定。

当bf == 0,则subLR自己就是新增因此

           parent->_bf = subL->_bf = subLR->_bf = 0;

当bf==-1,则subLR的左子树新增

          parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;

当bf==1,则subLR的右子树新增

          subL->_bf = -1;parent->_bf = 0;subLR->_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 == 0)
    {
      // subLR自己就是新增
      parent->_bf = subL->_bf = subLR->_bf = 0;
    }
    else if (bf == -1)
    {
      // subLR的左子树新增
      parent->_bf = 1;
      subL->_bf = 0;
      subLR->_bf = 0;
    }
    else if (bf == 1)
    {
      // subLR的右子树新增
      subL->_bf = -1;
      parent->_bf = 0;
      subLR->_bf = 0;
    }
    else
    {
      assert(false);
    }
  }

右左双旋

当parent->_bf == 2 && cur->_bf == -1时,我们需要进行右左双旋操作,当然同左右双旋一样,只进行一次旋转肯定是不够的,我们也可以猜到先对subR作为一次父节点进行右单旋,在再对parent进行左单旋。

当然双旋最重要的其实是bf值的确定,我们需要根据最开始的subRL的bf值来确定。

当bf == 0,则subRL自己就是新增

           parent->_bf = subR->_bf = subRL->_bf = 0;

当bf==-1,则subRL的左子树新增

           parent->_bf = 0;subRL->_bf = 0;subR->_bf = 1;

当bf==1,则subRL的右子树新增

           parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;

  void RotateRL(Node* parent)
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    int bf = subRL->_bf;
    RotateR(parent->_right);
    RotateL(parent);
    if (bf == 0)
    {
      // subRL自己就是新增
      parent->_bf = subR->_bf = subRL->_bf = 0;
    }
    else if (bf == -1)
    {
      // subRL的左子树新增
      parent->_bf = 0;
      subRL->_bf = 0;
      subR->_bf = 1;
    }
    else if (bf == 1)
    {
      // subRL的右子树新增
      parent->_bf = -1;
      subRL->_bf = 0;
      subR->_bf = 0;
    }
    else
    {
      assert(false);
    }
  }

判断是否符合AVL树

 主要运用递归的思想,不多阐述,实在不明白可以画递归展开图。

    int _Height(Node* root)
    {
      if (root == nullptr)
        return 0;
      int leftHeight = _Height(root->_left);
      int rightHeight = _Height(root->_right);
      return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }
    bool _IsBalance(Node* root)
    {
      if (root == nullptr)
        return true;
      int leftHeight = _Height(root->_left);
      int rightHeight = _Height(root->_right);
      if (rightHeight - leftHeight != root->_bf)
      {
        cout << root->_kv.first << "平衡因子异常" << endl;
        return false;
      }
      return abs(rightHeight - leftHeight) < 2
        && _IsBalance(root->_left)
        && _IsBalance(root->_right);
    }

三、整体代码

#pragma once
#include<iostream>
#include<assert.h>
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>
class 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->_right = cur;
      cur->_parent = parent;
    }
    else
    {
      parent->_left = cur;
      cur->_parent = parent;
    }
    while (parent)
    {
      if (cur == parent->_left)//根据在左还是右改变bf值
      {
        parent->_bf--;
      }
      else
      {
        parent->_bf++;
      }
      if (parent->_bf == 0)//bf=0则向上都无需变化
      {
        break;
      }
      else if (parent->_bf == 1 || parent->_bf == -1)//bf变化向上遍历改变bf值
      {
        cur = parent;
        parent = parent->_parent;
      }
      else if (parent->_bf == 2 || parent->_bf == -2)//破坏了bf值需要-1<=bf<=1的区间,需要旋转矫正
      {
        if (parent->_bf == 2 && cur->_bf == 1)//左旋情况
        {
          RotateL(parent);
        }
        else if (parent->_bf == -2 && cur->_bf == -1)//右旋情况
        {
          RotateR(parent);
        }
        else if (parent->_bf == 2 && cur->_bf == -1)//右旋再左旋情况
        {
          RotateRL(parent);
        }
        else if (parent->_bf == -2 && cur->_bf == 1)//左旋再右旋情况
        {
          RotateLR(parent);
        }
        // 1、旋转让这颗子树平衡了
        // 2、旋转降低了这颗子树的高度,恢复到跟插入前一样的高度,所以对上一层没有影响,不用继续更新
        break;
      }
      else
      {
        assert(false);//其它情况的bf值表示这颗avl树本身就有问题
      }
    }
    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;
      parent->_right = subRL;
      subR->_left = parent;
      Node* parentParent = parent->_parent;
      parent->_parent = subR;
      if (subRL)//判断节点subRL是否为空,防止出错
        subRL->_parent = parent;
      if (_root == parent)
      {
        _root = subR;
        subR->_parent = nullptr;
      }
      else
      {
        if (parentParent->_left == parent)//链接subR给父节点的父节点,需要判断是在左子树还是右子树
        {
          parentParent->_left = subR;
        }
        else
        {
          parentParent->_right = subR;
        }
        subR->_parent = parentParent;
      }
      parent->_bf = subR->_bf = 0;
    }
    void RotateR(Node* parent)//右旋
    {
      Node* subL = parent->_left;
      Node* subLR = subL->_right;
      parent->_left = subLR;
      if (subLR)
        subLR->_parent = parent;
      subL->_right = parent;
      Node* parentParent = parent->_parent;
      parent->_parent = subL;
      if (_root == parent)
      {
        _root = subL;
        subL->_parent = nullptr;
      }
      else
      {
        if (parentParent->_left == parent)
        {
          parentParent->_left = subL;
        }
        else
        {
          parentParent->_right = subL;
        }
        subL->_parent = parentParent;
      }
      parent->_bf = subL->_bf = 0;
    }
    void RotateRL(Node* parent)
    {
      Node* subR = parent->_right;
      Node* subRL = subR->_left;
      int bf = subRL->_bf;
      RotateR(parent->_right);
      RotateL(parent);
      if (bf == 0)
      {
        // subRL自己就是新增
        parent->_bf = subR->_bf = subRL->_bf = 0;
      }
      else if (bf == -1)
      {
        // subRL的左子树新增
        parent->_bf = 0;
        subRL->_bf = 0;
        subR->_bf = 1;
      }
      else if (bf == 1)
      {
        // subRL的右子树新增
        parent->_bf = -1;
        subRL->_bf = 0;
        subR->_bf = 0;
      }
      else
      {
        assert(false);
      }
    }
    void RotateLR(Node* parent)
    {
      //...
      Node* subL = parent->_left;
      Node* subLR = subL->_right;
      int bf = subLR->_bf;
      RotateL(parent->_left);
      RotateR(parent);
      if (bf == 0)
      {
        // subLR自己就是新增
        parent->_bf = subL->_bf = subLR->_bf = 0;
      }
      else if (bf == -1)
      {
        // subLR的左子树新增
        parent->_bf = 1;
        subL->_bf = 0;
        subLR->_bf = 0;
      }
      else if (bf == 1)
      {
        // subLR的右子树新增
        subL->_bf = -1;
        parent->_bf = 0;
        subLR->_bf = 0;
      }
      else
      {
        assert(false);
      }
    }
    void _InOrder(Node* root)
    {
      if (root == nullptr)
        return;
      _InOrder(root->_left);
      cout << root->_kv.first << " ";
      _InOrder(root->_right);
    }
    int _Height(Node* root)
    {
      if (root == nullptr)
        return 0;
      int leftHeight = _Height(root->_left);
      int rightHeight = _Height(root->_right);
      return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }
    bool _IsBalance(Node* root)
    {
      if (root == nullptr)
        return true;
      int leftHeight = _Height(root->_left);
      int rightHeight = _Height(root->_right);
      if (rightHeight - leftHeight != root->_bf)
      {
        cout << root->_kv.first << "平衡因子异常" << endl;
        return false;
      }
      return abs(rightHeight - leftHeight) < 2
        && _IsBalance(root->_left)
        && _IsBalance(root->_right);
    }
  private:
    Node* _root = nullptr;
};

感谢你耐心的看到这里ღ( ´・ᴗ・` )比心,如有哪里有错误请踢一脚作者o(╥﹏╥)o! 

相关文章
|
28天前
|
存储 算法 C++
【C/C++ 数据结构 】无向图和有向图的差异
【C/C++ 数据结构 】无向图和有向图的差异
25 0
|
6天前
|
算法 DataX
二叉树(中)+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”
二叉树(中)+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”
|
27天前
|
存储 算法 程序员
【数据结构】【版本2.0】【树形深渊】——二叉树入侵
【数据结构】【版本2.0】【树形深渊】——二叉树入侵
|
28天前
|
算法 C++ 开发者
【C/C++ 数据结构 】二叉树基本性质:具有n个结点的完全二叉树的深度为[log2n]+1或者[log2(n+1)]...
【C/C++ 数据结构 】二叉树基本性质:具有n个结点的完全二叉树的深度为[log2n]+1或者[log2(n+1)]...
11 0
|
28天前
|
存储 算法 数据库
【C/C++ 数据结构 】树的 四种表示方法
【C/C++ 数据结构 】树的 四种表示方法
30 0
|
28天前
|
存储 算法 C语言
【C/C++ 数据结构 树】探索C/C++中的二叉树:从理论到实践
【C/C++ 数据结构 树】探索C/C++中的二叉树:从理论到实践
60 0
|
15天前
|
消息中间件 存储 搜索推荐
深入理解栈和队列(二):队列
深入理解栈和队列(二):队列
29 0
|
1月前
【栈】数据结构栈的实现
【栈】数据结构栈的实现
|
1月前
|
存储
数据结构--栈和队列
数据结构--栈和队列
|
1月前
|
存储 算法 数据处理
数据结构从入门到精通——栈
栈,作为一种后进先出(LIFO)的数据结构,在计算机科学中扮演着重要的角色。它的特性使得它在处理函数调用、括号匹配、表达式求值等问题时具有得天独厚的优势。然而,如果我们跳出传统思维的束缚,会发现栈的用途远不止于此。
57 0

热门文章

最新文章