首页 最新 热门 推荐

  • 首页
  • 最新
  • 热门
  • 推荐
2025年5月31日 星期六 7:23pm

红黑树从头至尾插入和删除结点的全程演示图

  • 25-03-02 16:41
  • 4005
  • 8907
blog.csdn.net

                     红黑树插入和删除结点的全程演示


作者:July、saturnman。
时间:二零一一年三月二十八日。
出处:http://blog.csdn.net/v_JULY_v。
声明:版权所有,侵权必究。
-----------------------------------

引言:

    目前国内图书市场上,抑或网上讲解红黑树的资料层次不齐,混乱不清,没有一个完整而统一的阐述。而本人的红黑树系列四篇文章(详见文末的参考文献),虽然从头至尾,讲的有根有据,层次清晰,然距离读者真正做到红黑树了然于胸,则还缺点什么。

    而我们知道,即便在经典的算法导论一书上,也没有把所有的插入、删除情况一一道尽,直接导致了不少读者的迷惑,而我的红黑树系列第4篇文章:一步一图一代码,一定要让你真正彻底明白红黑树,虽然早已把所有的插入、删除情况都一一道尽了,但也缺了点东西。

    缺点什么东西列?对了,缺的就是一个完完整整的,包含所有插入、删除情况全部过程的全程演示图,即缺一个例子,缺一个完整的图来从头至尾阐述这一切。

    ok,本文,即以40幅图来全程演示此红黑树的所有插入,和删除情况。相信,一定会对您理解红黑树有所帮助。

    话不絮烦,下面,本文便以此篇文章:一步一图一代码,一定要让你真正彻底明白红黑树为纲,从插入一个结点到最后插入全部结点,再到后来一个一个把结点全部删除的情况一一阐述。

    由于为了有个完整统一,红黑树插入和删除情况在此合作成一篇文章。同时,由于本人的红黑树系列的四篇文章已经把红黑树的插入、删除情况都一一详尽的阐述过了,因此,有关红黑树的原理,本文不再赘述,只侧重于用图来一一全程演示结点的插入和删除情况。有任何问题,欢迎指正。


红黑树插入情况全过程演示

       通过本人的红黑树系列第4篇文章,我们已经知道,红黑树的所有插入情况有以下五种:

情形1: 新节点N位于树的根上,没有父节点
情形2: 新节点的父节点P是黑色
情形3:父节点P、叔叔节点U,都为红色,
[对应第二篇文章中,的情况1:z的叔叔是红色的。]
情形4: 父节点P是红色,叔叔节点U是黑色或NIL;
插入节点N是其父节点P的右孩子,而父节点P又是其父节点的左孩子。
[对应我第二篇文章中,的情况2:z的叔叔是黑色的,且z是右孩子]
情形5: 父节点P是红色,而叔父节点U 是黑色或NIL,
要插入的节点N 是其父节点的左孩子,而父节点P又是其父G的左孩子。
[对应我第二篇文章中,情况3:z的叔叔是黑色的,且z是左孩子。]

    详细,可参考此红黑树系列第4篇文章:一步一图一代码,一定要让你真正彻底明白红黑树。

 

首先,各个结点插入与以上的各种插入情况,一一对应起来,如图:

    以下的20张图,是依次插入这些结点:12 1 9 2 0 11 7 19 4 15 18 5 14 13 10 16 6 3 8 17的全程演示图,已经把所有的5种插入情况,都全部涉及到了:

红黑树的一一插入各结点:12 1 9 2 0 11 7 19 4 15 18 5 14 13 10 16 6 3 8 17的全程演示图完。

 

红黑树删除情况全过程演示
    红黑树的所有删除情况,
如下:

情况1: N 是新的根。
情形2:兄弟节点S是红色
[对应我第二篇文章中,情况1:x的兄弟w是红色的。]
情况 3: 兄弟节点S是黑色的,且S的俩个儿子都是黑色的。但N的父节点P,是黑色。
[对应我第二篇文章中,情况2:x的兄弟w是黑色的,且兄弟w的俩个儿子都是黑色的。
(这里,N的父节点P为黑)]
情况4: 兄弟节点S 是黑色的、S 的儿子也都是黑色的,但是 N 的父亲P,是红色。
[还是对应我第二篇文章中,情况2:x的兄弟w是黑色的,且w的俩个孩子都是黑色的。
(这里,N的父节点P为红)]
情况5: 兄弟S为黑色,S 的左儿子是红色,S 的右儿子是黑色,而N是它父亲的左儿子。
//此种情况,最后转化到下面的情况6。
[对应我第二篇文章中,情况3:x的兄弟w是黑色的,w的左孩子是红色,w的右孩子是黑色。]
情况6: 兄弟节点S是黑色,S的右儿子是红色,而 N 是它父亲的左儿子。
[对应我第二篇文章中,情况4:x的兄弟w是黑色的,且w的右孩子时红色的。]

    接下来,便是一一删除这些点12 1 9 2 0 11 7 19 4 15 18 5 14 13 10 16 6 3 8 17为例,即,红黑树删除情况全程演示:

    各个结点删除与以上的六种情况,一一对应起来,如图:

首先,插入12 1 9 2 0 11 7 19 4 15 18 5 14 13 10 16 6 3 8 17结点后,形成的红黑树为:

 

然后,以下的20张图,是一一删除这些结点12 1 9 2 0 11 7 19 4 15 18 5 14 13 10 16 6 3 8 17所得到的删除情况的全程演示图:

红黑树的一一删除各结点:12 1 9 2 0 11 7 19 4 15 18 5 14 13 10 16 6 3 8 17的全程演示图完。


 

参考文献,本人代表作之一:红黑树系列:

1、教你透彻了解红黑树
2、红黑树算法的实现与剖析
3、红黑树的c源码实现与剖析
4、一步一图一代码,R-B Tree
5、红黑树插入和删除结点的全程演示
6、红黑树的c++完整实现源码
7、 http://saturnman.blog.163.com/。

全文完。

文章知识点与官方知识档案匹配,可进一步学习相关知识
算法技能树首页概览49583 人正在系统学习中
注:本文转载自blog.csdn.net的v_JULY_v的文章"http://blog.csdn.net/v_JULY_v/archive/2011/03/28/6284050.aspx"。版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。如有侵权,请联系我们删除。
复制链接
复制链接
相关推荐
发表评论
登录后才能发表评论和回复 注册

/ 登录

评论记录:

未查询到任何数据!
回复评论:

分类栏目

后端 (14832) 前端 (14280) 移动开发 (3760) 编程语言 (3851) Java (3904) Python (3298) 人工智能 (10119) AIGC (2810) 大数据 (3499) 数据库 (3945) 数据结构与算法 (3757) 音视频 (2669) 云原生 (3145) 云平台 (2965) 前沿技术 (2993) 开源 (2160) 小程序 (2860) 运维 (2533) 服务器 (2698) 操作系统 (2325) 硬件开发 (2492) 嵌入式 (2955) 微软技术 (2769) 软件工程 (2056) 测试 (2865) 网络空间安全 (2948) 网络与通信 (2797) 用户体验设计 (2592) 学习和成长 (2593) 搜索 (2744) 开发工具 (7108) 游戏 (2829) HarmonyOS (2935) 区块链 (2782) 数学 (3112) 3C硬件 (2759) 资讯 (2909) Android (4709) iOS (1850) 代码人生 (3043) 阅读 (2841)

热门文章

101
推荐
关于我们 隐私政策 免责声明 联系我们
Copyright © 2020-2024 蚁人论坛 (iYenn.com) All Rights Reserved.
Scroll to Top