数据·结构

简介: 数据·结构

1.概念

二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查

找元素相当于在顺序表中搜索元素,效率低下。

 

因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。

 

AVL树满足以下条件:

 

它的左右子树都是AVL树

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

比如:

 

 

 

2.定义

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

3.插入

那么如何用算法实现AVL树呢?

 

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

 

那么AVL树的插入过程可以分为两步:

 

按照二叉搜索树的方式插入新节点

调整节点的平衡因子

即第一步我们就把二叉搜索树的插入代码copy一份过来,进行一定的修改:

 

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;
    }
    else
    {
      parent->_left = cur;
    }
    cur->_parent = parent;
/**************************************/
 
    return true;
  }
 
private:
  Node* _root = nullptr;
};

 

然后第二步就是调整平衡因子,让左右子树高度之差(平衡因子)不超过1.

 

cur插入后,cur的父亲节点parent的平衡因子一定需要调整,再插入之前,parent的平衡因子分为三种情况:-1、0、1(插入之前一定满足AVL树规则),我们默认平衡因子=右子树高度-左子树高度,那么就分为以下两种情况:

 

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

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

如果parent的平衡因子发生了变化,那么就证明祖先有可能会受影响,就要向上继续更新。

 

这里我们同样需要分情况讨论:

 

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

 

如果parent的平衡因子为0,说明插入之前parent的平衡因子为正负1,插入后被调整成0,此时满足AVL树的性质,插入成功,且高度没有发生变化。

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

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

我们把上述逻辑转化成代码:

 

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;
    }
    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)
      {
        // 旋转处理
      }
      else
      {
        // 插入之前AVL树就有问题
        assert(false);
      }
    }
 
    return true;
  }
 
private:
  Node* _root = nullptr;
};

 

4.旋转

当节点的平衡因子为正负2时,则需要我们对该子树进行旋转处理。

 

那旋转最重要的是不能破坏我们二叉搜索树的特性,即旋转过后依旧满足左子树小于根,根小于右子树,那么怎么样进行旋转既能让二叉搜索树保持平衡,又能保持二叉搜索树的特性呢?

 

4.1右单旋

当新节点插入到较高左子树的左侧时(左左),我们需要进行『 右单旋』操作。

 

原理图与实现细节 

一般有以下这两种情况以及对应的旋转操作:

 

1)失衡节点的左孩子没有右孩子(subL无右孩子)

 

 

 

subL无右孩子时,parent直接旋转到subL的右分支即可,我们不需要考虑subL的右孩子放到哪。

 

2)失衡节点的左孩子有右孩子(subL有右孩子subLR)

 

 

 

subL有右孩子时,parent如果旋转到subL的右孩子处,需要将subL的右孩子subLR放到旋转过来的parent节点的左分支上即可。

 

体现到代码中如何判断什么时候进行右旋呢?

 

观察图像得知,当parent平衡因子为-2 && cur平衡因子为-1时,进行右旋。

 

观察发现,这样旋转后依然满足二叉搜索树的特性,且旋转后该树平衡了。

 

那么接下来我们要进行代码实现:

 

这里有几个需要注意的细节:

 

细节1:subL是否有右孩子subLR,如果有我们需要更新subLR的双亲节点。

细节2:parent是否是根节点,如果是根节点,我们需要更新根节点的值为subL;如果不是根节点,可能是某个节点的左子树,也可能是某个节点的右子树,我们需要更新subL的双亲节点为旋转之前parent双亲节点的左分支或右分支,所以我们需要提前保存parent的双亲结点ppnode。

细节3:旋转结束后更新parent与subL的平衡因子为0;

代码实现

void RotateR(Node* parent)
{
  Node* subL = parent->_left;
  Node* subLR = subL->_right;
 
  parent->_left = subLR;
  // 细节1
  if (subLR)
    subLR->_parent = parent;
 
  subL->_right = parent;
 
  Node* ppnode = parent->_parent;
  parent->_parent = subL;
 
  // 细节2
  if (parent == _root)
  {
    _root = subL;
    subL->_parent = nullptr;
  }
  else
  {
    if (ppnode->_left == parent)
    {
      ppnode->_left = subL;
    }
    else
    {
      ppnode->_right = subL;
    }
    subL->_parent = ppnode;
  }
 
  // 细节3
  subL->_bf = 0;
  parent->_bf = 0;
}

 

4.2左单旋

当新节点插入到较高右子树的右侧时(右右),我们需要进行『 左单旋』操作。

 

原理图与实现细节 

一般有以下这两种情况以及对应的旋转操作:

 

1)失衡节点的右孩子没有左孩子(subR无左孩子)

 

 

 

subR无左孩子时,parent直接旋转到subR的左分支即可,我们不需要考虑subR的左孩子放到哪。

 

2)失衡节点的右孩子有左孩子(subR有左孩子subRL)

 

 

 

subR有左孩子时,parent如果旋转到subR的左孩子处,需要将subR的左孩子subRL放到旋转过来的parent节点的右分支上即可。

 

