替罪羊树的上限

Question

Pat Morin 的免费教科书：开放数据结构：替罪羊树。 http://opendatastructures.org/ods-cpp.pdf 第 174-175 页

替罪羊树跟踪 n=节点数和 q=上限。

这个上限是多少？我认为这是树中可能存在的最大节点数，具体取决于树的高度。它不是。我如何找到上限以便我可以制作这棵树。

Answer 1

在上下文中，q 就是 the Wikipedia article 所说的 MaxNodeCount:

[..] MaxNodeCount simply represents the highest achieved NodeCount. It is set to NodeCount whenever the entire tree is rebalanced, and after insertion is set to max(MaxNodeCount, NodeCount).

（其中NodeCount在书中是n）

另外，如果删除后

NodeCount <= α * MaxNodeCount

然后整棵树重新平衡，MaxNodeCount重新设置为NodeCount的值。书中α的取值为0.5

替罪羊树的上限

Upper Bound for Scapegoat tree

c++

binary-search-tree