红黑树删除节点有两个子节点的转化分析

思路:

红黑树欲删除节点(d)两个子节点的情况下,想直接删除节点不好处理,
转换成只有一个子节点没有子节点的情况,则更好处理
一般是找后继节点(s),然后交换欲删除节点(d)和后继节点(s)
后继节点可以简单理解为比当前节点大的节点中最小的节点

交换的方式可以有两种:
1.值交换
2.节点位置交换

位置交换时,应注意后继节点的位置不同的两种情况
1.欲删除节点(d)和后继节点(s)不直接相邻
2.欲删除节点(d)和后继节点(s)相邻,即s是d的右子节点

写代码时,应注意区分这两种情况

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容