fok*_*ute 13 binary-search-tree data-structures
我正在阅读Peter Brass的高级数据结构.
在关于搜索树的章节的开头,他说有两种搜索树模型 - 一种是节点包含实际对象(如果树用作字典的值),另一种是所有对象存储在叶子和内部节点仅用于比较.
第二个模型比第一个模型有什么优势？
数据仅在叶节点中的二叉树的一大优势是,您可以根据数据集中不存在的元素进行分区.
例如,如果我有一个0-1百万的可能数据集,但绝大多数项目要么处于高端或低端而不是中间,我可能仍然希望我的第一次比较为500,000 - 即使这个数字不在我的数据集中.如果每个节点都有数据,我就无法做到这一点.虽然理论上通常不需要,但我已经多次遇到基于数据简化实现之外的值的分区.
小智 0
在节点中存储信息对象，我们在这种情况下谈论 trie，对于快速检索信息很有用（比在数组/哈希表中存储内容更快，其中最坏情况的 auf 访问是 O(n)，在 trie 中）这是 O(m) [m 是 n 的长度])
看这里： https: //en.wikipedia.org/wiki/Trie
在搜索树中，此操作可能要复杂得多（查看 AVL 树 O(log n) ），因此可能会更慢并且实现起来更复杂。
选择什么数据结构？这取决于你想做什么