红黑树中最大和最小数量的内部节点？

Question

黑色高度为k的红黑树中的最小内部节点数为2 ^k -1,如下图所示:

黑色高度为k的最大内部节点数为2 ^2k -1,如果黑色高度为2,则应为2 ⁴ - 1 = 15.但是,请考虑以下图像:

内部节点的数量是7.我做错了什么？

Answer 1

(我完全重写了这个答案,因为正如评论者指出的那样,它最初是不正确的.)

我认为通过使用红黑树和2-3-4树之间的等距来考虑这个问题可能会有所帮助.具体地,黑色高度为h的红黑树对应于高度为h的2-3-4树,其中每个红色节点对应于多关键节点中的关键字.

这种连接使我们更容易做出一些简洁的观察.首先,底层中的任何2-3-4树节点对应于没有红色子节点,一个红色子节点或两个红色子节点的黑色节点.这些是红黑树中唯一可以是叶节点的节点.如果我们想要最大化树中总节点的数量,我们想要使2-3-4树只有4个节点,(在等轴测图下)映射到红色/黑色树,每个黑色节点有两个红孩子.一个有趣的效果是它使树层颜色在黑色和红色之间交替,顶层(包含根)是黑色.

从本质上讲,这可以归结为计算高度为2h - 1的完整二叉树中的内部节点数(2h层在黑色和红色之间交替).这等于高度为2h-2的完整二叉树中的节点数(因为如果你拉掉所有叶子,你将留下一个完整的树,比你开始时的树高一个).这可以达到2 ^{2h - 1} - 1,这与您给出的数字(我现在确信它是不正确的)不同,但与您获得的数字相匹配.

Answer 2

如果不是这个公式不起作用,你需要计算树中的黑色NIL叶子.root必须不是RED,这违反了Red-Black树的一个属性.