红黑树有些写特性不理解,求大佬解答?

发布于 2022-09-11 18:43:00 字数 753 浏览 7 评论 0

1.首先是红黑树的特性

红黑树的特性:

(1) 每个节点或者是黑色,或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!]
(4) 如果一个节点是红色的,则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
第5条子孙节点包括NIL节点吗?
图片描述
如果包括NIL节点那上图中路径上黑节点数目就是3个,树的高度就是4。
第5条子孙节点的路径包括到NIL节点的路径吗?
比如80--40--20--10--NIL是一条路径
80--40--20--NIL也是一条路径

2.关于红黑树高度和节点的个数

一棵含有n个节点的红黑树的高度至多为2log(n+1).
我是不是可以认为当有n个节点时一定有一个红黑树的高度为2log(n+1)?
比如当n=3时一定存在一个高度为4的红黑树

补充n=3时高度为4的树
图片描述

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(2

南烟 2022-09-18 18:43:00
  1. 包括
  2. 是的,一定可以构造这样高度的一棵树,但不可能更多,否则就不是红黑树了
简单 2022-09-18 18:43:00

看了下算法导论,有几点
1.从某个节点x出发(不包括该节点)到达一个叶节点的任意一条路径上,黑色节点的个数称为该节点的黑高度(x's black height),记为bh(x)。
2.以任意节点x为根的子树至少包含2^bh(x)-1个内部点,如果x是根节点的话n>=2^bh(x)-1。
3.最终证明了内节点个数和高度的关系是n>=2^(h/2)-1。
当黑高bh(x)=h时第二个条件等于成立,即没有红色节点。我们已经知道h/2<=bh(x),同样当没有红色节点时第三个条件的等式才成立,此时h/2=bh(x)=h。最后当h=0时等式成立,高为其他时内部节点个数和高度的关系是n>2^(h/2)-1。
如果有其他不对还请指出。

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文