为什么这个关于红黑二叉搜索树的说法是正确的？
Why is this statement regarding red-black binary search trees true?
语句：假设红黑二叉搜索树中的某个不成功的搜索在 k 键比较后终止。然后，任何不成功的搜索都会执行至少 ceiling(k/2) 个键比较。
为什么正确的解释：极端情况下，links红黑交替（从红色开始），黑色高度为ceiling(k/2) - 1 .任何不成功的搜索都会跟踪从根到空 link 的路径；沿着这条路径正好有 ceiling(k/2) - 1 黑色 links（不包括 null link）。如果路径不包含红色 links，则它包含 ceiling(k/2) 个节点（并进行 ceiling(k/2) 键比较）。
我的看法：除非k = 0或1，否则不可能k == ceiling(k/2)。我开始想，也许问题出在我如何解读这句话。
如果一些次不成功的查找需要k次比较，那么每次不成功的查找至少要[=20=次] ] ceil(k/2) 比较。
那包括拿k的比较，因为k是至少ceil(k/2).
注意 "at least" 表示 >=
语句：假设红黑二叉搜索树中的某个不成功的搜索在 k 键比较后终止。然后，任何不成功的搜索都会执行至少 ceiling(k/2) 个键比较。
为什么正确的解释：极端情况下，links红黑交替（从红色开始），黑色高度为ceiling(k/2) - 1 .任何不成功的搜索都会跟踪从根到空 link 的路径；沿着这条路径正好有 ceiling(k/2) - 1 黑色 links（不包括 null link）。如果路径不包含红色 links，则它包含 ceiling(k/2) 个节点（并进行 ceiling(k/2) 键比较）。
我的看法：除非k = 0或1，否则不可能k == ceiling(k/2)。我开始想，也许问题出在我如何解读这句话。
如果一些次不成功的查找需要k次比较，那么每次不成功的查找至少要[=20=次] ] ceil(k/2) 比较。
那包括拿k的比较，因为k是至少ceil(k/2).
注意 "at least" 表示 >=