Проектирование алгоритма, который ищет k-й наибольший элемент между двумя деревьями AVL

Question

Это был заданный вопрос, прочитанный в лекции на прошлой неделе, и с тех пор я обдумываю его. Нам было предложено создать алгоритм, который ищет между двумя деревьями AVL для k-го наибольшего элемента. Каждый узел в двух деревьях содержит две части информации: ее целочисленное значение и количество дочерних элементов, которые он имеет в своем поддереве, включая сам (так что у листа будет 1 ребенок). Сложность алгоритма не может быть хуже, чем O ((logn)^2).

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

Answer 1

В качестве первого шага, пусть разработать функцию, которая для заданного верхней границы б определяет, сколько элементов в AVL-дереве менее, когда б:

count(node, b) 
    if node.key < b: 
     return node.left.size + 1 + count(node.right, b) 
    else 
     return count(node.left, b) 

Есть только один рекурсивный вызов в каждой ветви, а глубина узла увеличивается при каждом вызове. Таким образом, сложность этой функции O (log (n)).

Теперь мы можем построить требуемую функцию с помощью count:

kth(k, node1, tree2) 
    left = node1.left.size + count(tree2, node1.key) 
    if k < left: 
     return kth(k, node.left, node2.right 
    else if k == left: 
     return max(upperBound(tree2, node1.key), upperBound(node1.left, node1.key)) 
    else if k == left + 1: 
     return node1.key 
    else 
     return kth(k - node1.left.size - 1, tree2) 

Для этой функции node1 также увеличивается в каждом рекурсивном вызове, поэтому мы имеем O (журнал N) вызовы, каждый из которых требует O (журнал n) время, вызванное вызовом функции count. Общее время работы: O (log² n) при необходимости.

Для выполнения этого решения необходимо выполнить функцию upperBound, которая должна вернуть максимальный ключ в поддереве. Это можно сделать легко в o (log n) раз.

Answer 2

Предположим, что элемент k-th находится в первом дереве. Мы можем бинарно искать его позицию в дереве. Для фиксированной позиции p мы можем найти элемент p-th в дереве в O(log n) времени (начиная с корня и идя влево справа в зависимости от размера левого поддерева).

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

Когда мы знаем количество элементов, меньших заданного во втором дереве (назовем это число s), мы знаем, что его положение в объединении деревьев точно равно s + p.

Эти алгоритмы работают в O(log^2 n) времени.

Если k-й элемент не находится в первом дереве, он должен находиться во втором дереве. Поэтому мы повторяем эту процедуру для другого дерева, чтобы получить ответ в общем случае.