Диапазон запросов - дерево не содержит верхнюю и/или нижнюю границу

Question

Пусть у меня есть Binary Search Tree

 50 
    /  \ 
    17  72 
/ \ / \ 
12 23 54 76 
/\ / \ 
9 14 19  67 

К сожалению, я посасывать рисунок деревьев

Я хочу, чтобы вернуть все узлы, которые находятся в пределах определенного ассортимент. Например

[12, 23] --> {12, 14, 17, 23, 19} 

Мой подход прост

1. Найти LCA
2. Найти нижнюю границу
3. Хотя узел! = LCA.parent, добавьте правое поддерево
4. От LCA, в то время как узел! = верхняя граница, добавить левое поддерево
5. Добавить верхнее и левое поддеревье верхней границы

Однако, если одна или обе эти границы НЕ содержатся в дереве. Например,

[11, 72] --> {12, 14, 17, 23, 19, 50, 54, 67, 72} 

Мой подход кажется схожим, кроме как для поиска границ, поиск до тех пор, пока ваша граница не будет превышена дочерними узлами. Поэтому, после обнаружения «LCA» (а не истинной LCA, поскольку она не существует), найдите 11. После достижения 12, см., Что левый ребенок меньше 11, поэтому остановитесь там.

1. Есть ли более эффективное решение для выполнения этого запроса диапазона? BST не является обязательным, он просто выглядит как хорошая структура данных.
2. Будет ли мой подход работать/эффективен ли он, когда границы не содержатся в дереве?

Answer 1

Как поясняет @Nico, вам нужен рекурсивный алгоритм для перемещения по дереву, вам не нужно заботиться о LCA. Тот факт, что двоичное дерево является двоичным деревом поиска, позволяет выполнять некоторые оптимизации и избегать обхода всего дерева. например: не пересекайте левую ветвь узла, если значение узла ниже вашей нижней границы.

void FindNodesInBound(BSTNode node, int lowerBound, int upperBound, List<int> matches) { 
    if (node != null) { 
     if (node.Value >= lowerBound) 
      FindNodesInBound(node.Left, lowerBound, upperBound, matches); 
     if (node.Value >= lowerBound && node.Value <= upperBound) 
      matches.Add(node.Value); 
     if (node.Value <= upperBound) 
      FindNodesInBound(node.Right, lowerBound, upperBound, matches); 
    } 
} 

Answer 2

Одним из возможных вариантов:

• "найти" нижнее значение (12 в примере). Он возвращает структуру данных, которая позволяет перемещаться по порядку, например, std::map::iterator на C++. Проще говоря, это путь от корня до искомого узла.
• Запуск в исходном состоянии от найденного узла до достижения более высокого значения (23 в примере).

---

Так говорит вопрос, «BST не является обязательным, это только казалось хорошей структурой данных для использования.», Другой вариант, чтобы сохранить число в отсортированном массиве. Это, конечно, ограничивает возможность изменения набора чисел. В отсортированном массиве двоичный поиск для меньшего числа и начало перехода к более высокому концу (так же, как подход BST.)