BST в массиве обхода
У меня есть следующая реализация двоичного дерева в массиве;
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;
Я не думаю, что это правильно, и мне нужна помощь, чтобы понять, как сделать это правильно.
1 ответ
Вы не сказали, в чем ваша проблема с рекурсией, чтобы мы поняли, какое поведение вы хотите улучшить.
Есть много решений для этого, но почти все они имеют такую же или худшую производительность, как ваше рекурсивное решение. Действительно, лучшими решениями будут вещи, которые вы должны будете сделать, когда создаете дерево. Например, вы можете сохранить высоту каждого узла в четвертом индексе массива для каждого узла. Затем выполняется тривиальное сканирование каждого четвертого индекса для определения максимальной высоты. Также было бы проще, если бы у узлов были родительские ссылки, хранящиеся вместе с ними, чтобы их не нужно было вычислять во время проверки высоты.
Одним из решений является симуляция рекурсии с помощью стека, но на самом деле это ничем не отличается от рекурсии.
Другое решение состоит в том, чтобы пройти через каждый узел и определить его высоту на основе его родителя, но не в определенном порядке обхода. Однако из-за того, как вы это настроили, без вторичной структуры данных для хранения иерархии, она будет менее эффективной O(n^2). Проблема в том, что вы не можете получить от ребенка к его родителю без полного сканирования массива. Затем вы можете сделать это за линейное время (но рекурсия также является линейным временем, поэтому я не уверен, что у нас все будет лучше. Это также не будет намного лучше с точки зрения памяти).
Можете ли вы определить, какой тип эффективности вы хотите улучшить?
Вот псевдокод для каждого, но я полагаюсь на несколько структур данных, которые нелегко представить:
Решение "рекурсия без рекурсии":
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, каждый из которых выполняет 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
}