Avl дерево - найти первый ключ отсутствует в дереве после того, как я

Question

У меня есть вышеуказанная проблема, которую я пытаюсь решить.У дерева Avl также есть размер поддерева для каждого узла, и я знаю максимум.Мне нужно найти следующий первый номер после i, которого нет в дереве.Мне нужно сделать это в O(logn) время.

Я попал в

if i bigger/equal the maximum then return i+1,

Я пытался сделать другие случаи, чтобы найти минимум после i это в дереве, и я знаю, что могу сделать это в O(logn), если найденное число больше i+1 return i+1.

Теперь я понимаю, что если в дереве есть i+1, мне нужно продолжать поиск, но сложность времени становится больше, чем мне нужно.Буду очень признателен за любые рекомендации.Я не ищу код, только идею или руководство, как решить его в указанное время

Answer 1

В качестве подсказки подумайте, как бы вы решили эту проблему, если бы у вас были элементы в массиве, а не в дереве AVL.Как бы вы решили эту проблему за время O (log n) в массиве с помощью модифицированного бинарного поиска?

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

Answer 2

Я думаю, что ваша проблема может быть более сложной в анализе временной сложности, чем фактический алгоритм.

Мы знаем, что при правильном выполнении время поиска в правильно сформированном дереве AVL высотой log[2](n) всегда будет log[2](n). Поиск пропущенного элемента в этом случае ничем не отличается от поиска существующего элемента.

Допустим, у вас есть дерево AVL A, и оно включает i и i+1. Тогда мы знаем, что i+1 должен быть либо родительским узлом i, а i - левым дочерним узлом, либо i+1 - правым дочерним узлом i. Итак, мы можем сделать вывод:

if i ^ i+1 in A => i+1(l)=i v i(r)=i+1

Таким образом, если вы найдете i и его родительский узел не равен i+1, то его правый дочерний узел должен быть i+1. Вы можете расширить это значение до i=i+1 после нахождения i+1 и продолжать проверять это условие. Самое интересное в том, что есть только одно место, на которое нужно смотреть для каждого значения i+n после i, если вы отслеживаете узлы, через которые вы прошли.

Если вы пройдете через [i+7, i+4, i], вы сразу узнаете, что если A содержит i, то оно не может содержать i+1. Это связано с i+1 < i+4, но i < i+1 < i+4.

Если вы пройдете через [i-6, i-2, i], вы также сразу узнаете, что если A содержит i+1, то оно не может содержать i+1. Это связано с i-2 < i+1, но i-2 < i < i+1.

Если вам нужно было пройти через [i+7, i+3, i+1, i], вы нашли i, i+1 и, поскольку i+3 не равно i+2, вы знаете, i+2 должен быть правым дочерним узлом i+1, поскольку он должен не быть ребенком i+3, поскольку он меньше, но i+1 уже занял позицию левого ребенка. Таким образом, вы проверяете, является ли i+1 правый дочерний элемент i+2, вы продолжаете проверять i+4 с i+3, по существу, используя алгоритм:

define stack //use your favourite stack implementaion
let n = root node
let i = yourval
while n.val != i
     stack.push(n)
     if i > n.val
         n = n.right
     else //equivalent to "else if i < n.val" since loop condition ensures they are not equal
         n = n.left

while !stack.empty
    if stack.peek.right.val != queue.peek.val + 1
        //Implies parent holds value
        temp = stack.pop.val + 1
        if(temp != stack.peek.val) //If the parent does not hold the next value return it
            return temp;
    else //Right child holds value
         stack.push(queue.peek.right)
         i = stack.peek.val
return i+1 //if the stack is empty eventually return the next value

Из-за того, как формируются деревья AVL, ваш стек будет не более 2*logn[2](n) элементов большого размера (если i - это лист на LHS, а последнее значение - это лист на RHS). Таким образом, в целом ваш поиск займет log[2](n) для начального поиска i и еще одного 2*log[2](n) вместе взятых, что составляет 3*log[2](n), что в Большом Омикроне все еще равно O(log[2](n)).