体现到代码中如何判断什么时候进行左旋呢?

 

观察图像得知,当parent平衡因子为2 && cur平衡因子为1时,进行左旋。

 

观察发现,这样旋转后依然满足二叉搜索树的特性,且旋转后该树平衡了。

 

那么接下来我们要进行代码实现:

 

这里有几个需要注意的细节:

 

细节1:subR是否有左孩子subRL,如果有我们需要更新subRL的双亲节点。

细节2:parent是否是根节点,如果是根节点,我们需要更新根节点的值为subR;如果不是根节点,可能是某个节点的左子树,也可能是某个节点的右子树,我们需要更新subR的双亲节点为旋转之前parent双亲节点的左分支或右分支,所以我们需要提前保存parent的双亲结点ppnode。

细节3:旋转结束后更新parent与subR的平衡因子为0;

代码实现

void RotateL(Node* parent)
{
  Node* subR = parent->_right;
  Node* subRL = subR->_left;
 
  parent->_right = subRL;
  // 细节1
  if (subRL)
    subRL->_parent = parent;
 
  subR->_left = parent;
  Node* ppnode = parent->_parent;
  parent->_parent = subR;
 
  // 细节2
  if (parent == _root)
  {
    _root = subR;
    subR->_parent = nullptr;
  }
  else
  {
    if (ppnode->_left == parent)
    {
      ppnode->_left = subR;
    }
    else
    {
      ppnode->_right = subR;
    }
    subR->_parent = ppnode;
  }
 
  // 细节3
  parent->_bf = 0;
  subR->_bf = 0;
}

4.3先左旋再右旋

当新节点插入到较高左子树的右侧时(左右),仅使用左旋或右旋都无法使子树恢复平衡,所以我们需要进行『 先左旋再右旋』操作。

 

原理图与实现细节 

 

 

体现到代码中如何判断什么时候进行先左旋再右旋呢?

 

观察图像得知,当parent平衡因子为-2 && cur平衡因子为1时,进行先左旋再右旋。

 

观察发现,这样旋转后依然满足二叉搜索树的特性,且旋转后该树平衡了。

 

如果是下面这种树,你会发现会有两种不同的情况,即新插入的节点是subLR的左树还是右树,这个问题决定了最后parent和subL的平衡因子。

 

如果是右树,如图『 节点4』,最后旋转结束,parent的平衡因子为0,subL的平衡因子为-1;

如果是左树,如图『 节点2』,最后旋转结束,parent的平衡因子为1,subL的平衡因子为0;

 

 

所以根据上面的分析,我们需要知道新插入的节点是subLR的左树还是右树.

 

这个通过subLR的平衡因子就能判定:

 

如果为1,证明插入的节点是subLR的右树,即『 节点4』,所以最终subL的平衡因子为-1,parent的平衡因子为0;

如果为-1,证明插入的节点是subLR的左树,即『 节点2』,所以最终parent的平衡因子为1,subL的平衡因子为0;

如果为0,则为上上面图片的情况,最终parent和subL的平衡因子都为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)
  {
    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);
  }
}

4.4先右旋再左旋

当新节点插入到较高右子树的左侧时(右左),仅使用左旋或右旋都无法使子树恢复平衡,所以我们需要进行『 先右旋再左旋』操作。

 

原理图与实现细节 

 

 

体现到代码中如何判断什么时候进行先右旋再左旋呢?

 

观察图像得知,当parent平衡因子为2 && cur平衡因子为-1时,进行先右旋再左旋。

 

观察发现,这样旋转后依然满足二叉搜索树的特性,且旋转后该树平衡了。

 

如果是下面这种树,你会发现会有两种不同的情况,即新插入的节点是subRL的左树还是右树,这个问题决定了最后parent和subR的平衡因子。

 

如果是左树,如图『 节点2』,最后旋转结束,parent的平衡因子为0,subR的平衡因子为1;

如果是右树,如图『 节点4』,最后旋转结束,parent的平衡因子为-1,subR的平衡因子为0;

 

 

所以根据上面的分析,我们需要知道新插入的节点是subRL的左树还是右树.

 

这个通过subRL的平衡因子就能判定:

 

如果为-1,证明插入的节点是subRL的左树,即『 节点2』,所以最终subR的平衡因子为1,parent的平衡因子为0;

如果为1,证明插入的节点是subRL的右树,即『 节点4』,所以最终parent的平衡因子为-1,subR的平衡因子为0;

如果为0,则为上上面图片的情况,最终parent和subR的平衡因子都为0。

代码实现

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;
    subR->_bf = 1;
    parent->_bf = 0;
  }
  else if (bf == 1)
  {
    subRL->_bf = 0;
    subR->_bf = 0;
    parent->_bf = -1;
  }
  else if (bf == 0)
  {
    subRL->_bf = 0;
    subR->_bf = 0;
    parent->_bf = 0;
  }
  else
  {
    assert(false);
  }
}
 
