二进制搜索树 - 搜索范围

Question

如果我有一个二进制搜索树与数字对（a，b）其中（a < = b）;有没有一种算法可以帮助我找到S中的元素，其中的关键值在a，b（含）（[a，b]）的范围内。

运行时限制是O（h + k），h是S的树高度，k是该范围内元素的数量。

Answer 1

经典的答案是“算法导论”： http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap14.htm

第1步：找到一个，使用正常二叉树查找。

第2步：迭代调用树继承，直到找到b。树继任者给你树中的下一个项目：

TREE-SUCCESSOR(x) 
    if right[x] ≠ NIL 
     then return TREE-MINIMUM (right[x]) 
    y ← p[x] 
    while y ≠ NIL and x = right[y] 
     do x ← y 
     y ← p[y] 
    return y 

TREE-MINIMUM (x) 
    while left[x] ≠ NIL 
     do x ← left[x] 
    return x