专栏首页算法无遗策动画 | 什么是红黑树?(基于2-3树)

动画 | 什么是红黑树?(基于2-3树)

学习过2-3树之后就知道应怎样去理解红黑树了,如果直接看「算法导论」里的红黑树的性质,是看不出所以然。我们也看看一颗二分搜索树满足红黑的性质:

1.每个节点或是红色的,或是黑色的;

2.根节点是黑色的;

3.每个叶子节点(NIL)是黑色的;

4.如果一个节点是红色的,则它的两个子节点都是黑色的;

5.对每个节点,从该节点到其所有后代叶子节点的简单路径上,均包含相同数目的黑色节点。

如果说前面4个还算理解,那第5个性质又是怎么去理解呢?此时我们借着2-3树去理解基本的红黑树,当然我会在后几篇文章介绍2-3-4树以及基于2-3-4树的红黑树。

抛开上面二分搜索树满足红黑的性质,我们知道2-3树不是二叉树,我们把它转换成一颗二叉树,2-节点很好转,3-节点转二叉却有两种,如下图:

红黑是指被指向节点的链接颜色,对于一颗2-3树,因为3-节点的存在有很多不同的二叉树的表示,所以我们只考虑左倾的情况。

左倾红黑树和2-3树等价的定义

红黑树的定义是含有红黑链接并满足下列条件的二分搜索树:

1.红链接均为左连接;

2.没有任何一个节点同时和两条红链接相连;

3.该树是完美黑色平衡的,即任意空链接到根节点的路径上的黑链接数量相同(和2-3树等价的,任意节点到其叶子节点的高度都是相同的)。

因为2-3树不存在永久的4-节点,4-节点终归要分解的(在2-3-4树中,为了更好地插入和删除,4-节点可存在于叶子节点和非叶子节点)2-3树一样不行,所以在2-3树中没有任何一个节点能同时和两条红链接相连。对于第3条,2-3树本身是绝对平衡的,将3-节点转成二叉只增加了左红链接,其他黑链接没有什么变化,依然是黑色平衡的。

查找元素

查找命中和二分搜索树一样,从根节点开始,如果查找命中则返回,否则比它小的进行左递归查找,比它大的进行右递归查找,直到查找为空。

写插入元素和删除元素之前,还是要先介绍一下旋转和颜色转换。

旋转

在插入或者删除操作中可能会出现右倾或者两条连续的红链接,在向上变换的过程中(恢复)都要调整为左倾。

假设有一条红色的右链接需要转为左链接,如下图所示:

这个操作叫做左旋转,右链接变成左链接,意味着被红链接指向的节点会变成红色,根节点默认是黑色。

右旋转也一样,不过在左倾红黑树中,只有出现两条连续红色的左连接才会进行右旋转,如下图:

Code:左旋转和右旋转

颜色转换

颜色转换是用在临时4-节点上的,不管是向下变换还是向上变换。

Code:颜色转换

插入元素

插入元素也需要先进行查找命中,查找未命中则在此节点(NIL)插入一个元素,是在红黑树底下插入一个红色节点,插入元素默认是红色节点。

如果红黑树目前是一颗空树,可以直接存储一个元素作为节点,然后该节点变成黑色。如果不是一颗空树,插入元素分两种情况:向2-节点插入新元素和向3-节点插入新元素。

向2-节点插入新元素有两种情况

向2-节点插入新元素很简单,如果新元素小于父节点的元素,直接插入红色的节点即可;如果新元素大于父节点的元素,则产生一个红色右链接,插完之后进行向上变换,在向上变换的过程中(修复红黑树的性质)需要进行左旋转,将右链接变成左链接,满足左倾红黑树的性质。

向3-节点插入新元素有三种情况

1.新元素小于3-节点最小值

2.新元素位于3-节点最小值和最大值之间

3.新元素大于3-节点最大值

插入元素只有向上变换的过程,目的是为了满足红黑性质。

动画:插入元素

Code:插入元素

删除元素

删除元素既有向下变换也有向上变换:向下变换是为了树底下有一个被红链接指向的节点可以被删除,不影响黑色平衡;向上变换是为了修复基于2-3树的左倾红黑树。

Code:向上变换(修复调整)

删除元素有4个原则:

1.删除元素的当前节点不能是2-节点;

2.向下变换不为2-节点;

3.从树底部删除节点;

4.向上变换,消除右倾和4-节点。

删除元素借鉴了之前学的二分搜索树删除元素的思想,二分搜索树删除元素分为删除最小元素、删除最大元素和删除任意元素三种情况:删除最小元素是一直递归它的左孩子,直到左孩子为空才进行删除;删除最大的元素则相反;如果是删除任意的元素需要进行命中查找,找到了就取右子树的最小值替换掉待删除元素,然后进行右子树的删除最小元素。

红黑树删除元素也是一样的,不过是多了向下变换和向上变换的过程。因为是左倾红黑树,删除最小元素是最合适的。

删除最小元素

