data-structures - 将所有元素存储在叶节点中的优点是什么？

Question

我在看 高级数据结构 彼得·布拉斯。

在搜索树一章的开头，他指出搜索树有两种模型——一种是节点包含实际对象(如果树用作字典的值)，另一种是所有对象都存储在叶子和内部节点仅用于比较。

与第一个模型相比，第二个模型有哪些优势？

Answer 1

数据仅位于叶节点中的二叉树的一大优势是您可以根据不在数据集中的元素进行分区。

例如，如果我有一个可能的数据集 0-100 万，但绝大多数项目要么处于高端或低端但不在中间，我可能仍然希望我的第一次与 500,000 进行比较 - 即使是这个数字不在我的数据集中。如果每个节点都有数据，我就做不到这一点。虽然理论上通常不需要，但我已经多次遇到基于数据简化实现之外的值的分区。