将所有元素存储在叶节点中有什么优点？
我正在阅读 Peter Brass 的高级数据结构。
在搜索树章节的开头，他指出搜索树有两种模型 - 一种是节点包含实际对象（如果树用作字典，则为该值），另一种是所有对象都存储在叶子和内部节点仅用于比较。
第二种模型与第一种模型相比有哪些优点？
I'm reading Advanced Data Structures by Peter Brass.
In the beginning of the chapter on search trees, he stated that there is two models of search trees - one where nodes contain the actual object (the value if the tree is used as a dictionary), and an other where all objects are stored in leaves and internal nodes are only for comparisons.
What are the advantages of the second model over the first one?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
假设您正在根据某些复杂的标准在某些对象上构建树。根据多个属性计算的示例。有时您无法更改此对象来存储计算值，并且计算此条件的范围很大。因此，您只需计算此条件一次，并根据条件结果将对象存储在叶子中。然后，当您的树完成时，您可以更快地找到所需的对象，因为您不必计算路径中每个树节点的条件。
Lets say you are building tree over some objects on some complex criteria. On example calculated from multiple properties. Sometimes you can't change this object to store calculated value and calculating this criteria is expansive. So you calculate this criteria only once, and store objects in leafs based on criteria result. Then when your tree is complete you can find required object much faster because you don't have to calculate criteria for each tree node in your path.
在节点中存储信息对象，我们在这种情况下谈论 trie，对于快速检索信息很有用（比在数组/哈希表中存储内容更快，其中最坏情况的 auf 访问是 O(n)，在 trie 中）这是 O(m) [m 是 n 的长度])
看这里：
https://en.wikipedia.org/wiki/Trie
在搜索树中，此操作可以复杂得多（查看 AVL 树 O(log n) ），因此可能会更慢并且实现起来更复杂。
选择什么数据结构？
这取决于你想做什么
well storing information objects in the nodes, we talking in this case about a trie, is usefull for fast retrival of information(faster than storing stuff in an array/hashtable, where the worst case auf acces is O(n), in the trie this is O(m) [m is the lenght of n])
look here:
https://en.wikipedia.org/wiki/Trie
In a search tree this oerations can be much more complicated(look AVL Tree O(log n) ) and so can be slower and is more compley to implement.
What data structure to choose??
Well this depends on what u want to do
数据仅位于叶节点中的二叉树的一大优点是，您可以根据数据集中不存在的元素进行分区。
例如，如果我有一个可能的数据集 0-100 万，但绝大多数项目要么处于高端或低端，但不在中间，我可能仍然希望第一次与 500,000 进行比较 - 甚至尽管这个数字不在我的数据集中。如果每个节点都有数据，我就无法这样做。虽然理论上通常不需要，但我多次遇到过基于数据简化实现之外的值进行分区的情况。
One of the big advantages of a binary tree where data is only in the leaf nodes is that you can partition based on elements that are not in your dataset.
For example, if I have a possible dataset of 0-1 million, but the vast majority of items are either at the high end or low end but not in the middle, I may still want my first compare against 500,000 - even though that number is not in my data set. If every node had data, I could not do this. While not normally needed in theory, I've run into many times that partitioning based on a value outside my data simplified implementation.
B+ 树是所有键/值都存储在叶节点中的情况的示例。这里的主要优点是，由于所有项目都在叶节点中，因此叶节点可以链接在一起形成链表，从而允许快速有序遍历。如果访问特定元素，则始终可以找到序列中的下一个元素，而无需访问任何父元素，因为叶节点链接在一起。文件系统和数据库存储系统可以利用这种结构进行范围搜索等。
B+ trees are an example of a case where all key/values are stored in leaf nodes. The primary advantage here is that since all items are in the leaf nodes, the leaf nodes can be linked together to form a linked list which allows rapid in-order traversal. If you access a particular element, you can always find the next element in the sequence without visiting any parents because the leaf nodes are linked together. Filesystems and database storage systems can take advantage of this structures for range searches and stuff.