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

Question

У меня есть perfect binary tree, который перечислил путь после заказа. Примером такого дерева может быть

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

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

Answer 1

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

Здесь журнал ^* п означает iterated logarithm: число раз функция логарифм должна быть итеративно применяется до результата меньше или равна 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. While ((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 (log log n).

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

1. Compute количество населения индекса и добавить его к значению индекса. Самый значительный бит, который изменился с 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, правильность которого должна быть доказана. Обратите внимание, что этот шаг выполняется только тогда, когда добавление результатов подсчета количества данных переносится в бит разделения, но добавление количества популяций только старших битов не приводит к этому переносу. Бит «Разделение» соответствует значению 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); 
} 

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

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); 
} 

Answer 2

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

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

Если ответ на оба вопроса «да»: Предположим, что индекс дочернего элемента равен к, индекс родительского элемента задается

(k - 1)/2 

Answer 3

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

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

Это, однако, увлекательная проблема, и я хотел бы, чтобы меня доказали неправильно. Я просто просмотрел свою копию Hacker's Delight - у меня были большие надежды на некоторые из экзотических базовых номеров, с которыми они играют, но ничего не подойдет.

Answer 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 ^ч -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 (в противном случае).

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

Answer 5

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

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

Rewrite этикетки п в 15-п. Тогда мы получим:

     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, то в левом поддереве независимо поддерево было обнаружено, что в последней стадии. Set n = n-4
  • Если n - 4 < 0, он находится в правом поддереве любого поддерева, обнаруженного на последнем шаге. Набор n = n-1.
• Et cetera пока не приступите к тестированию n-1 >= 0.

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

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

Answer 6

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] 

Answer 7

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