Как я могу рассчитать уровень узла в идеальном двоичном дереве из индекса глубины первого порядка?

Question

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

(Например, в дереве с 3 уровнями корневой узел имеет индекс 0, первый ребенок имеет 1, первый ребенок первого ребенка имеет 2, второй ребенок первого ребенка имеет 3, второй ребенок имеет 4 , первый ребенок второго ребенка имеет 5, второй ребенок второго ребенка имеет индекс 6.

 0 
    / \ 
    1  4 
/\ /\ 
2 3 5 6 

)

Я знаю, что размер дерева (число узлов/максимальный уровень), но только индекс конкретного узла, и мне нужно рассчитать его уровень (то есть его расстояние до корневого каталога). Как это сделать наиболее эффективно?

Answer 1

let i - указатель, который вы ищете, и n - общее количество узлов.

Этот алгоритм делать то, что вы хотите:

level = 0 
while i != 0 do 
    i-- 
    n = (n-1)/2 
    i = i%n 
    level++ 
done 

0 является индексом корня, если i = 0 тогда вы на хорошем уровне, иначе вы можете удалить корень и вы получите два поддерева n = (n-1)/2 обновляет количество узлов - это новое дерево (которое является поддеревом старого), а i = i%n выбирает только хорошее поддерево.

Answer 2

EDIT: попытка номер 1 ... работает только для BFS.

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

parentIndex = (index-1)/2 

Таким образом, вы можете повторить эту формулу, пока вы не получите < = 0, каждый раз, когда вы зацикливаете, вы по существу поднимаетесь на уровень в дереве.

EDIT: Попытка номер 2 ..

Лучшим способом я могу думать, делать бы O (индекс + § п), который является O (п). Делайте DFS до тех пор, пока не достигнете нужного индекса, затем продолжайте идти вверх по дереву с помощью указателя родителя, пока не достигнете корня, отслеживающего количество раз, когда вы поднялись. Это предполагает, что родительский указатель существует на каждом узле.

Answer 3

Кажется, что ходьба по дереву непосредственно должна быть достаточно эффективной.

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

Например, позволяет искать в дереве 4 уровня с 15 элементами

    (root node)(left elements)(right elements) 
Starting range: (0)(1 2 3 4 5 6 7)(8 9 10 11 12 13 14) 
Go left  : (1)(2 3 4)(5 6 7) 
Go right  : (5)(6)(7) 
Found node, total depth 2 

Вы должны быть в состоянии сделать это с помощью простого цикла, используя только несколько переменных, чтобы сохранить начало и конец диапазонов. Вы также можете легко адаптировать это, если вы выполняете некоторые незначительные изменения, такие как использование обхода post/pre/in-order или начало индексов формы 1 вместо 0.

Answer 4

Если все, что у вас есть, это индекс, вы не может найти глубину.

Предположим, у вас есть дерево, как это:

1 
/\ 
    2 5 
/\ 
3 4 

Узел с индексом 3 имеет глубину 2.

Предположим, у вас есть дерево, как это:

1 
/\ 
2 3 
/\ 
    4 5 

узел с индексом 3 имеет глубину 1.

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

Редактировать: Если вы имеете в виду идеальное двоичное дерево, как в, все листья находятся на одной глубине, и каждый родитель имеет двух детей, то вы все равно не можете найти глубину.

Сравните эти два дерева:

1 
/\ 
2 3 


     1 
/ \ 
    2  5 
/\ /\ 
3 4 6 7 

Глубина узла 3 изменяется в зависимости от высоты дерева.

Edit 2: если вы знаете высоту общего дерева, вы можете использовать этот рекурсивный алгоритм:

def distanceFromRoot(index, rootIndex, treeHeight): 
    if index == rootIndex: 
     return 0 
    leftIndex = rootIndex+1 
    rightIndex = rootIndex + 2**treeHeight 
    if index >= rightIndex: 
     return 1 + distanceFromRoot(index, rightIndex, treeHeight-1) 
    else: 
     return 1 + distanceFromRoot(index, leftIndex, treeHeight-1) 

Answer 5

UNTESTED:

int LevelFromIndex(int index, int count) 
{ 
    if (index == 0) 
     return 0; 
    if (index > (count - 1)/ 2) 
     index -= (count - 1)/2; 
    return 1 + LevelFromIndex(index - 1, (count - 1)/2); 
} 

Здесь count общее число узлов в дерево.

Answer 6

Итак, у нас есть такое дерево с 4-х уровней:

  0    - 0th level 
    /  \   
    1   8  - 1th level 
/\  /\  
    2 5  9 12 - 2th level 
/\ /\ /\ /\ 
3 4 6 7 10 11 13 14 - 3th level 

Как вы можете видеть, каждый левый потомок имеют индекс корня увеличивается на один (левый = корень + 1), потому что в ДФС оставил ребенка всегда посещения сначала. Второй узел имеет индекс левого узла, увеличенный по размеру левого поддерева (правый = левый + левый). Если мы знаем глубину дерева, мы можем рассчитать его размер (size = 2^depth - 1). Поскольку левое поддерево имеет глубину, равную глубине родительской, уменьшенной на единицу, ее размер = 2^(parentDepth - 1) - 1.

Итак, теперь мы имеем алгоритм - вычисляем индекс левого узла, вычисляем индекс правого узла. Если индекс узла лежит между ним, перейдите на левый узел, иначе - перейдите в правый узел.

Код:

static int level(int index, int root, int treeDepth) { 
     if (index == root) 
      return 0; 

     if (treeDepth <= 0 /* no tree */ || treeDepth == 1 /* tree contains only root */) 
      throw new Exception("Unable to find node"); 

     int left = root + 1; 
     int right = left + (int)Math.Pow(2, treeDepth - 1) - 1; 

     if (index == left || index == right) 
      return 1; 

     if (left < index && index < right) 
      return 1 + level(index, left, treeDepth - 1); 
     else 
      return 1 + level(index, right, treeDepth - 1); 
    } 

Answer 7

Вот еще одно предложение, что сделало бы решение этого вопроса проще:

Если вы маркировать узлы с индексом в ширину, первый заказ, вы можете вычислить уровень без обхода в O (1) раз. Поэтому, если вы выполняете несколько запросов, вы можете сделать O (N) BFT и получить каждый запрос в течение O (1).

Формула уровня:

level = floor(log(index + 1)) 

Если бревно к основанию 2

Попробуйте его на этом дереве:

 0 
    / \ 
    / \ 
    1  2 
/\ /\ 
/ \ / \ 
3  4 5  6 

Приветствие.