Двоичное дерево поиска - поиск области

Question

Если у меня есть дерево двоичного поиска S с номером пары (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