4.5插入的完整代码 
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)
      {
        RotateL(parent);
      }
      else if (parent->_bf == -2 && cur->_bf == -1)
      {
        RotateR(parent);
      }
      else if (parent->_bf == -2 && cur->_bf == 1)
      {
        RotateLR(parent);
      }
      else
      {
        RotateRL(parent);
      }
      break;
    }
    else
    {
      // 插入之前AVL树就有问题
      assert(false);
    }
  }
 
  return true;
}

 

5.验证

5.1验证二叉搜索特性

如何验证一个平衡二叉搜索树是否健康呢?

 

那是否符合二叉搜索很简单,我们只需要中序遍历一遍看看是不是有序的即可。

 

中序遍历:

 

//中序遍历
void Inorder()
{
  _Inorder(_root);
}
//中序遍历子函数
void _Inorder(Node* root)
{
  if (root == nullptr)
    return;
  _Inorder(root->_left);
  cout << root->_kv.first << " ";
  _Inorder(root->_right);
}

创建子函数实现中序遍历的原因是:外部调用Inorder无法访问到private的根节点。

 

5.2验证平衡特性

验证平衡特性,我们可以获取左右子树的高度,然后利用这个高度计算差值,看看是否平衡即可。

 

首先是获取左右子树的高度:

 

int _Height(Node* root)
{
  if (root == nullptr)
    return 0;
 
  int leftHeight = _Height(root->_left);
  int rightHeight = _Height(root->_right);
    //返回左右子树高的那一个+1作为当前树的高度
  return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
 
int Height()
{
  return _Height(_root);
}

判断是否平衡:

 

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

 

观察上述验证平衡特性的代码,其实有很多重复计算,比如每次判断都需要重新计算该节点所有字数的高度,有没有什么办法保存这些高度呢?

 

其实我们可以采用后序遍历的思想,从最底下开始验证,这样就可以首先获取底层的高度,新增一个高度的参数,验证成功后利用引用将高度返回给上一层(输出型参数)。

 

bool _IsBalance(Node* root, int& height)
{
  if (root == nullptr)
  {
    height = 0;
    return true;
  }
 
  int leftHeight = 0, rightHeight = 0;
    //后序的思想
    //有一棵子树不平衡就返回false
  if (!_IsBalance(root->_left, leftHeight)
    || !_IsBalance(root->_right, rightHeight))
  {
    return false;
  }
 
  if (abs(rightHeight - leftHeight) >= 2)
  {
    cout << root->_kv.first << "不平衡" << endl;
    return false;
  }
 
  if (rightHeight - leftHeight != root->_bf)
  {
    cout << root->_kv.first << "平衡因子异常" << endl;
    return false;
  }
 
  height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
 
  return true;
}
 
bool IsBalance()
{
  int height = 0;
  return _IsBalance(_root, height);
}

————————————————

 

                           版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

                       

 

相关文章
|
存储 测试技术 开发工具
基础了解·创建第一个SwiftUI项目
基础了解·创建第一个SwiftUI项目
178 0
|
存储 C语言
《C和指针》读书笔记(第十章 结构和联合)(下)
《C和指针》读书笔记(第十章 结构和联合)(下)
|
存储 C语言 C++
《C和指针》读书笔记(第十章 结构和联合)(上)
《C和指针》读书笔记(第十章 结构和联合)(上)
CS专业408系列--数据结构基础01
CS专业408系列--数据结构基础01
119 0
|
存储 小程序 编译器
C · 进阶 | 深度剖析数据在内存中的存储
数学中我们常见到函数的概念。但是你了解`C语言`中的函数吗? - 维基百科中对函数的定义:==子程序== 在计算机科学中,子程序(英语:`Subroutine`, `procedure`, `function`, `routine`, `method`, `subprogram`, `callable unit`),是一个大型程序中的某部分代码, 由一个或多个语句块组 成。它负责完成某项特定任务,而且相较于其他代码,具备相对的独立性。一般会有输入参数并有返回值,提供对过程的封装和细节的隐藏。这些代码通常被集成为软件库
104 0
C · 进阶 | 深度剖析数据在内存中的存储
|
存储 大数据 索引
【python入门到精通】理解python中的内存·类型本质·以及连续储存以及顺链表的概念
【python入门到精通】理解python中的内存·类型本质·以及连续储存以及顺链表的概念
163 0
【python入门到精通】理解python中的内存·类型本质·以及连续储存以及顺链表的概念
|
知识图谱
欧几里德结构数据与 非欧几里德结构数据
欧几里德结构数据与 非欧几里德结构数据
536 0
欧几里德结构数据与 非欧几里德结构数据
|
SQL 算法 数据库
我的网站的结构说明
不知道大家有没有看懂这个图。这个是我的网站(不包括后台管理)的结构图。基本上和三层架构有些相似,但是有三个不同的地方:      一、 数据访问层。 1、数据访问层针对项目是通用,而针对数据库却是专用的。
825 0
|
存储 算法 索引