BST в массиве transversal

Question

У меня есть следующая реализация двоичного дерева в массиве;

32 
/\ 
2 -5 
    /\ 
    -331 399 

Данные сгруппированы по 3 указателям за раз. index%3==0 - это значение узла, index%3==1 - это индекс значения левого узла, а index%3==2 - это индекс значения правого узла. Если левая или правая индексная ссылка равна 0, в этом направлении нет узла.

Я пытаюсь найти глубину (высоту) этого дерева. Я написал это рекурсивно

height(node): 
    if node == null: 
     return 0 
    else: 
     return max(height(node.L), height(node.R)) + 1 

Однако я хочу найти нерекурсивное решение.

Вот некоторые псевдокод я есть, предполагая дерево не пусто

int i = 0; int left = 0; int right = 0; 
while (i != n){ 
if (a[i+1] != 0){ 
    left++; 
} 
else if (a[i+2] != 0){ 
    right++; 
} 
i = i + 3; 
} 

return max (left, right) + 1; 

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

Answer 1

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

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

Одним из решений является имитация рекурсии со стеком, но это действительно не отличается от рекурсии.

Другое решение - пройти через каждый узел и определить его высоту на основе его родительского элемента, но не в определенном порядке обхода. Однако из-за того, как вы настроили эту конфигурацию, без дополнительной структуры данных для хранения иерархии, она будет менее эффективной O (n^2). Проблема в том, что вы не можете получить от ребенка родителя без полного сканирования массива. Затем вы можете сделать это в линейном времени (но рекурсия также является линейным временем, поэтому я не уверен, что мы делаем лучше. Это также не будет намного лучше с точки зрения памяти).

Можете ли вы определить, какую эффективность вы хотите улучшить?

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

«рекурсия без рекурсии» решение:

int get_height(int * tree, int length) { 

    Stack stack; 

    int max_height = 0; 

    if (length == 0) { 
     return 0; 
    } 

    // push an "array" of the node index to process and the height of its parent. 
    // make this a struct and use that for real c code 
    stack.push(0,0); 

    while(!stack.empty()) { 
     int node_index, parent_height = stack.pop(); 

     int height = parent_height + 1; 
     if (height > max_height) { 
      max_height=height; 
     } 
     if (tree[node_index+1] != 0) 
      stack.push(tree[node_index+1], height); 
     if (tree[node_index+2] != 0) 
      stack.push(tree[node_index+2], height); 

    } 

    return max_height; 
} 

Сейчас работает на действительно медленном решении, которое не использует дополнительной памяти, но это ДЕЙСТВИТЕЛЬНО плохо. Это как писать фибоначчи рекурсивно плохо. Первоначальный алгоритм прошел через каждый узел и выполнил O (n), проверит худший случай для времени выполнения O (n^2) (на самом деле не так плохо, как я изначально думал)

изменить: гораздо позже я добавляю оптимизацию, которая пропускает все узлы с дочерними элементами. Это ДЕЙСТВИТЕЛЬНО важно, поскольку оно вырезает много вызовов.Наилучшим случаем является то, что дерево фактически является связанным списком, и в этом случае оно выполняется в O (n) времени. Худший случай - полностью сбалансированное дерево - с логарифмическими листами, каждый из которых выполняет logn, обращается к корню для O ((log (n)^2). Это не так уж плохо. Линии ниже для обозначения

«очень медленно, но без дополнительной памяти» решение (но в настоящее время обновляется, чтобы не быть почти так медленно):

int get_height(int * tree, int length) { 
    int max_height = 0; 
    for (int i = 0; i < length; i+=3) { 

     // Optimization I added later 
     // if the node has children, it can't be the tallest node, so don't 
     // bother checking from here, as the child will be checked 
     if (tree[i+1] != 0 || tree[i+2] != 0) 
      continue; 

     int height = 0; 
     int index_pointing_at_me; 

     // while we haven't gotten back to the head of the tree, keep working up 
     while (index_pointing_at_me != 0) { 
      height += 1; 
      for (int j = 0; j < length; j+=3) { 
       if (tree[j+1] == tree[i] || 
        tree[j+2] == tree[i]) { 
        index_pointing_at_me = j; 
        break; 
       } 
      } 

     } 
     if (height > max_height) { 
      max_height = height; 
     } 

    } 

    return max_height; 
} 

Улучшение на предыдущее решение, но использует O (N) памяти - это предполагает, что родители всегда перед детьми в массив (который, я полагаю, технически не требуется)

int get_height(int * tree, int length) { 

    if (length == 0) 
     return 0; 

    // two more nodes per node - one for which node is its parent, the other for its height 
    int * reverse_mapping = malloc((sizeof(int) * length/3) * 2) 
    reverse_mapping[1] = 1; // set height to 1 for first node 



    // make a mapping from each node to the node that points TO it. 
    // for example, for the first node 
    // a[0] = 32 
    // a[1] = 3 
    // a[2] = 6 
    // store that the node at 3 and 6 are both pointed to by node 0 (divide by 3 just saves space since only one value is needed) and that each child node is one taller than its parent 
    int max_height = 0; 
    for (int i = 0; i < length; i+=3) { 

     int current_height = reverse_mapping[(i/3)*2+1]; 
     if (current_height > max_height) 
      max_height = current_height; 

     reverse_mapping[(tree[i+1]/3)*2] = i; 
     reverse_mapping[(tree[i+1]/3)*2 + 1] = current_height + 1; 

     reverse_mapping[(tree[i+2]/3)*2] = i; 
     reverse_mapping[(tree[i+2]/3)*2 + 1] = current_height + 1; 

    } 
    return max_height 
}