算法4」里的红黑树介绍了删除最小键这一小节,虽没有很详细地介绍,但给出了沿着左链接向下变换的三种情况:

1.如果当前节点(父节点位置)的左子节点不是2-节点,完成;

2.如果当前节点(父节点位置)的左子节点是2-节点而左子节点的兄弟节点不是2-节点,则左子节点借它的兄弟节点的一个键过来;

3.如果当前节点(父节点位置)的左子节点和左子节点的兄弟节点都是2-节点,将左子节点、当前节点和左子节点的兄弟节点合并成一个临时的4-节点,使当前节点由3-节点变成2-节点或则4-节点变成3-节点。

Code:moveRedLeft

删除最大节点思路也是一样的,不过这是左倾红黑树,对删除最大节点益处不大,甚至向下转换的时候左倾调整为右倾,向上转换balance还要将右倾调整为左倾。

动画:删除最小元素

Code:删除最小元素

删除任意元素

在前面学习了删除最小节点,删除任意节点自然就很简单了。我们如果要删除一个节点,首先进行命中查找,查找到这个待删除元素,将右子树的最小值替换掉这个待删除元素,指向待删除节点的链接颜色不能被改变。然后进行右子树的删除最小元素。

在命中查找过程中,需要沿着左链接或沿着右链接进行向下转换。前面删除最小元素就是沿着左链接向下转换的。

沿着右链接向下转换也分三种情况:

1.如果当前节点(父节点位置)的右子节点不是2-节点,将左倾转换成右倾;

2.如果当前节点(父节点位置)的右子节点是2-节点而右子节点的兄弟节点不是2-节点,则右子节点借它的兄弟节点的一个键过来;

3.如果当前节点(父节点位置)的右子节点和右子节点的兄弟节点都是2-节点,将右子节点、当前节点和右子节点的兄弟节点合并成一个临时的4-节点,使当前节点由3-节点变成2-节点或则4-节点变成3-节点。

Code:moveRedRight

Code:删除任意元素

动画:删除任意元素

阅读原文可查看算法4里的RedBlackTree.java源码

-----END-----

本文分享自微信公众号 - 算法无遗策(gh_6519e8c0cb55),作者:我脱下短袖

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 动画 | 什么是2-3树?(修改删除操作方式)

    我们回忆一下AVL树,它在插入和删除节点时,总要保证任意节点左右子树的高度差不超过1。正是因为有这样的限制,插入一个节点和删除一个节点都有可能调整多个节点的不平...

    我脱下短袖
  • 动画 | 什么是2-3树?

    我们回忆一下AVL树,它在插入和删除节点时,总要保证任意节点左右子树的高度差不超过1。正是因为有这样的限制,插入一个节点和删除一个节点都有可能调整多个节点的不平...

    我脱下短袖
  • 动画 | 什么是红黑树?(与2-3-4树等价)

    二分搜索树是为了快速查找而生,它是一颗二叉树,每一个节点只有一个元素(值或键值对),左子树所有节点的值均小于父节点的值,右子树所有的值均大于父节点的值,左右子树...

    我脱下短袖
  • 一万字详解 Redis Cluster Gossip 协议

    大家好,我是历小冰,今天来讲一下 Reids Cluster 的 Gossip 协议和集群操作,文章的思维导图如下所示。

    程序员历小冰
  • (2)MongoDB副本集自动故障转移 全流程原理

    前文我们搭建MongoDB三成员副本集,了解集群基本特性,今天我们围绕下图聊一聊背后的细节。

    小码甲
  • 动画 | 什么是2-3-4树?

    画了一系列树的动画,从二分搜索树,到AVL树,再到2-3树,再到基于2-3树的红黑树,都可以发现这些树都跟二叉查找树很像啊。

    我脱下短袖
  • 【从二叉树到红黑树】清晰理解红黑树的演变---红黑的含义

    网上关于红黑树的博文很多,但是多是上来即讲定义,未说其所以然,难以理解且无所营养,甚者示例图有误且概念模糊的比比即是;

    云服务器最新
  • 动画 | 什么是2-3树?

    我们回忆一下AVL树,它在插入和删除节点时,总要保证任意节点左右子树的高度差不超过1。正是因为有这样的限制,插入一个节点和删除一个节点都有可能调整多个节点的不平...

    我脱下短袖
  • 动画 | 什么是2-3树?(修改删除操作方式)

    我们回忆一下AVL树,它在插入和删除节点时,总要保证任意节点左右子树的高度差不超过1。正是因为有这样的限制,插入一个节点和删除一个节点都有可能调整多个节点的不平...

    我脱下短袖
  • 我画了 20 张图,给女朋友讲清楚红黑树

    红黑树是一种常见的自平衡二叉查找树,常用于关联数组、字典,在各种语言的底层实现中被广泛应用,Java的TreeMap和TreeSet就是基于红黑树实现的。本篇分...

    范蠡

扫码关注云+社区

领取腾讯云代金券