Применение логарифма для навигации по дереву

Question

Я когда-то знал способ использования логарифмов для перехода от одного листа дерева к следующему «упорядоченному» листу дерева. Я думаю, что это включало в себя взятие значения позиции (ранга?) «Текущего» листа и использование его в качестве начального числа для нового обхода от корня до нового целевого листа - полностью с использованием теста функции журнала, чтобы определить, следуйте по правому или левому узлу вниз к листу.

Я больше не помню, как применять эту технику. Может ли кто-нибудь повторно представить меня?

Я также не помню, требовал ли метод, чтобы дерево было сбалансировано, или оно работало на n-деревьях или только на двоичных деревьях. Любая информация будет оценена.

Answer 1

Поскольку вы упомянули, идти ли налево или направо, я предполагаю, что вы говорите именно о двоичном дереве.В таком случае, я думаю, вы правы, что есть способ.Если ваши узлы нумеруются слева направо, сверху вниз, начиная с 1, вы можете найти ранг (глубину в дереве), взяв log2 номера узла.Чтобы снова найти этот узел из корня, вы можете использовать двоичное представление числа, где 0 = слева и 1 = справа.

Например:

• n= 11

• 11 в двоичном виде - 1011

• Мы всегда игнорируем первую 1, поскольку она будет присутствовать для каждого числа (все узлыранг n будет двоичными числами с n + 1 цифрой, причем первая цифра будет 1).У нас осталось 011, то есть от корня идите налево, затем направо, потом направо.

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

Я считаю, что это работает только с сбалансированными двоичными деревьями.

Answer 2

ОК, это предложение требует больше символов, чем я могу уместить в поле для комментариев.Стивен не верит, что знание глубины узла в дереве полезно.Я думаю, что это.Я был неправ в прошлом и уверен, что буду неправ в будущем, поэтому я попытаюсь объяснить, как эта идея работает, чтобы не ошибаться в настоящем.Если я, я прошу прощения заранее.Я почти уверен, что получил его на одном из моих курсов по Алгоритмам и структурам данных, используя книгу CLR.Прошу прощения за любые ошибки в примечаниях или номенклатуре, я давно не изучал этот материал.

Цитирование wikipedia , " полное двоичное дерево - это двоичное дерево, в котором каждыйУровень, за исключением, возможно, последнего, полностью заполнен, и все узлы расположены как можно левее."

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

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

Это попытка объяснить дополнительную часть определения википедии:

"This depth is equal to the integer part of log2(n) where n 
 is the number of nodes on  the balanced tree. 

 Example 1: balanced tree with 1 node, log2(1) = 0 (depth = 0). 

 Example 2: balanced tree with 3 nodes, log2(3) = 1.59 (depth=1). 

 Example 3: balanced tree with 5 nodes, log2(5) = 2.32 
 (depth of tree is 2 nodes)."

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

Вот почему я думаю, что полезно знать глубину искомого узла.

Это немного странно, поскольку наличие "позиционного значения" - это не то, о чем мы обычно заботимся в дереве.Я могу понять, почему Стив думал об этом в терминах массива, поскольку позиционные значения присущи массивам.

- Брайан Дж. Стинар -

Answer 3

Я думаю, что нашел ответ, или, по крайней мере, факсимиле.

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

log2(1) = 0.0
log2(2) = 1
log2(3) = 1.58
log2(4) = 2
log2(5) = 2.32     
log2(6) = 2.58     
log2(7) = 2.807
log2(8) = 3
log2(9) = 3.16
log2(10) = 3.32
log2(11) = 3.459
log2(12) = 3.58

Дробная часть представляет уникальную диагональную позицию (обратите внимание, что все узлы 3, 6 и 12 имеют дробную часть 0,58).Также обратите внимание, что каждый узел принадлежит либо левой, либо правой стороне дерева, в зависимости от того, является ли дробный компонент журнала меньшим или большим 0,5.Кроме анекдотов, алгоритм поиска узла выглядит следующим образом:

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

Так, например, если вы ищете узел 11, тогда вы начнете с вычисления журнала, который равен 3.459.Тогда ...

1. 3-459 <= дробь меньше чем .5: повернуть налево и уменьшить целое число до 2. </li>
2. 2-918 <= удвоенная дробь больше чем .5: поверните направо и уменьшите целое число до 1. </li>
3. 1-836 <= удвоение. 918 дает 1,836: но учитывается только дробная часть: поверните направо и уменьшите предыдущее целое число до 0. Готово !! </li>

При соответствующем размещении та же техника работает для любого сбалансированного n-арного дерева.Например, при наличии сбалансированного троичного дерева выбор следующих левого, среднего или правого краев снова основан на дробной части бревна следующим образом:

between 0.5-0.832: turn left  (a one-third fraction range)
between 0.17-0.49: turn right  (another one-third fraction range)
otherwise go down the middle.  (the last one-third range)

Алгоритм корректируется путем умножениядробная часть на 3 вместо 2. Опять же, краткий справочник для тех, кто хочет проверить это последнее утверждение:

log3(1) = 0.0
log3(2) = 0.63          
log3(3) = 1             
log3(4) = 1.26          
log3(5) = 1.46
log3(6) = 1.63
log3(7) = 1.77
log3(8) = 1.89          
log3(9) = 2

На данный момент мне интересно, есть ли еще более краткий способ выразить это целое "основанный на журнале нисходящий выбор узла. "Мне интересно, если кто-нибудь знает ...

Answer 4

Что-то, что по крайней мере напоминает ваше описание, это Binary Heap , используемая в приоритетных очередях.

Answer 5

Случай 1: Узлы имеют указатели на своих родителей

Начиная с node, перемещайтесь вверх по указателю parent до тех пор, пока не будет найден указатель с ненулевым right_child.Перейдите к right_child и пройдите left_child, пока они не равны нулю.

Случай 2: Узлы не имеют указателей на родительский элемент

Начинаяот root найдите путь к node (включая root и node).Затем найдите самую последнюю вершину (то есть узел) в пути, которая имеет ненулевое значение right_child.Пройдите right_child и пройдите left_child, пока они не равны нулю.

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