为什么仅将数据存储在平衡二叉搜索树的叶节点中？

Question

我买了一本关于计算几何的好书.在这里和那里阅读时,我经常偶然发现使用这种特殊的二叉搜索树.这些树是平衡的,应该只在叶节点中存储数据,而内部节点应该只存储值以引导搜索到叶子.

下图显示了此树的示例(其中叶子是矩形,内部节点是圆圈).

我有两个问题:

1. 不在内部节点中存储数据有什么好处？

2. 出于学习的目的,我想实现这样一棵树.因此,我认为使用AVL树作为基础可能是一个好主意,但这是一个好主意吗？

任何有用的资源都非常受欢迎.

Answer 1

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

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

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

当然！AVL树并不是非常复杂，因此它是学习的不错选择。

Answer 2

内部节点不存储数据有什么好处？

一般来说，不在内部节点存储数据没有任何优势。例如，红黑树是平衡树，它将数据存储在内部节点和叶子节点中。

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

我认为是的。