当前位置:   article > 正文

红黑树 -- 平衡二叉树_红黑树转平衡二叉树

红黑树转平衡二叉树

  平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。

二叉树

  二叉树是每个节点最多有两个子树的树结构,如下图:
在这里插入图片描述
  二叉树有五种基本形态:

  • 二叉树可以是空集
  • 根节点可以有空的左右子树
  • 根节点只有一个左子树
  • 根节点只有一个右子树
  • 根节点可以有左右子树

如下图:
在这里插入图片描述

为什么需要平衡二叉树?

在这里插入图片描述
  为了避免上图这种情况的发生,我们希望可以有一种算法,将我们的不平衡的二叉树排序树转化为平衡二叉排序树。这样就可以让我们的二叉排序树结构实现最优化。

平衡因子

  该节点左子树的高度 - 该节点右子树的高度,即左右子树高度之差。

平衡二叉树旋转实现详解

 LL 型

在这里插入图片描述

 LR 型

在这里插入图片描述

 RR 型

在这里插入图片描述

 RL 型

在这里插入图片描述


 情况一:

在这里插入图片描述

 情况二:

在这里插入图片描述

 情况三:

在这里插入图片描述

 情况四:

在这里插入图片描述

 情况五:

在这里插入图片描述

 情况六:

在这里插入图片描述

 情况七:

在这里插入图片描述

 情况八:

在这里插入图片描述
  上图情况一,情况二,情况四的由于刚画,忘记了吧区别的子节点区分出来,画一次是真的麻烦,希望大家见谅,不过没有标出来,相信大家也能看出来,小编谢谢各位读者的谅解了。

  综上分析,二叉树转换成平衡二叉树的所有情况都给大家罗列出来了,图形画的着实难受,希望能帮到大家,如有疑问请留言!!!

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/知新_RL/article/detail/762510
推荐阅读
相关标签
  

闽ICP备14008679号