实现红黑树, C语言

作者: sk邵楷 | 来源:发表于2022-11-13 10:50 被阅读0次

001 红黑树(二)之 C语言的实现(3)
实现红黑树, C语言
STL源码解析(1)-红黑树
C语言——红黑树
红黑树
红黑树C++ 实现
拿下红黑树
树-红黑树和AVL树的区别
红黑树
数据结构学习_02红黑树平衡操作

感觉linux内核内存管理里面会用到红黑树, 所以就学了一下, 主要是看了B站码炫课堂讲解的红黑树视频, 然后用C语言尝试了一下, 然后做个笔记.

可以通过" https://www.cs.usfca.edu/~galles/visualization/RedBlack.html " 这个网站试一试红黑树的生成和删除.

红黑树的定义

   1, 节点是红色或者黑色
   2, 根是黑色
   3, 所有叶子都是黑色(叶子是NULL节点, 这类节点不可以忽略, 否则代码会看不懂)
   4, 每个红色节点必须有两个黑色的子节点(从每个叶子到根的所有路径上不能有两个连续的红色节点)
   5, 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点(黑色平衡)

红黑树.jpg

为什么需要红黑树:

对于二叉搜索树，如果插入的数据是随机的，那么它就是接近平衡的二叉树，平衡的二叉树，它的操作效率（查询，插入，删除）效率较高，时间复杂度是O（logN）。但是可能会出现一种极端的情况，那就是插入的数据是有序的（递增或者递减），那么所有的节点都会在根节点的右侧或左侧，此时，二叉搜索树就变为了一个链表，它的操作效率就降低了，时间复杂度为O(N)，所以可以认为二叉搜索树的时间复杂度介于O（logN）和O(N)之间，视情况而定。那么为了应对这种极端情况，红黑树就出现了，它是具备了某些特性的二叉搜索树，能解决非平衡树问题，红黑树是一种接近平衡的二叉树（说它是接近平衡因为它并没有像AVL树的平衡因子的概念，它只是靠着满足红黑节点的5条性质来维持一种接近平衡的结构，进而提升整体的性能，并没有严格的卡定某个平衡因子来维持绝对平衡）。

红黑树的查找，插入和删除操作，时间复杂度都是O(logN)。

红黑树和AVL树的比较：
1, AVL树的时间复杂度虽然优于红黑树，但是对于现在的计算机，cpu太快，可以忽略性能差异
2, 红黑树的插入删除比AVL树更便于控制操作
3, 红黑树整体性能略优于AVL树（红黑树旋转情况少于AVL树）

整个视频核心的地方有下面几个点:

一, 红黑树和 2-3-4树的等价

image.png

二, 红黑树的新增操作

红黑树中, 新增一个节点, 都当做新增一个红色的节点. 其次, 新增的节点都会在叶子节点上

情况1

image.png

情况2

image.png

情况3

image.png

举例来说: 插入的节点的父节点是爷爷节点的左孩子(右孩子与之相反), 有两种可能

image.png

可以看出, 最上面的情况只要一个右旋就可以了, 下面的情况, 先是左旋, 然后右旋, 代码如下(x代表插入的节点):

               if(x == rightOf(parentOf(x)))
                {
                    x = parentOf(x);
                    leftRotate(x);
                }
                //父亲变黑
                setColor(parentOf(x), RB_BLACK);
                //爷爷变红
                setColor(parentOf(parentOf(x)), RB_RED);
                //根据爷爷节点右旋转
                rightRotate(parentOf(parentOf(x)));

情况4

image.png

最左边是初始状态, 右边四个分别是新增5, 新增3.5, 新增1, 新增2.5的四种情况, 可以看出这些情况只要对相应的节点进行变色就行了. 具体来说, 插入节点的叔叔节点变黑, 插入节点的父节点变黑, 插入节点的爷爷变红. 代码如下(x代表插入的节点):

           //叔叔节点
            y = leftOf(parentOf(parentOf(x)));

            //第三种情况
            if(colorOf(y)== RB_RED)
            {
                setColor(parentOf(x), RB_BLACK);
                setColor(y, RB_BLACK);
                setColor(parentOf(parentOf(x)), RB_RED);
                //爷爷节点递归
                x=parentOf(parentOf(x));
            }

三, 红黑树的删除操作

首先, 红黑树的删除操作分成下面三步:
1)首先, 找到需要删除节点的前驱节点(值小于删除节点的所有节点的最大的)或者是后继节点(值大于删除节点的所有节点的最小的)
2)然后用替代节点覆盖要删除的节点
3)然后把这个替代节点给删掉
当然, 如果你要删除的节点是一个叶子节点, 那么你要找的替代节点就是它自己, 删除的节点也就是它自己
如果你要删除的节点, 只有一个叶子节点, 那么替代节点就是它的叶子节点(最靠近它的就是它的叶子.....)
接下来, 重点来了, 有个结论就是, 你要找的替代节点都是红黑树上的叶子节点, 或者是叶子节点的上一层节点. 简单证明如下(可以不看).

论证方式:

        红黑树等价于2-3-4树
        删除2-3-4树的一个节点
        找替代节点的时候, 因为2-3-4树是个满树, 最后的替代节点肯定找的要么是它自己, 要么就是2-3-4树的一个叶子节点
         2-3-4树的一个叶子节点就是红黑树的叶子节点或者是叶子节点上一层的一个节点

删除操作情况1

自己可以搞定——替代节点是红色的, 这种情况对应替代节点是2-3-4树的3节点或者是4节点

image.png

如上图, 删除 0节点, 7.5节点, 9节点, 11节点, 这些节点都对应着2-3-4树的3节点或者是4节点, 并且都是红色的, 那么直接删掉就可以了. 不影响黑色平衡.

删除操作情况2

情况二、自己搞不定，需要跟兄弟借，但是兄弟不借，找父亲借，父亲下来，然后兄弟找一个人去代替父亲当家

对于3节点, 可以是借1个(左旋就可以了), 也可以借2个(右旋再左旋)

image.png

对于4节点, 肯定是借两个节点情况, 一个左旋就可以了

image.png

删除操作情况3

情况三、跟兄弟借，兄弟也没有（兄弟情同手足，同时自损）

image.png

这种情况下, 兄弟变红了, 导致这条路径完全少了一个黑色节点, 整个树不平衡了, 那么需要x的父节点, 即50这个节点开始, 不断重复向兄弟节点借黑色节点, 这样一个循环, 不断靠借, 来使得整个树变成原先的黑色平衡, 代码实现很简单, 但理解很难, 建议看一下B站码炫课堂的红黑树视频, 对照代码理解一下.