红黑树添加删除节点操作详解资料整理.doc_节点的概念 - CSDN文库

红黑树添加删除节点

5星 · 超过95%的资源需积分: 33 86 浏览量更新于2023-03-03 评论 1 收藏 344KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

红黑树的插入、删除及旋转原则



红黑树 !"的插入和删除操作很繁琐，一不小心就容易弄错，不

能靠强制记忆。因此，今天总结一下红黑树插入和删除操作的推导原则，包括

旋转的推导原则。

本文所有内容来自三个网页

# $%&&$#'#(&) 

(*+,-.//0'/1/02020+01+0./,',-20,

/2.12+2+20+.0+12+2/.-0',/+

/0-.++2'''''1+0+..2./2/1/--/1120

-1112011,1,',/2'22+-+1+2-2+--/

/,+//0'1'0--/'2/-1'12.01'-'+--+'0.2.

00.23%*,1.0-,0/0''++1234*'

# $%&&#(&22&2,&-&4' & 

.# $%&&$#'#(&220--0&'&(& 

.'+101..2+//#$(

如果大家能打开上面的链接，就不用再看了，我整理

得不好。。

先是比较简单的插入操作的推导原则：

#红黑树的插入和普通搜索二叉树5$!"的插入一样，只是

在插入完以后，将新插入的节点标记为红色，然后从该节点开始，向上进行调

整颜色。

#向上调整颜色进行旋转时，旋转的原则是尽量用  次或者最多  次旋转完成，

并且旋转操作不能影响该层以下层次的节点，只能影响其父节点，然后将其父

节点（或者叔节点、兄弟节点）作为新的要调整颜色节点，继续向上递推调整。

.#调整完后注意检查根的颜色是否还是黑色。

删除操作的推导原则：（比较麻烦！）

#删除节点  时，先找到  的中根后继节点 ，然后将  的数据复制给 （不

包括颜色），然后将  删除。这样，删除  的时候， 最多只有一个孩子节点

，将  取代  即可，然后如果  的颜色是黑色，才需要调整颜色。若要调整颜

色，从  处开始向上递推的调整颜色。

#从  处开始向上调整颜色时也应注意不要影响该层次以下的节点，只能影响

 同层或者更高层的节点。调整完后  的父节点（或者叔节点、兄弟节点）作

为新的待调节点（新的 ），如果  颜色为红色时，则不用调了，直接结

束。

.#调整是应注意通过标记各层高度（黑高度）来进行推导。

/#结束后看  是否是红色，如果是，改成黑色。

Remarks:

#里面提到的高度是指黑节点个数。

#层次也是关于黑节点来说的。

红黑树原理详解上：

前言：

6666666之所以要写这篇文章，第一个目的是为了各位朋友在查看我写的源代码之前有一个可

以理解理论的文章因为红黑树还是有点难的，

如果不想搞懂理论，而直接看代码，那绝对是云里雾里，不知所云。第二个目的是我觉得

网上虽然后不少我文章也在讲，但是我就是理解

不上有点困难，在我参考了很多文章之后，认真阅读才慢慢摸透了其中的原理，所以我想

用自己的方式来表达，希望有助于各位的朋友理解。

你可以在这里获得配套源代码

红黑树由来：

6666666他是在 + 年由 1 发明的，他称之为“对称二叉  树”，它现代的名字

是 78#9'4 和 '5 于 +,

年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且

在实践中是高效的它可以在 :"时间内做查找，

插入和删除，这里的 是树中元素的数目。

红黑树性质：

#每个结点或红或黑。

#根结点为黑色。

剩余22页未读，继续阅读

评论9

zhanglong71

2012-08-10

对理解rbtree原理很有用。不过，本人只是用而已，更倾向于了解各接口的用法及例子。

dkdkdk

粉丝: 13
资源: 25

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