data-structures - 为什么只在平衡的二分查找树的叶节点中存储数据？

Question

我买了一本不错的关于计算几何的小书。当在这里和那里阅读它时，我经常偶然发现这种特殊类型的二进制搜索树的用法。这些树是平衡的，应仅将数据存储在叶节点中，而内部节点应仅存储值以指导向下搜索到叶。

下图显示了这些树的示例(其中叶子是矩形，内部节点是圆形)。

我有两个问题:

不在内部节点中存储数据的优点是什么？

为了学习，我想实现这样一棵树。因此，我认为使用AVL树作为基础可能是一个好主意，但这是一个好主意吗？

任何有用的资源都是非常欢迎的。

Answer 1

What is the advantage of not storing data in the inner nodes?

根据设计，有些树数据结构要求内部节点中不存储任何数据，例如Huffman code trees和B+ trees。在霍夫曼树的情况下，要求没有两个叶子具有相同的前缀(即，到节点“A”的路径是101，而到节点“B”的路径是10)。对于B +树，这是因为它针对块搜索进行了优化(这也意味着每个内部节点都有很多子节点，并且树通常只有几层深)。

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树并不是非常复杂，因此它是学习的不错选择。