计算O(LogN)中二进制搜索树内范围内的节点数

Question

给定一个BST和两个整数'a'和'b'(a <b),我们怎样才能找到节点的数量,一个<节点值<b,在O(log n)中？

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

Answer 1

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

现在,首先找到包含该值的节点a.获取的值小a于此节点中存储的值.这一步是Log(n).

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

减去两个计数,你有a和之间的节点数b.此搜索的总复杂度为2*Log(n)= O(Log(n)).

_{观看此视频.教授通过使用Splay Trees解释了你的问题.}