algorithm - 计算 O(LogN) 中二叉搜索树范围内的节点数

Question

给定一个 BST 和两个整数 'a' 和 'b' (a < b)，我们如何在 O(log n) 中找到满足 a < 节点值 < b 的节点数？

我知道可以很容易地在 LogN 时间内找到 a 和 b 的位置，但是如何计算中间的节点而不进行遍历，这是 O(n)？

Answer 1

在二叉搜索树的每个节点中，还要计算树中小于其值的值的数量(或者，对于下面脚注中提到的不同树设计，其左子树中的节点) .

现在，首先找到包含值a 的节点。获取已存储在此节点中的小于a 的值的计数。这一步是Log(n)。

现在找到包含值b 的节点。获取存储在此节点中的小于 b 的值的计数。这一步也是Log(n)。

将这两个计数相减，得到a 和b 之间的节点数。此搜索的总复杂度为 2*Log(n) = O(Log(n))。

---

_{参见 this video .教授在这里使用 Splay Trees 解释了你的问题。}