Что значит использовать обратные указатели в сбалансированном по высоте дереве?
Я должен написать код дерева с сбалансированной высотой с обратными указателями, основанный на коде дерева с сбалансированной высотой ниже. Я должен изменить приведенный ниже код таким образом, чтобы больше не использовались стеки для следования по пути вверх во время перебалансировки; вместо этого каждый некорневой узел должен иметь дополнительное поле вверх, которое указывает на верхний сосед узла. Эти поля должны быть установлены правильно, особенно при поворотах и при выполнении вставки или удаления на уровне листа.
#include <stdio.h>
#include <stdlib.h>
#define BLOCKSIZE 256
typedef int object_t;
typedef int key_t;
typedef struct tr_n_t { key_t key;
struct tr_n_t *left;
struct tr_n_t *right;
int height;
} tree_node_t;
tree_node_t *currentblock = NULL;
int size_left;
tree_node_t *free_list = NULL;
tree_node_t *get_node()
{ tree_node_t *tmp;
if( free_list != NULL )
{ tmp = free_list;
free_list = free_list -> left;
}
else
{ if( currentblock == NULL || size_left == 0)
{ currentblock =
(tree_node_t *) malloc( BLOCKSIZE * sizeof(tree_node_t) );
size_left = BLOCKSIZE;
}
tmp = currentblock++;
size_left -= 1;
}
return( tmp );
}
void return_node(tree_node_t *node)
{ node->left = free_list;
free_list = node;
}
tree_node_t *create_tree(void)
{ tree_node_t *tmp_node;
tmp_node = get_node();
tmp_node->left = NULL;
return( tmp_node );
}
void left_rotation(tree_node_t *n)
{ tree_node_t *tmp_node;
key_t tmp_key;
tmp_node = n->left;
tmp_key = n->key;
n->left = n->right;
n->key = n->right->key;
n->right = n->left->right;
n->left->right = n->left->left;
n->left->left = tmp_node;
n->left->key = tmp_key;
}
void right_rotation(tree_node_t *n)
{ tree_node_t *tmp_node;
key_t tmp_key;
tmp_node = n->right;
tmp_key = n->key;
n->right = n->left;
n->key = n->left->key;
n->left = n->right->left;
n->right->left = n->right->right;
n->right->right = tmp_node;
n->right->key = tmp_key;
}
object_t *find(tree_node_t *tree, key_t query_key)
{ tree_node_t *tmp_node;
if( tree->left == NULL )
return(NULL);
else
{ tmp_node = tree;
while( tmp_node->right != NULL )
{ if( query_key < tmp_node->key )
tmp_node = tmp_node->left;
else
tmp_node = tmp_node->right;
}
if( tmp_node->key == query_key )
return( (object_t *) tmp_node->left );
else
return( NULL );
}
}
int insert(tree_node_t *tree, key_t new_key, object_t *new_object)
{ tree_node_t *tmp_node;
int finished;
if( tree->left == NULL )
{ tree->left = (tree_node_t *) new_object;
tree->key = new_key;
tree->height = 0;
tree->right = NULL;
}
else
{ tree_node_t * path_stack[100]; int path_st_p = 0;
tmp_node = tree;
while( tmp_node->right != NULL )
{ path_stack[path_st_p++] = tmp_node;
if( new_key < tmp_node->key )
tmp_node = tmp_node->left;
else
tmp_node = tmp_node->right;
}
/* found the candidate leaf. Test whether key distinct */
if( tmp_node->key == new_key )
return( -1 );
/* key is distinct, now perform the insert */
{ tree_node_t *old_leaf, *new_leaf;
old_leaf = get_node();
old_leaf->left = tmp_node->left;
old_leaf->key = tmp_node->key;
old_leaf->right = NULL;
old_leaf->height = 0;
new_leaf = get_node();
new_leaf->left = (tree_node_t *) new_object;
new_leaf->key = new_key;
new_leaf->right = NULL;
new_leaf->height = 0;
if( tmp_node->key < new_key )
{ tmp_node->left = old_leaf;
tmp_node->right = new_leaf;
tmp_node->key = new_key;
}
else
{ tmp_node->left = new_leaf;
tmp_node->right = old_leaf;
}
tmp_node->height = 1;
}
/* rebalance */
finished = 0;
while( path_st_p > 0 && !finished )
{ int tmp_height, old_height;
tmp_node = path_stack[--path_st_p];
old_height= tmp_node->height;
if( tmp_node->left->height -
tmp_node->right->height == 2 )
{ if( tmp_node->left->left->height -
tmp_node->right->height == 1 )
{ right_rotation( tmp_node );
tmp_node->right->height =
tmp_node->right->left->height + 1;
tmp_node->height = tmp_node->right->height + 1;
}
else
{ left_rotation( tmp_node->left );
right_rotation( tmp_node );
tmp_height = tmp_node->left->left->height;
tmp_node->left->height = tmp_height + 1;
tmp_node->right->height = tmp_height + 1;
tmp_node->height = tmp_height + 2;
}
}
else if ( tmp_node->left->height -
tmp_node->right->height == -2 )
{ if( tmp_node->right->right->height -
tmp_node->left->height == 1 )
{ left_rotation( tmp_node );
tmp_node->left->height =
tmp_node->left->right->height + 1;
tmp_node->height = tmp_node->left->height + 1;
}
else
{ right_rotation( tmp_node->right );
left_rotation( tmp_node );
tmp_height = tmp_node->right->right->height;
tmp_node->left->height = tmp_height + 1;
tmp_node->right->height = tmp_height + 1;
tmp_node->height = tmp_height + 2;
}
}
else /* update height even if there was no rotation */
{ if( tmp_node->left->height > tmp_node->right->height )
tmp_node->height = tmp_node->left->height + 1;
else
tmp_node->height = tmp_node->right->height + 1;
}
if( tmp_node->height == old_height )
finished = 1;
}
}
return( 0 );
}
object_t *delete(tree_node_t *tree, key_t delete_key)
{ tree_node_t *tmp_node, *upper_node, *other_node;
object_t *deleted_object; int finished;
if( tree->left == NULL )
return( NULL );
else if( tree->right == NULL )
{ if( tree->key == delete_key )
{ deleted_object = (object_t *) tree->left;
tree->left = NULL;
return( deleted_object );
}
else
return( NULL );
}
else
{ tree_node_t * path_stack[100]; int path_st_p = 0;
tmp_node = tree;
while( tmp_node->right != NULL )
{ path_stack[path_st_p++] = tmp_node;
upper_node = tmp_node;
if( delete_key < tmp_node->key )
{ tmp_node = upper_node->left;
other_node = upper_node->right;
}
else
{ tmp_node = upper_node->right;
other_node = upper_node->left;
}
}
if( tmp_node->key != delete_key )
deleted_object = NULL;
else
{ upper_node->key = other_node->key;
upper_node->left = other_node->left;
upper_node->right = other_node->right;
upper_node->height = other_node->height;
deleted_object = (object_t *) tmp_node->left;
return_node( tmp_node );
return_node( other_node );
}
/*start rebalance*/
finished = 0; path_st_p -= 1;
while( path_st_p > 0 && !finished )
{ int tmp_height, old_height;
tmp_node = path_stack[--path_st_p];
old_height= tmp_node->height;
if( tmp_node->left->height -
tmp_node->right->height == 2 )
{ if( tmp_node->left->left->height -
tmp_node->right->height == 1 )
{ right_rotation( tmp_node );
tmp_node->right->height =
tmp_node->right->left->height + 1;
tmp_node->height = tmp_node->right->height + 1;
}
else
{ left_rotation( tmp_node->left );
right_rotation( tmp_node );
tmp_height = tmp_node->left->left->height;
tmp_node->left->height = tmp_height + 1;
tmp_node->right->height = tmp_height + 1;
tmp_node->height = tmp_height + 2;
}
}
else if ( tmp_node->left->height -
tmp_node->right->height == -2 )
{ if( tmp_node->right->right->height -
tmp_node->left->height == 1 )
{ left_rotation( tmp_node );
tmp_node->left->height =
tmp_node->left->right->height + 1;
tmp_node->height = tmp_node->left->height + 1;
}
else
{ right_rotation( tmp_node->right );
left_rotation( tmp_node );
tmp_height = tmp_node->right->right->height;
tmp_node->left->height = tmp_height + 1;
tmp_node->right->height = tmp_height + 1;
tmp_node->height = tmp_height + 2;
}
}
else /* update height even if there was no rotation */
{ if( tmp_node->left->height > tmp_node->right->height )
tmp_node->height = tmp_node->left->height + 1;
else
tmp_node->height = tmp_node->right->height + 1;
}
if( tmp_node->height == old_height )
finished = 1;
}
/*end rebalance*/
return( deleted_object );
}
}
void check_tree( tree_node_t *tr, int depth, int lower, int upper )
{ if( tr->left == NULL )
{ printf("Tree Empty\n"); return; }
if( tr->key < lower || tr->key >= upper )
printf("Wrong Key Order \n");
if( tr->right == NULL )
{ if( *( (int *) tr->left) == 10*tr->key + 2 )
printf("%d(%d) ", tr->key, depth );
else
printf("Wrong Object \n");
}
else
{ check_tree(tr->left, depth+1, lower, tr->key );
check_tree(tr->right, depth+1, tr->key, upper );
}
}
int main()
{ tree_node_t *searchtree;
char nextop;
searchtree = create_tree();
printf("Made Tree: Height-Balanced Tree\n");
while( (nextop = getchar())!= 'q' )
{ if( nextop == 'i' )
{ int inskey, *insobj, success;
insobj = (int *) malloc(sizeof(int));
scanf(" %d", &inskey);
*insobj = 10*inskey+2;
success = insert( searchtree, inskey, insobj );
if ( success == 0 )
printf(" insert successful, key = %d, object value = %d, \
height is %d\n",
inskey, *insobj, searchtree->height );
else
printf(" insert failed, success = %d\n", success);
}
if( nextop == 'f' )
{ int findkey, *findobj;
scanf(" %d", &findkey);
findobj = find( searchtree, findkey);
if( findobj == NULL )
printf(" find failed, for key %d\n", findkey);
else
printf(" find successful, found object %d\n", *findobj);
}
if( nextop == 'd' )
{ int delkey, *delobj;
scanf(" %d", &delkey);
delobj = delete( searchtree, delkey);
if( delobj == NULL )
printf(" delete failed for key %d\n", delkey);
else
printf(" delete successful, deleted object %d, height is now %d\n",
*delobj, searchtree->height);
}
if( nextop == '?' )
{ printf(" Checking tree\n");
check_tree(searchtree,0,-1000,1000);
printf("\n");
if( searchtree->left != NULL )
printf("key in root is %d, height of tree is %d\n",
searchtree->key, searchtree->height );
printf(" Finished Checking tree\n");
}
}
return(0);
}
Что означает "использование обратных указателей" и "стеки больше не используются"? Должен ли я изменить /* start rebalancing */ часть, а также функции rotation а также insert? Я немного понимаю, как работает сбалансированное по высоте дерево, но я не совсем понимаю, что мне нужно делать для этого задания.
1 ответ
В вашей исходной древовидной структуре каждый узел имеет указатели на своих левых и правых дочерних элементов (если они есть), но не на его родительский узел. Если вам нужно выполнить операцию с таким деревом, которая требует знания некоторого или всего пути от корня дерева до какого-либо интересующего узла, тогда вам нужно построить этот путь, пройдя по дереву и записав путь по мере go - например, в структуре данных стека. Вы не можете работать в обратном направлении от конечного узла.
Вы можете увидеть именно такое поведение в коде, который вы разместили. Например, в функции insert() у тебя есть...
tree_node_t * path_stack[100]; int path_st_p = 0;
... и позже...
path_stack[path_st_p++] = tmp_node;
... и так далее.
Если, с другой стороны, каждый узел также имеет указатель на свой родительский узел, вам не нужно отслеживать пути через дерево. Вместо этого вы можете начать с любого узла и идти назад вверх по дереву, насколько это необходимо, потому что информация, необходимая для этого, будет переноситься самими узлами. Задание просит вас изменить реализацию дерева, чтобы использовать этот подход вместо стекового подхода, который он использует сейчас.
Наличие "назад" или родительских указателей удобно в некоторых отношениях, но неудобно в других. Они дают более простые выражения для ряда вещей и требуют меньше бухгалтерии при обходе дерева. Они также могут позволить вам более эффективно обмениваться кодом между функциями дерева. С другой стороны, они являются дополнительным элементом, которым нужно управлять всякий раз, когда и где бы вы ни модифицировали дерево, и они вводят избыточность в плохом смысле, что они дают возможность для несогласованности.
Ваше назначение начинается с добавления обратного указателя на struct tr_n_t, Затем вы должны корректно инициализировать его всякий раз, когда добавляете узел в дерево, и обновлять его всякий раз, когда вы переопределяете узел как прямой результат удаления или в процессе ребалансировки. Кроме того, вы удалите код в обоих insert() а также delete() он отслеживает путь через дерево к точке / узлу вставки для удаления и изменяет код перебалансировки в обеих функциях так, чтобы он использовал новые обратные указатели для перехода назад по дереву вместо использования стеков, как сейчас.