Почему количество поддеревьев, полученных из запроса дерева диапазонов, равно O (log (n))?

Если мы сделаем предположение, что приведенное выше - это чисто функциональное двоичное дерево [wiki], поэтому там, где узлы неизменяемы, мы можем сделать «копию» этого дерева так, чтобы в дереве находились только элементы со значением больше x₁ и ниже x₂.

Давайте начнем с очень простого случая, чтобы проиллюстрировать эту мысль. Представьте, что у нас просто нет границ, чем мы можем просто вернуть все дерево. Поэтому вместо построения дерева новый мы возвращаем ссылку на корень дерева. Таким образом, мы можем без каких-либо границ вернуть дерево в О (1), если это дерево не редактируется (по крайней мере, пока мы используем поддерево).

Вышеупомянутый случай, конечно, довольно прост. Мы просто делаем «копию» (на самом деле не копию, поскольку данные неизменяемы, мы можем просто вернуть дерево) всего дерева. Итак, давайте стремимся решить более сложную проблему: мы хотим построить дерево, содержащее все элементы, превышающие пороговое значение x₁. По сути, мы можем определить для этого рекурсивный алгоритм:

1. сокращенная версия None (или того, что представляет собой нулевую ссылку или ссылку на пустое дерево) - это None;
2. если значение узла меньше порогового, мы возвращаем «вырезанную» версию правого поддерева; и
3. если значение узла превышает пороговое значение, мы возвращаем индексный дескриптор, который имеет такое же правое поддерево, а в качестве левого дочернего дочернего элемента - вырезанную версию левого дочернего дочернего элемента.

Итак, в псевдокоде это выглядит так:

def treelarger(some_node, min):
    if some_tree is None:
        return None
    if some_node.value > min:
        return Node(treelarger(some_node.left, min), some_node.value, some_node.right)
    else:
        return treelarger(some_node.right, min)

Таким образом, этот алгоритм работает в Ой) с час - высотой дерева, поскольку для каждого случая (кроме первого) мы рекурсивно переходим к один (не обоим) дочерних элементов, и он заканчивается, если у нас есть узел без дочерних элементов (или по крайней мере не имеет поддерева в том направлении, в котором нам нужно разрезать поддерево).

Таким образом, мы делаем нет, чтобы сделать копию полный дерева. Мы повторное использование много узлов в старом дереве. Мы только строим новую «поверхность», но большая часть «объема» является частью старого двоичного дерева. Хотя само дерево содержит узлы На), мы создаем максимум Ой) новых узлов. Мы можем оптимизировать вышеперечисленное так, чтобы, учитывая, что вырезанная версия одного из поддеревьев такая же, мы не создавали новый узел. Но это даже не имеет большого значения с точки зрения временной сложности: мы генерируем не более Ой) новых узлов, а общее количество узлов либо меньше исходного числа, либо такое же.

В случае полного дерева высота дерева час масштабируется с O (журнал n), и, таким образом, этот алгоритм будет работать в O (журнал n).

Тогда как мы можем создать дерево с элементами между двумя порогами? Мы можем легко переписать приведенное выше в алгоритм treesmaller, который генерирует поддерево, содержащее все элементы меньшего размера:

def treesmaller(some_node, max):
    if some_tree is None:
        return None
    if some_node.value < min:
        return Node(some_node.left, some_node.value, treesmaller(some_node.right, max))
    else:
        return treesmaller(some_node.left, max)

так что, грубо говоря, есть два отличия:

1. меняем условие с some_node.value > min на some_node.value < max; и
2. мы выполняем рекурсию по дочернему ребенку right, если условие выполняется, и слева, если оно не выполняется.

Теперь выводы, которые мы делаем из предыдущего алгоритма, также являются выводами, которые могут быть применены к этому алгоритму, поскольку он снова только вводит новые узлы Ой), а общее количество узлов может только уменьшаться.

Хотя мы может создаем алгоритм, который одновременно учитывает два порога, мы можем просто повторно использовать вышеуказанные алгоритмы для создания поддерева, содержащего только элементы в пределах диапазона: мы сначала передаем дерево функции treelarger, а затем результат через treesmaller ( или наоборот).

Поскольку в обоих алгоритмах мы вводим новые узлы Ой), а высота дерева не может увеличиваться, мы, таким образом, создаем не более O (2 ч) и, таким образом, Ой) новых узлов.

Если исходное дерево было деревом полный, значит, мы создаем новые узлы O (журнал n).

Рассмотрим поиск двух конечных точек диапазона. Этот поиск будет продолжаться до тех пор, пока не будет найден наименьший общий предок двух листовых узлов, охватывающих ваш интервал. В этот момент поиск разветвляется: одна часть движется зигзагом влево, а другая - вправо. А пока давайте сосредоточимся на той части запроса, которая разветвляется влево, поскольку логика такая же, но обратная для правой ветви.

В этом поиске полезно думать о каждом узле не как о отдельной точке, а как о диапазоне точек. Таким образом, общая процедура такова:

1. Если диапазон запроса полностью включает диапазон, представленный этим узлом, прекратите поиск по x и начните поиск в поддереве y этого узла.

2. Если диапазон запроса находится исключительно в диапазоне, представленном правым поддеревом этого узла, продолжайте поиск x вправо и не исследуйте поддерево y.

3. Если диапазон запроса перекрывает диапазон левого поддерева, то он должен полностью включать диапазон правого поддерева. Итак, обработайте y-поддерево правого поддерева, а затем рекурсивно исследуйте x-поддерево слева.

Во всех случаях мы добавляем не более одного y-поддерева для рассмотрения, а затем рекурсивно продолжаем исследование x-поддерева только в одном направлении. Это означает, что мы, по сути, прослеживаем путь вниз по x-дереву, добавляя не более одного y-поддерева за шаг. Поскольку дерево имеет высоту O (log n), общее количество y-поддеревьев, посещенных таким образом, равно O (log n). А затем, включая количество посещенных y-поддеревьев в случае, когда мы разветвлялись прямо вверху, мы получаем еще O (log n) поддеревьев для поиска в общей сложности O (log n) поддеревьев.

Надеюсь это поможет!