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

Question

一棵黑色高度为k的红黑树内部节点个数最少为2^k-1，如下图所示:

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

内部节点数是7，我做错了什么？

Answer 1

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

我认为使用 isometry between red-black trees and 2-3-4 trees 可能有助于思考这个问题.具体来说，一棵黑色高度为h的红黑树对应一棵高度为h的2-3-4树，其中每个红色节点对应多键节点中的一个键。

这种联系使我们更容易做出一些巧妙的观察。首先，底层的任何 2-3-4 树节点都对应于一个没有红色子节点、一个红色子节点或两个红色子节点的黑色节点。这些是红黑树中唯一可以作为叶节点的节点。如果我们想最大化树中的总节点数，我们想让 2-3-4 树只有 4 个节点，这(在等距下)映射到红/黑树，其中每个黑色节点有两个红色 child 。一个有趣的效果是它使树层的颜色在黑色和红色之间交替，顶层(包含根)为黑色。

本质上，这归结为计算高度为 2h - 1(2h 层在黑色和红色之间交替)的完全二叉树中的内部节点数。这等于一棵高度为 2h - 2 的完整二叉树中的节点数(因为如果你拉掉所有的叶子，你剩下的是一棵高度比你开始时少一的完整树)。计算结果为 2^{2h - 1} - 1，这与给你的数字不同(我现在确信这是不正确的)但与你得到的数字相匹配。