binary-tree - 如何有效地到达二叉搜索树的叶子？

Question

我想对 BST 叶子中的所有值求和。显然，如果不遍历整棵树，我就无法到达树叶。这是真的？我可以在不花费 O(N) 时间的情况下到达树叶吗？

Answer 1

你意识到叶子本身至少是 O(n) 的 1/2 吗？

Answer 2

如果不遍历整棵树（尤其是如果您想要每一片叶子），就无法获得树的叶子，不幸的是，这将在 O(n) 时间内运行。如果您想访问所有这些叶子，您确定树是存储数据的最佳方式吗？还有其他数据结构可以更有效地访问您的数据。

Answer 3

要访问 BST 的所有叶节点，您必须遍历 BST 的所有节点，这将是 O(n) 的顺序。

一种替代方法是使用 B+ 树，您可以在 O(log n) 时间内遍历到叶节点，然后可以顺序访问所有叶节点以计算总和。因此，在您的情况下，它将是 O(log n + k)，其中 k 是叶节点的数量，n 是 B+ 树中的节点总数。

干杯

Answer 4

您将不得不遍历树搜索没有子节点的节点，或者修改用于表示树的结构以包含叶节点列表。这也将需要修改您的插入和删除方法以维护列表（例如，如果您从节点中删除最后一个子节点，它将成为叶节点）。除非树非常大，否则只要继续遍历树就足够了。