c++ - 替罪羊树的上限

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。