二進制搜索樹 - 搜索範圍

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