红黑树中节点的最大高度

Question

如果我们在红黑树中有一个节点，黑色高度为3，该节点允许的最大高度是多少？

Answer 1

红黑树的最大高度为2 * log(n+1) 所以如果节点数是 15 ，那么最大高度应该是 2 * log(16) or 8

Interesting points about Red-Black Tree:

red-black树的黑色高度是一个黑色节点的个数从根节点到叶节点的路径。
叶节点也算作黑节点。所以，一棵 red-black 树高度 h 有黑色高度 >= h/2.
具有 n 个节点的 red-black 树的高度为 h<= 2 log2(n + 1)。全部叶子 (NIL) 是黑色的。
一个节点的黑色深度定义为黑色节点的个数从根到那个节点，即黑人祖先的数量。
每个 red-black 树都是二叉树的特例。

Black Height of a Red-Black Tree :

黑色高度是从根到路径上黑色节点的个数一片树叶。叶节点也算黑节点。从以上属性3和4，我们可以推导出，一棵Red-Black高度为h的树有 black-height >= h/2.

Every Red Black Tree with n nodes has height <= 2Log2(n+1) This can be proved using the following facts:

对于一般的二叉树，令k为上的最小节点数所有根到 NULL 路径，然后 n >= 2k – 1（例如，如果 k 为 3，则 n 位于至少 7).这个表达式也可以写成 k <= Log2(n+1).
来自属性 4 of Red-Black trees and above claim, 我们可以说 Red-Black 有n个节点的树，有一条从根到叶的路径 at-most Log2(n+1) 个黑色节点。
从属性 3 和 5 棵 Red-Black 树中，我们可以声称 Red-Black 树中黑色节点的数量至少为 ⌊ n/2 ⌋ 其中 n 是节点总数。
从以上几点，我们可以得出一个事实，红黑树具有 n 个节点的高度 <= 2Log2(n+1)

Answer 2

为了最大化该节点的高度，您需要创建最长的向下路径，其中只有 3 个黑色节点（不包括起始节点）。正如在 red-black 树中，红色节点不能有红色子节点，您能做的最好的事情就是在这样的路径上交替颜色。此外，路径必须以黑色节点结束，因为所有 (NIL) 叶子都是黑色的。所以有 3 个黑色节点的最长路径是：

node (black, but not counted in "black height")
   \
   red 
     \ 
     black #1
       \
       red
         \
         black #2
           \
           red
             \
             black #3/NIL

高度（=路径长度）为6，不能再长了。所以这就是黑高为3的节点的最大高度。一般情况下，节点的最大高度是其黑高的2倍。

红黑树中节点的最大高度

Maximum height of a node in a red-black tree

algorithm

red-black-tree