我买了一本关于计算几何的不错的小书。在这里和那里阅读它时，我经常偶然发现这种特殊类型的二叉搜索树的使用。这些树是平衡的，应该只将数据存储在叶节点中，而内部节点应该只存储值以引导搜索到叶节点。
下图显示了这种树的一个示例（其中叶子是矩形，内部节点是圆形）。
我有两个问题：
不在内部节点中存储数据有什么好处？
出于学习的目的，我想实现这样一棵树。因此，我认为使用 AVL 树作为基础可能是个好主意，但这是个好主意吗？
非常欢迎任何有用的资源。
问问题
3071 次
5 回答
5
不在内部节点中存储数据有什么好处？
根据设计，有些树数据结构要求内部节点中不存储任何数据，例如Huffman 代码树和B+ 树。在霍夫曼树的情况下，要求没有两个叶子具有相同的前缀（即到节点'A'的路径是101，而到节点'B'的路径是10）。在 B+ 树的情况下，它来自于它针对块搜索进行了优化（这也意味着每个内部节点都有很多子节点，并且树通常只有几层深）。
出于学习的目的，我想实现这样一棵树。因此，我认为使用 AVL 树作为基础可能是个好主意，但这是个好主意吗？
当然！AVL 树并不是非常复杂，因此它是一个很好的学习候选者。
于 2013-03-01T18:59:33.250 回答
2
其他类型的二叉树在叶子而不是内部节点处具有数据是很常见的，但对于二叉搜索树来说却相当少见。
您可能想要这样做的一个原因是教育 - 以这种方式实现二叉搜索树通常比传统方式更容易。为什么？几乎完全是因为删减。删除叶子通常很容易，而删除内部节点则更难/更麻烦。如果您的数据仅在叶子上，那么您总是很容易！
值得思考的是内部节点上的键是从哪里来的。通常它们是位于叶子（带有数据）的键的副本。稍后，如果叶子节点的键被删除，内部节点的键可能仍然会挂起。
于 2013-03-01T20:03:07.857 回答
1
不在内部节点中存储数据有什么好处？
一般来说，不将数据存储在内部节点中没有任何优势。例如，红黑树是平衡树，它将其数据存储到内部节点和叶节点中。
出于学习的目的，我想实现这样一棵树。因此，我认为使用 AVL 树作为基础可能是个好主意，但这是个好主意吗？
在我看来，确实如此。
于 2013-03-01T18:40:53.627 回答
-1
我正在阅读同一本书，他们说这可以通过任何一种方式完成，数据存储在外部或内部节点。
他们使用的树是红黑的。
无论如何，这里有一篇文章将数据存储在红黑树的内部节点上，然后将这些数据节点链接在一起作为一个列表。
Arjan van den Boogaard 在 C++ 中具有双向链表的平衡二叉搜索树
http://archive.gamedev.net/archive/reference/programming/features/TStorage/default.html
于 2013-07-27T00:46:51.483 回答
-1
仅将数据保存在叶节点（例如 B+ 树）中的一个好处是扫描/读取数据非常简单。叶节点链接在一起。因此，当您位于给定叶节点内数据的“末端”（右侧或左侧）时，要读取下一项，您只需读取指向下一个（或上一个）节点的链接/指针并跳转到下一个叶页.
对于每个节点中都有数据的 B 树，您必须遍历树才能按顺序读取数据。这当然是一个定义明确的过程，但可以说更复杂，通常需要更多的状态信息。
于 2013-03-01T19:06:45.237 回答