1

我在家庭作业中被要求回答一个关于“红-红-黑”树的问题。红红黑树的描述(从互联网某处复制)是:

“红-红-黑树是满足以下条件的二叉搜索树:

  1. 每个节点不是红色就是黑色
  2. 每片叶子(零)都是黑色的
  3. 如果一个节点是红色的,它的父节点是红色的,那么它的两个子节点都是黑色的
  4. 从节点到后代叶子的每条简单路径都包含相同数量的黑色节点(树的黑色高度)”

有人问我,给定具有 n 个节点的红-红-黑树,黑色高度为 k 的最大内部节点数是多少?最小的数是多少?

我已经想了两个多小时了,但除了头痛之外,我一无所获。

谢谢!

4

2 回答 2

1

最大节点数:(2^2k)-1

最小节点数:(2^k)-1

于 2021-06-11T07:40:12.513 回答
0

两个红节点永远不能连续出现。当您遍历任何路径时,黑色节点的数量应该相等。

于 2012-03-29T09:03:45.890 回答