我在家庭作业中被要求回答一个关于“红-红-黑”树的问题。红红黑树的描述(从互联网某处复制)是:
“红-红-黑树是满足以下条件的二叉搜索树:
- 每个节点不是红色就是黑色
- 每片叶子(零)都是黑色的
- 如果一个节点是红色的,它的父节点是红色的,那么它的两个子节点都是黑色的
- 从节点到后代叶子的每条简单路径都包含相同数量的黑色节点(树的黑色高度)”
有人问我,给定具有 n 个节点的红-红-黑树,黑色高度为 k 的最大内部节点数是多少?最小的数是多少?
我已经想了两个多小时了,但除了头痛之外,我一无所获。
谢谢!