侧边栏壁纸
博主头像
coydone博主等级

记录学习,分享生活的个人站点

  • 累计撰写 306 篇文章
  • 累计创建 51 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

红黑树

coydone
2021-06-12 / 0 评论 / 0 点赞 / 381 阅读 / 2,512 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

红黑树的由来

BST存在问题

BST(二叉查找树)存在的问题是,树在插入的时候会导致倾斜,不同的插入顺序会导致树的高度不一样,而树的高度直接影响了树的查找效率,最坏的情况所有的结点都在一条斜线上,这样树的高度为N。

基于BST存在的问题,平衡查找二叉树(Balanced BST)产生了。平衡树在插入和删除的时候,会通过旋转操作将高度保持在logn。其中两款具有代表性的平衡树分别为AVL树(高度平衡树,具备二叉搜索树的全部特性,而且左右子树高度差不超过1,通过左旋和右旋实现平衡)和红黑树。

AVL树由于实现比较复杂,而且插入和删除性能差,在实际环境下的应用不如红黑树。

二叉树删除操作

二叉树的删除操作:本质上是找前驱或者后继结点来替代。

  • 前驱结点:小于当前节点的最大值。

  • 后继结点:大于当前节点的最小值。

删除的情况:

  • 叶子节点直接删除(没有前驱或后继节点)

  • 只有一个子结点的用子结点替代(本质上就是找的前驱结点或者是后继结点,左结点就是前驱结点,右结点就是后继结点)

  • 有两个子结点的,需要找到替代结点(替代结点就是前驱结点或者后继结点)

红黑树删除操作和二叉树一样,只不过红黑树多了着色和旋转过程。

2-3-4树

定义

2-3-4树是四阶的B树(Balance Tree),它属于一种多路查找树,它的结构有以下限制:所有叶子结点都拥有相同的深度。

节点只能是2-结点、3-结点、4-结点之一。

  • 2-结点:包含1个元素的结点,有2个子结点。

  • 3-结点:包含2个元素的结点,有3个子结点。

  • 4-结点:包含3个元素的结点,有4个子结点。

所有结点必须至少包含1个元素。

元素始终保持排序顺序,整体上保持二叉查找树的性质,即父结点大于左子结点,小于右子结点;而且结点有多个元素时,每个元素必须大于它左边的和它的左子树中元素。

2-3-4树的查询操作像普通的二叉搜索树一样,非常简单,但由于其结点元素数不确定,在一些编程语言中实现起来并不方便,实现一般使用它的等同——红黑树。

2-3-4树与红黑树对应关系

结点插入

2-3-4树中结点添加需要遵守以下规则:

  • 插入都是向最下面一层插入;

  • 升元:将插入结点由2-结点升级成3-结点,或由3-结点升级成4-结点;

  • 向4-结点插入元素后,需要将中间元素提到父结点升元,原结点变成两个2-结点,再把元素插入2-结点中,如果父结点也是4-结点,则递归向上层升元,至到根结点后将树高加1;

而将这些规则对应到红黑树里,就是:

  • 新插入的结点颜色为红色,这样才可能不会对红黑树的高度产生影响。

  • 2-结点对应红黑树中的单个黑色结点,插入时直接成功(对应2-结点升元)

  • 3-结点对应红黑树中的黑+红子树,插入后将其修复成红+黑+红子树(对应3-结点升元)

  • 4-结点对应红黑树中的红+黑+红子树,插入后将其修复成红色祖父+黑色父叔+红色孩子子树,然后再把祖父结点当成新插入的红色结点递归向上层修复,直至修复成功或遇到root结点。

红黑树定义

红黑树是一种结点带有颜色属性的二叉查找树,但它在二叉查找树之外,还有以下5大性质:

  1. 结点是红色或黑色。

  2. 根结点是黑色。

  3. 所有叶子都是黑色(叶子是NIL结点,这类结点不可以忽视,否则代码会看不懂)

  4. 每个红色结点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色结点。)

  5. 从任一结点到其每个叶子的所有简单路径都包含相同数目的黑色结点(黑色平衡)。

红黑树演示网站:https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

下图就是一个典型的红黑树:

常见操作

变色:结点的颜色由黑变红或者由红变黑;

左旋:以某个结点作为旋转点,其右子结点变为旋转节点的父结点,右子结点的左子结点变为旋转结点的右子结点,左子结点保持不变。

左旋

右旋:以某个结点作为旋转点,其左子结点变为旋转结点的父结点,左子结点的右子结点变为旋转结点的左子结点,右子结点保持不变。

右旋

新增

新增:分情况讨论,主要是要找到插入位置,然后自平衡(左旋或者右旋)且插入结点是红色(如果是黑色的话,那么当前分支上就会多出一个黑色结点出来,从而破坏了黑色平衡),以下分析全部以左子树为例子,右子树的情况则相反。

  • 如果插入的是第一个结点(根结点),红色变黑色。

  • 如果父结点为黑色,则直接插入,不需要变色。

  • 如果父结点为红色,叔叔结点也是红色(此种情况爷爷结点一定是黑色),则父结点和叔叔结点变黑色,爷爷结点变红色。(如果爷爷结点是根结点,则再变成黑色),爷爷结点此时需要递归(把爷爷结点当做新插入的结点再次进行比较)

  • 如果父结点是红色,没有叔叔结点或者叔叔结点是黑色(此时只能是NIL节点),则以爷爷结点为支点右旋,旋转之后原来的爷爷结点变红色,原来的父结点变黑色。

删除

通俗点讲就是三句话:自己能搞定的自己搞定;搞不定的找兄弟和父亲帮忙;父亲和兄弟都帮不了那有福同享,有难同当(父亲和兄弟自损)

自己能搞定的自己搞定:

  • 如果删除的结点对应于2-3-4树的3结点或者4结点,则直接删除,不用跟兄弟和父亲借。

  • 如果删除的是红色结点,则直接删;如果删除的是黑色结点,则红色结点上来替代,变黑即可;

搞不定的找兄弟和父亲帮忙:

  • 前提是找到“真正“的兄弟结点

  • 兄弟结点有的借(此时兄弟结点一定是黑色,如果是红色那说明这个结点不是真正的兄弟结点,需要回到上一步找真正的兄弟结点)

  • 兄弟结点有两个子结点的情况(2个子结点肯定是红色,如果是黑色的话相当于此时兄弟结点对应2-3-4树是2结点,不可能有多余的元素可以借),此时需要旋转变色。

  • 兄弟结点只有一个子结点的情况,此时需要旋转变色。

兄弟和父亲结点帮不了忙,于是开始递归自损。

  • 前提是找到“真正”的兄弟结点,兄弟结点没有多余的元素可借(此时兄弟结点一定为黑色2结点),此时兄弟结点所在分支也要自损一个黑色结点以此达到黑色平衡,最快的方式就是兄弟结点直接变红(相当于就是减少一个黑色结点),此时一父结点为root的子树又达到了平衡(两边都比之前少一个黑色)。但是以祖父结点为root的树依然是不平衡的,此时需要递归处理。

代码实现

RBTree.java

TreeOperation.java

RBTreeTest.java

0

评论区