为什么只在平衡的二分查找树的叶节点中存储数据? [英] Why storing data only in the leaf nodes of a balanced binary-search tree?
问题描述
我买了一本不错的关于计算几何的小书.当在这里和那里阅读它时，我经常偶然发现这种特殊类型的二进制搜索树的用法.这些树是平衡的，应仅将数据存储在叶节点中，而内部节点应仅存储值以指导向下搜索到叶.
I have bought a nice little book about computational geometry. While reading it here and there, I often stumbled over the use of this special kind of binary search tree. These trees are balanced and should store the data only in the leaf nodes, whereas inner nodes should only store values to guide the search down to the leaves.
下图显示了这些树的示例(叶子是矩形，内部节点是圆形).
The following image shows an example of this trees (where the leaves are rectangles and the inner nodes are circles).
我有两个问题:
-
不在内部节点中存储数据有什么好处?
What is the advantage of not storing data in the inner nodes?
出于学习的目的，我想实现一棵这样的树.因此，我认为使用AVL树作为基础可能是一个好主意，但这是一个好主意吗?
For the purpose of learning, I would like to implement such a tree. Therefore, I thought it might be a good idea to use an AVL tree as the basis, but is it a good idea?
非常欢迎您提供任何有用的资源.
Any kind of helpful resource is very welcome.
推荐答案
不将数据存储在内部节点中有什么好处?
What is the advantage of not storing data in the inner nodes?
根据设计，有些树数据结构要求内部节点中不存储任何数据，例如 B +树.在霍夫曼树的情况下，要求没有两个叶子具有相同的前缀(即，到节点"A"的路径是101，而到节点"B"的路径是10).对于B +树，这是因为它针对块搜索进行了优化(这也意味着每个内部节点都有很多子节点，并且树通常只有几层深).
There are some tree data structures that, by design, require that no data is stored in the inner nodes, such as Huffman code trees and B+ trees. In the case of Huffman trees, the requirement is that no two leaves have the same prefix (i.e. the path to node 'A' is 101 whereas the path to node 'B' is 10). In the case of B+ trees, it comes from the fact that it is optimized for block-search (this also means that every internal node has a lot of children, and that the tree is usually only a few levels deep).
出于学习目的，我想实现一棵这样的树.因此，我认为使用AVL树作为基础可能是一个好主意，但这是一个好主意吗?
For the purpose of learning, I would like to implement such a tree. Therefore, I thought it might be a good idea to use an AVL tree as the basis, but is it a good idea?
当然！ AVL树并不是非常复杂，因此它是学习的不错选择.
Sure! An AVL tree is not extremely complicated, so it's a good candidate for learning.
这篇关于为什么只在平衡的二分查找树的叶节点中存储数据?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
