Получение родителя вершины в идеальном бинарном дереве

У меня есть идеальное двоичное дерево, которое перечисляет способ пост-заказа. Примером такого дерева будет

                         15
                 7               14
             3       6       10      13
           1   2   4   5    8  9   11  12

Размер дерева мне известен. Я ищу формулу или простой алгоритм, который будет принимать одно число в качестве входных данных (идентификатор интересующей меня вершины) и возвращать также одно число - идентификатор родителя. Это довольно легко пройти через дерево сверху и получить результат в O(log n), Есть ли более быстрое решение? Меня больше всего интересуют листья, поэтому, если есть решение для особого случая, принесите его тоже.

Источник

8 ответов

Решение

Родительский индекс может быть найден во времени O (log* n) и в пространстве O(1).

Здесь log* n означает повторный логарифм: количество раз, которое функция логарифма должна быть применена итеративно, прежде чем результат станет меньше или равен 1.

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

Ниже я нарисую несколько алгоритмов, которые не требуют дополнительного пространства и дают результат в O(log n) время наихудшего случая, O(log log n) ожидаемое время, O(log log n) время наихудшего случая и O (log* п) худшее время. Они основаны на следующих свойствах индексов пост-порядка для совершенного двоичного дерева:

  1. Все индексы на крайнем левом пути дерева равны 2i-1.
  2. Индексы каждого правого потомка узла на крайнем левом пути равны 2i-2.
  3. Любой узел на крайнем левом пути и его правом поддереве помечены индексами, у которых старший значащий ненулевой бит находится в одной и той же позиции: i,
  4. Левое поддерево любого узла на крайнем левом пути содержит 2i-1 узла. (Это означает, что после вычитания 2i-1 мы получим узел, который расположен аналогичным образом относительно его родителя, имеет такую ​​же глубину, но ближе к "особым" узлам, удовлетворяющим свойствам #1 и #2).

Свойства #1 и # 2 дают простые алгоритмы для получения родительского узла для некоторых узлов дерева: для индексов вида 2i-1, умножьте на 2 и добавить 1; для индексов вида 2я-2, просто добавь 1, Для других узлов мы могли бы повторно использовать свойство #4, чтобы прийти к узлу, удовлетворяющему свойству #1 или #2 (вычитая размеры нескольких левых поддеревьев), затем найти некоторый родительский узел, расположенный на крайнем левом пути, и затем добавить обратно все ранее вычитаемые значения. А свойство № 3 позволяет быстро найти размер, какие поддеревья должны быть вычтены. Итак, у нас есть следующий алгоритм:

  1. В то время как ((x+1) & x) != 0 а также ((x+2) & (x+1)) != 0 повторите шаг 2.
  2. Очистить наиболее значимый ненулевой бит и добавить 1, Накопить разницу.
  3. Если ((x+1) & x) == 0, умножить на 2 и добавить 1; в противном случае, если ((x+2) & (x+1)) == 0, добавлять 1,
  4. Добавьте обратно все различия, накопленные на шаге 2.

Например, 12 (в двоичном виде 0b1100) преобразуется на шаге № 2 в 0b0101затем 0b0010 (или же 2 в десятичном виде). Накопленная разница 10, Шаг № 3 добавляет 1 и шаг № 4 добавляет обратно 10так что результат 13,

Другой пример: 10 (в двоичном виде 0b1010) преобразуется на шаге № 2 в 0b0011 (или же 3 в десятичном виде). Шаг № 3 удваивает его (6), затем добавляет 1 (7). Шаг № 4 добавляет обратно накопленную разницу (7), так что результат 14,

Временная сложность составляет O(log n) - но только когда все элементарные операции выполняются за O(1) время.

Чтобы улучшить временную сложность, мы могли бы выполнить несколько итераций шага № 2 параллельно. Мы могли бы получить n/2 старшие разряды индекса и подсчет численности населения рассчитывают на них. Если после добавления результата к оставшимся младшим битам сумма не переполняется этими старшими битами, мы могли бы применить этот подход рекурсивно, со сложностью O(log log n). Если бы у нас было переполнение, мы могли бы вернуться к первоначальному алгоритму (побитовый). Обратите внимание, что все установленные младшие биты также должны рассматриваться как переполнение. Таким образом, получаемая сложность составляет O (log log n) ожидаемого времени.

Вместо того, чтобы откатываться к битам, мы могли бы справиться с переполнением, используя бинарный поиск Мы могли бы определить, сколько старших битов (меньше, чем n/2) должны быть выбраны так, чтобы у нас не было переполнения или (как для индекса 0b00101111111111) количество выбранных ненулевых старших битов точно 1, Обратите внимание, что нам не нужно применять эту процедуру двоичного поиска более одного раза, потому что второе переполнение не произойдет, пока число битов в числе больше, чем O(log log n). Таким образом, получаемая сложность равна O (log log n) времени наихудшего случая. Предполагается, что все элементарные операции выполняются за O(1) раз. Если некоторые операции (подсчет населения, ведущий нулевой счет) осуществляются за время O (log log n), то наша временная сложность возрастает до O (log2 log n).

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

  1. Вычислить численность населения индекса и добавить его к значению индекса. Наиболее значимый бит, который изменился с 0 в 1 определяет точку разделения для старших / младших битов.
  2. Вычислить численность населения по старшим битам, затем добавить результат к младшим битам.
  3. Если "разделительный" бит не равен нулю и ((x+1) & x) != 0 а также ((x+2) & (x+1)) != 0, продолжайте с шага № 1.
  4. Если все младшие биты установлены и младший значащий старший бит установлен, обработайте этот угловой случай как правый дочерний.
  5. Если ((x+1) & x) != 0 а также ((x+2) & (x+1)) != 0Также обработайте это как право ребенка.
  6. Если ((x+1) & x) == 0, умножить на 2 и добавить 1; в противном случае, если ((x+2) & (x+1)) == 0, добавлять 1,

Если условие шага № 3 удовлетворяется, это означает, что добавление на шаге № 2 привело к переходу в бит "разделения". Другие младшие биты представляют некоторое число, которое не может быть больше, чем исходный счетчик численности. Количество установленных битов в этом числе не может быть больше, чем логарифм счетчика чисел исходного значения. Это означает, что число установленных битов после каждой итерации составляет не более логарифма от числа установленных битов на предыдущей итерации. Поэтому сложность времени в наихудшем случае составляет O (log* n). Это очень близко к O(1). Например, для 32-битных чисел нам нужно примерно 2 итерации или меньше.

Каждый шаг этого алгоритма должен быть очевидным, за исключением, вероятно, шага № 5, правильность которого нужно доказать. Обратите внимание, что этот шаг выполняется только в том случае, если добавление счетчика заполнений приводит к переносу в бит "разделения", но добавление счетчика заполненности только для старших битов не приводит к переносу. Бит "разделение" соответствует значению 2i. Разница между количеством заполненных битов и количеством заполненных битов только старшего разряда i, Таким образом, шаг № 5 имеет значение как минимум 2i-i. Давайте применим побитовый алгоритм к этому значению. 2я-я достаточно большой, так что немного i-1 установлено. Очистите этот бит и добавьте 1 в значение в битах 0..i-2, Это значение по крайней мере 2i-1- (i-1), потому что мы только что вычли 2i-1 и добавили 1, Или, если мы переместим указатель на одну позицию вправо, у нас снова будет как минимум 2i-i. Если мы повторим эту процедуру, мы всегда найдем ненулевой бит в позиции i-1, Каждый шаг постепенно уменьшает разницу между значениями в битах 0..i-1 и ближайшая сила 2, Когда эта разница приходит к 2мы могли бы остановить этот побитовый алгоритм, потому что текущий узел явно является правильным потомком. Поскольку этот побитовый алгоритм всегда приводит к одному и тому же результату, мы могли бы его пропустить и всегда обрабатывать текущий узел как правильный дочерний элемент.

Вот реализация этого алгоритма на C++. Более подробную информацию и некоторые другие алгоритмы можно найти на ideone.

uint32_t getMSBmask(const uint32_t x)
{ return 1 << getMSBindex(x); }

uint32_t notSimpleCase(const uint32_t x)
{ return ((x+1) & x) && ((x+2) & (x+1)); }

uint32_t parent(const uint32_t node)
{
    uint32_t x = node;
    uint32_t bit = x;

    while ((x & bit) && notSimpleCase(x))
    {
        const uint32_t y = x + popcnt(x);
        bit = getMSBmask(y & ~x);
        const uint32_t mask = (bit << 1) - 1;
        const uint32_t z = (x & mask) + popcnt(x & ~mask);

        if (z == mask && (x & (bit << 1)))
            return node + 1;

        x = z;
    }

    if (notSimpleCase(x))
        return node + 1;
    else
        return node + 1 + (((x+1) & x)? 0: x);
}

Если нам нужно найти родителя только для конечного узла, этот алгоритм и код могут быть упрощены. ( Идеально).

uint32_t parent(const uint32_t node)
{
    uint32_t x = node;

    while (x > 2)
    {
        const uint32_t y = x + popcnt(x);
        const uint32_t bit = getMSBmask(y & ~x);
        const uint32_t mask = (bit << 1) - 1;
        x = (x & mask) + popcnt(x & ~mask);
    }

    return node + 1 + (x == 1);
}
Источник 
function getParent(node, size)
{
    var rank = size, index = size;

    while (rank > 0) {
        var leftIndex = index - (rank + 1)/2;
        var rightIndex = index - 1;

        if (node == leftIndex || node == rightIndex) {
            return index;
        }

        index = (node < leftIndex ? leftIndex : rightIndex);
        rank  = (rank - 1)/2;
    }
}

Он начинается с корня, решая, в какую ветку переходить, и повторяется до тех пор, пока узел не будет найден. Ранг - это индекс самого левого узла на том же уровне: 1, 3, 7, 15, ..., k^2 - k + 1,

Входные параметры:

  • node - Индекс узла, родитель которого вы хотите. (На основе 1)
  • size - индекс корневого узла; 15 в вашем примере.

Пример:

>>> r = []; for (var i = 1; i <= 15; i++) r.push(parent(i,15)); r;
[3, 3, 7, 6, 6, 7, 15, 10, 10, 14, 13, 13, 14, 15, undefined]
Источник

Давайте посмотрим на ваше дерево:

                     15
             7               14
         3       6       10      13
       1   2   4   5    8  9   11  12

Перепишите метку n как 15-n. Тогда мы получим:

                     0
             8               1
         12      9        5       2
       14  13  11  10   7   6   4   3

который также может быть записан как

                     0
             +8              +1
         +4      +1      +4      +1
       +2  +1  +2  +1  +2  +1  +2   +1

Ну, есть образец для вас. Таким образом, в этой схеме маркировки оставленные дети 2^(i+1) больше, чем их родители, где i рост ребенка, в то время как правильные дети 1 больше, чем их родители. Как мы можем определить рост ребенка, и будь то левый или правый ребенок?

К сожалению, я не могу найти способ получить эту информацию, не продумав весь путь к узлу, что означает логарифмическое время. Однако вы можете вывести путь к узлу непосредственно из метки узла (продемонстрировано здесь для дерева высоты-3):

  • Предположим, у нас есть ярлык n
  • Если n == 0корень.
  • Иначе:
    • Если n - 8 >= 0Это в левом поддереве корня. Задавать n = n-8,
    • Если n - 8 < 0Это в правильном поддереве корня. Задавать n = n-1,
  • Если n == 0 теперь это корень любого поддерева, обнаруженного на последнем шаге.
  • Иначе:
    • Если n - 4 >= 0он находится в левом поддереве любого поддерева, обнаруженного на последнем шаге. Задавать n = n-4
    • Если n - 4 < 0он находится в правом поддереве любого поддерева, обнаруженного на последнем шаге. Задавать n = n-1,
  • И так далее, пока вы не приступили к тестированию n-1 >= 0,

Вы можете сделать все это, используя немного арифметики и -1и в реальных условиях это будет невероятно быстро (вычисление этого в дереве из триллионного узла займет всего ~12 раз больше, чем в дереве из 10 узлов (игнорируя проблемы с памятью)), но это все равно будет логарифмическое время.

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

Источник 
import math
def answer(h,q=[]):
    ans=[]
    for x in q:
        if(True):
            curHeight=h;
            num=int(math.pow(2,h)-1)
            if(x==num):
                ans.append(-1)
            else:
                numBE=int(math.pow(2,curHeight)-2)
                numL=int(num-int(numBE/2)-1)
                numR=int(num-1)
                flag=0
                while(x!=numR and x!=numL and flag<10):
                    flag=flag+1
                    if(x>numL):
                        num=numR
                    else:
                        num=numL
                    curHeight=curHeight-1
                    numBE=int(math.pow(2,curHeight)-2)
                    numL=num-(numBE/2)-1
                    numR=num-1
                ans.append(num)
    return ans
Источник

Если вам разрешено запрашивать идентификаторы дочерних узлов, вы можете сделать несколько полезных вещей.

Тривиальный случай 1: если x = size это корень.

Тривиальный случай 2: если x это лист (запросить дочерние идентификаторы, чтобы узнать), попробуйте x + 1, Если x + 1 не является листом (другой запрос для дочерних идентификаторов), x был правильным ребенком x + 1, Если x + 1 это лист, x левый ребенок x + 2,

Для внутренних узлов: дети x являются x - 1 (правильный ребенок) и x - (1 << height(x) - 1) (левый потомок, правый потомок - идеальное двоичное дерево, поэтому он имеет 2 ч -1 узла). Итак, используя разницу между x а также left_child(x) высота x можно определить: height(x) =ctz(x - left_child(x)), но это действительно размер этого поддерева, который требуется, чтобы вы взяли 1 << height во всяком случае, так ctz можно бросить.
Так что родитель x либо x + 1 (МФЛ right_child(x + 1) == x) или родитель x является
x + (x - left_child(x)) * 2 (иначе).

Это не так хорошо, как просто выполнять математику для идентификатора, но при условии, что вам разрешено запрашивать дочерние элементы узла в постоянное время, это алгоритм с постоянным временем.

Источник

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

Каждый бит в индексе узла потенциально влияет на почти каждое решение влево / вправо / стоп при прохождении от узла к корню, включая первый. Более того, изучая индексы узлов на каждом уровне дерева, они апериодичны (и не только по степеням 2). Это означает (я думаю), что постоянного числа арифметических операций недостаточно для определения уровня или того, является ли узел левым или правым дочерним элементом.

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

Источник

python, верните -1 для корневого узла:

      def find_parent(h, n):
parent = -1
root = 2 ** h -1
while root >= n:
    left_top = root - 2 ** (h-1)
    right_top = root - 1
    print(f"parent:{parent}, root:{root}, left:{left_top}, right:{right_top}")
    if n >= root:
        return parent
    if n == left_top or n == right_top:
        return root
    if n < left_top:
        parent = root
        root = left_top
        h -= 1
    if n > left_top:
        parent = root
        root = right_top
        h -= 1
return parent
Источник

Когда вы говорите "это перечисляется в порядке пост-заказа", вы имеете в виду, что у вас есть индексированное представление дерева? Я имею в виду, является ли внутренняя структура данных массивом или чем-то подобным?

Кроме того, у вас есть индекс элемента, который вас интересует в родительском элементе?

Если ответ на оба вопроса "да": при условии, что индекс дочернего элемента равен k, индекс родительского элемента определяется как

(k - 1) / 2
Источник
Другие вопросы по тегам