Получение родительского элемента вершины в идеальном двоичном дереве

Ответ 1

Родительский индекс можно найти в 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 ^* n) наихудшее время. Они основаны на следующих свойствах пост-порядковых индексов для идеального двоичного дерева:

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

Свойства # 1 и # 2 дают простые алгоритмы для получения родительского узла для некоторых узлов дерева: для индексов формы 2 ⁱ -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; в противном случае if ((x+2) & (x+1)) == 0, добавьте 1.
4. Добавьте обратно все отличия, накопленные на шаге 2.

Например, 12 (в двоичной форме 0b1100) преобразуется на этапе № 2 в 0b0101, затем в 0b0010 (или 2 в десятичной 0b0010). Накопленная разница составляет 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 (log ² 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; в противном случае if ((x+2) & (x+1)) == 0, добавьте 1.

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

Каждый шаг этого алгоритма должен быть очевидным, за исключением, вероятно, шага №5, правильность которого должна быть доказана. Обратите внимание, что этот шаг выполняется только тогда, когда добавление результатов подсчета количества данных переносится в бит разделения, но добавление количества популяций только старших битов не приводит к этому переносу. Бит "Разделение" соответствует значению 2 ⁱ. Разница между численностью населения всех битов и количеством населения только старших бит не более i. Итак, шаг № 5 имеет значение не менее 2 ⁱ -i. Пусть применяется бит-бит-алгоритм к этому значению. 2 ⁱ -i достаточно большой, чтобы установить бит i-1. Очистите этот бит и добавьте 1 к значению в битах 0..i-2. Это значение не менее 2 ^{i -1} - (i -1), потому что мы просто вычитали 2 ^{i -1} и добавили 1. Или, если мы переместим индекс на одну позицию вправо, мы снова получим как минимум 2 ⁱ -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);
}

Ответ 2

Давайте взглянем на ваше дерево:

                     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.
• Et tetera, пока вы не приступите к тестированию n-1 >= 0.

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

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

Ответ 3

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]

Ответ 4

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

Тривиальный случай 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 ^h -1 узлы). Таким образом, используя разницу между x и left_child(x), высота x может быть определена: height(x) =ctz(x - left_child(x)), но на самом деле размера этого поддерева, которые требуют, чтобы вы хотели возьмите 1 << height любом случае, поэтому ctz можно отбросить.
Таким образом, родительский right_child(x + 1) == x x является либо x + 1 (iff right_child(x + 1) == x), либо родительский right_child(x + 1) == x x равен
x + (x - left_child(x)) * 2 (в противном случае).

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

Ответ 5

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

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

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

Ответ 6

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

Ответ 7

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

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

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

(k - 1) / 2