黑弹树的功效与作用_黑弹树的功效与作用

黑弹树的功效与作用_黑弹树的功效与作用红黑树的用途、红黑树的插入删除操作红黑树首先是一棵二叉查找树(BST),BST 满足的性质如下:左子树上所有节点的值均小于或等于它的根节点的值;右子树上所有节点的值均大于或等于它的根节点的值;左右子树䦹 BST。考虑向一棵 BST 中多次插入新节点的情况,如果插

红黑树的用途、红黑树的插入删除操作   红黑树首先是一棵二叉查找树(BST),BST 满足的性质如下: 左子树上所有节点的值均小于或等于它的根节点的值; 右子树上所有节点的值均大于或等于它的根节点的值; 左右子树䦹 BST。   考虑向一棵 BST 中多次插入新节点的情况,如果插入的总是最大(小)值,会导致 BST 严重不平衡。为了解决这个问题,引入了自平衡的二叉查找树——红黑树(BR-Tree)。红黑树的附加特性: 节点为黑色或红色; 根节点为黑色; 每个叶子节点都是黑色的空节点(NIL); 每个红色节点的两个孩子节点都是黑色(保证从每个叶子到根的所有路径上不能有两个连续的红色节点); 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点(保证了红黑树从根到叶子的最长路径不会超过最短路径的两倍)。   红黑树的用途   1)广泛应用在 C++ 的 STL 中,如 map 和 set 都是用红黑树实现的。   2)linux 进程调度,用红黑树管理进程控制块   3)epoll 在内核中的实现,用红黑树管理事件块   4)nginx 中,用红黑树管理 timer 等   红黑树的插入   插入的新节点 N 初始化为红色。   case 0.0:   N 为根节点,直接变为黑色。over。   case 0.1:   N 的父节点为黑色,无需调整。over。
黑弹树的功效与作用_黑弹树的功效与作用插图1 case 0.0 与 case 0.1 示意图   case 1:   N 的父节点为红色,无叔叔节点(父节点的兄弟节点)或叔叔节点为黑色,且 N 为右子。以父节点为新红色节点 N,并以 N 为支点进行左旋。继续判定旋转后的节点 N 是否满足性质。
黑弹树的功效与作用_黑弹树的功效与作用插图3 case 1 示意图 – 1   
黑弹树的功效与作用_黑弹树的功效与作用插图5 case 1 示意图 – 2   case 2:   N 的父节点为红色,无叔叔节点(父节点的兄弟节点)或叔叔节点为黑色,且 N 为左子。将 N 的父节点变为黑色,祖父节点变为红色,以祖父节点为支点进行右旋。
黑弹树的功效与作用_黑弹树的功效与作用插图7 case 2 示意图   
黑弹树的功效与作用_黑弹树的功效与作用插图9 case 1 与 case 2 示意图   case 3:   N 的父节点为红色,叔叔节点(父节点的兄弟节点)也为红色,将父节点与叔叔节点都变为黑色,祖父节点变为红色。若祖父节点仍不满足性质,则将祖父节点当做新红色节点递归调整。最后强制根节点为黑色。
黑弹树的功效与作用_黑弹树的功效与作用插图11 case 3 示意图   红黑树的删除   case 1:   如果需要删除的节点有两个孩子,我们的做法是找到这个节点的中序后继,将后继节点中的数据拷贝至待删除结点,然后删除后继节点。而后继节点必然最多只有一个子节点,这样我们就把删除两个孩子的节点转为删除一个孩子的节点(case 2)。   case 2:   删除只有一个孩子的节点,如果它两个孩子都为空,即均为叶子,我们任意将其中一个看作它的孩子。(这里体现出来,在红黑树里特别指定叶子结点为 NIL 节点的作用,NIL 节点经常可以充当正常节点使用以使得算法的表达更加容易。)   case 2.1:   若被删除节点是红色,它的父亲和孩子一定是黑色的。所以我们可以简单地用它的黑色孩子替换它。   case 2.2:   若被删除节点是黑色而它的孩子是红色。用它的红色孩子顶替上来并重绘为黑色。   case 2.3   若待删除节点和它的子节点都是黑色,情况比较多,由简单到复杂分为六小类。   先来约定涉及到的节点的名称。我们先用待删除节点的孩子代替待删除节点,并且记这个孩子为 N,记它的新的父节点为 P,它的兄弟节点为 S, S的左孩子为 SL,右孩子为 SR。   case 2.3.1:   若 N 是新的根。无需改动,所有属性都保持着。over。   case 2.3.2:   P 为红色,S 和 S 的两个孩子都是黑色的。将 P 置为黑色,S 置为红色。这样,不经过 N 的路径上的黑色结点数目并没有发生变化,而经过 N 结点的路径上黑色结点的数目增加了 1,刚好添补了这条路径上删除的黑色结点。所以红黑树又重新达到了平衡。   
黑弹树的功效与作用_黑弹树的功效与作用插图13 case 2.3.2 示意图   case 2.3.3:   S 是黑色,S 的右孩子是红色,而 N 是它父亲的左儿子。以 P 为支点左旋,这样 S 成为 P 和 R 的父亲。接着交换 N 的父亲和 S 的颜色,并使 S 的右儿子为黑色。   
黑弹树的功效与作用_黑弹树的功效与作用插图15 case 2.3.3 示意图(白色节点可以是红色或黑色,但是在变换前后都必须指定相同的颜色)   case 2.3.4:   S 是黑色,S 的左孩子是红色,S 的右儿子是黑色,而 N 是它父亲的左儿子。在这种情况下我们在 S 上做右旋,这样 S 的左儿子成为 N 的新兄弟。我们接着交换 S 和它的新父亲的颜色。所有路径仍有同样数目的黑色节点,但是现在N有了一个右儿子是红色的黑色兄弟,所以我们进入了 case 2.3.3。N 和它的父亲都不受这个变换的影响。   
黑弹树的功效与作用_黑弹树的功效与作用插图17 case 2.3.4 示意图   case 2.3.5:   S 是红色。在这种情况下我们在 P 上做左旋,把红色兄弟转换成 N 的祖父。我们接着对调 N 的父亲和祖父的颜色。尽管所有的路径仍然有相同数目的黑色节点,现在 N 有了一个黑色的兄弟和一个红色的父亲,所以我们可以接下去按 case 2.3.2、case 2.3.3、case 2.3.3 来处理。   
黑弹树的功效与作用_黑弹树的功效与作用插图19 case 2.3.5 示意图   case 2.3.6:   P、S 和 S 的儿子都是黑色的。在这种情况下,我们简单的重绘 S 为红色。结果是通过 S 的所有路径,都少了一个黑色节点。 因为删除 N 的初始的父亲使通过 N 的所有路径少了一个黑色节点,这使事情都平衡了起来。 但是,通过 P 的所有路径现在比不通过 P 的路径少了一个黑色节点。要修正这个问题,我们要转到 case 2.3.1,把 P 当做新的 N 重新平衡处理。   
黑弹树的功效与作用_黑弹树的功效与作用插图21 case 2.3.6

2024最新激活全家桶教程,稳定运行到2099年,请移步至置顶文章:https://sigusoft.com/99576.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处:https://sigusoft.com/56869.html

(0)
上一篇 2024年 8月 31日 下午3:02
下一篇 2024年 8月 31日 下午3:06

相关推荐

关注微信