我正在阅读Peter Brass 的《高级数据结构》。
在搜索树一章的开头，他指出搜索树有两种模型——一种是节点包含实际对象（树用作字典时的值），另一种是所有对象都存储在叶子和内部节点仅用于比较。
第二个模型比第一个模型有什么优势？
问问题
3551 次
4 回答
9
数据仅在叶节点中的二叉树的一大优点是您可以根据不在数据集中的元素进行分区。
例如，如果我有一个 0-100 万的可能数据集，但绝大多数项目要么处于高端或低端，但不在中间，我可能仍然希望我的第一次与 500,000 进行比较——即使这个数字不在我的数据集中。如果每个节点都有数据，我就无法做到这一点。虽然理论上通常不需要，但我已经多次遇到基于数据简化实现之外的值的分区。
于 2010-10-14T18:15:46.440 回答
3
B+ 树是所有键/值都存储在叶节点中的示例。这里的主要优点是，由于所有项目都在叶节点中，叶节点可以链接在一起形成一个链表，允许快速按顺序遍历。如果访问特定元素，则始终可以在序列中找到下一个元素，而无需访问任何父节点，因为叶节点链接在一起。文件系统和数据库存储系统可以利用这种结构进行范围搜索等。
于 2011-11-29T11:07:09.527 回答
1
假设您正在根据某些复杂标准在某些对象上构建树。从多个属性计算的示例。有时您无法更改此对象以存储计算值，并且计算此标准的范围很广。所以你只计算一次这个标准，并根据标准结果将对象存储在叶子中。然后，当您的树完成时，您可以更快地找到所需的对象，因为您不必为路径中的每个树节点计算标准。
于 2011-11-29T16:55:20.173 回答
0
在节点中很好地存储信息对象，在这种情况下我们谈论的是 trie，对于快速检索信息很有用（比在数组/哈希表中存储东西更快，其中最坏情况的 auf 访问是 O(n)，在 trie这是 O(m) [m 是 n 的长度])
看这里： https ://en.wikipedia.org/wiki/Trie
在搜索树中，这种操作可能要复杂得多（看 AVL Tree O(log n) ），因此可能会更慢并且更易于实现。
选择什么数据结构？？嗯，这取决于你想做什么
于 2010-10-14T18:15:12.367 回答