Как это бинарное дерево поиска выглядят?


Я написал БСТ в C и может использовать его в какой-то момент.

 search_tree tree_make_empty( search_tree tree )
 {
   if ( tree != NULL )
   {
       tree_make_empty( tree->left );
       tree_make_empty( tree->right );
       free( tree );
   }
   return NULL;
 }

 tree_position tree_find( CHAR_DATA *target, search_tree tree )
 {
     if ( tree == NULL )
       return NULL;

     if ( target < tree->hatedata->target_char )
       return tree_find( target, tree->left );
     else if ( target > tree->hatedata->target_char )
       return tree_find( target, tree->right );
     else
       return tree;
 }

 search_tree tree_insert( HATE_DATA *hatedata, search_tree tree )
 {
     if ( tree == NULL )
     {
       tree = (HATE_NODE * ) malloc( sizeof( HATE_NODE ) );

       if ( tree == NULL )
          bug( "tree_insert: out of space!" );
       else
       {
          tree->hatedata = hatedata;
          tree->left = tree->right = NULL;
       }
     }
     else if ( hatedata->target_char < tree->hatedata->target_char )
       tree->left = tree_insert( hatedata, tree->left );
     else if ( hatedata->target_char > tree->hatedata->target_char )
          tree->right = tree_insert( hatedata, tree->right );

     return tree;
 }

 tree_position tree_find_min( search_tree tree )
 {
    if ( tree == NULL )
       return NULL;
    else if ( tree->left == NULL )
       return tree;
    else
       return tree_find_min( tree->left );
 }

 search_tree tree_delete( HATE_DATA *hatedata, search_tree tree )
 {
    tree_position pos;

    if ( tree == NULL )
       bug( "tree_delete: not found" );
    else if ( hatedata->target_char < tree->hatedata->target_char )
       tree->left = tree_delete( hatedata, tree->left );
    else if ( hatedata->target_char > tree->hatedata->target_char )
         tree->right = tree_delete( hatedata, tree->right );
    else if ( tree->left && tree->right )
    {
       pos = tree_find_min( tree->right );
       tree->hatedata = pos->hatedata;
       tree->right = tree_delete( tree->hatedata, tree->right );
    }
    else
    {
       pos = tree;
       if ( tree->left == NULL )
         tree = tree->right;
       else if ( tree->right == NULL )
         tree = tree->left;
       free( pos );
    }

    return tree;
 }

 HATE_DATA *tree_retrieve( tree_position pos )
 {
    return pos->hatedata;
 }

...

 struct hate_data
 {
    CHAR_DATA *target_char;
    int hate_amount;
 };

 struct hate_node
 {
    HATE_DATA *hatedata;
    search_tree left;
    search_tree right;
 };

...

mob->hatedata = tree_make_empty( NULL );

Пример использования:

if ( IS_NPC(victim) )
{
     HATE_DATA *hatedata;
   tree_position P;

   if( ( P = tree_find( ch, victim->hatedata )) == NULL || tree_retrieve( P )->target_char != ch )
   {
     int test;
     hatedata = (HATE_DATA * ) malloc( sizeof( HATE_DATA ) );
     hatedata->target_char = ch;
     test = number_range( 1, 50 );
     hatedata->hate_amount = test;
     victim->hatedata = tree_insert( hatedata, victim->hatedata );
     ch_printf( ch, "It should now hate you for %d.\n\r", test );
   }
   else
   {
     hatedata = tree_retrieve(tree_find( ch, victim->hatedata ));
     ch_printf(ch, "You are already hated for %d!\n\r", hatedata->hate_amount );
   }

}

У вас есть какие-либо предложения? Выглядит нормально? Есть ли способы оптимизировать это?



735
3
задан 27 января 2011 в 06:01 Источник Поделиться
Комментарии
3 ответа

В tree_find и tree_find_min [правка: и даже в tree_insert] ты не набирает ничего с помощью рекурсии. Например, я думаю, tree_find_min , вероятно, будет яснее, что-то вроде:

tree_position tree_find_min( search_tree tree )
{
if ( tree == NULL )
return NULL;
while (tree->left != NULL)
tree = tree->left;
return tree;
}

Как дополнительное преимущество, это может быть быстрее с некоторыми компиляторами. В код, как:

 HATE_DATA *hatedata;

/* ... */

hatedata = (HATE_DATA * ) malloc( sizeof( HATE_DATA ) );

Я бы изменить его, чтобы выглядеть как:

 hatedata = malloc(sizeof(*hatedata));

Бросок выполняет ничего полезного в C, и могут прикрыть баг забывая включать чтобы получить правильный прототип для функции malloc. Используя оператор sizeof(*hatedata) , а не оператор sizeof(HATE_DATA) означает, что изменение типа требуется только изменить его в одном месте (где вы определили переменную), а не везде вы сделали выделение.

5
ответ дан 27 января 2011 в 07:01 Источник Поделиться

Используя сравнение, чем операторы < и > на указатели, кажется, немного излишним.

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

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

2
ответ дан 27 января 2011 в 07:01 Источник Поделиться

Еще лучший способ, чтобы сделать malloc-это с этот макрос (упрощенная версия g_new в GLib):

#define my_new(type, count)  ((type*)malloc (sizeof (type) * (count)))

Преимуществами этого являются:


  • меньше набирать, больше ясности

  • присвоение неправильного типа будет предупреждение компилятора

  • вы можете не случайно оператор sizeof() неправильно

Кроме того, конечно, что malloc может вернуть null. Самый простой способ справиться с этим-сделать функцию-оболочку, которая обрабатывает его.

2
ответ дан 27 января 2011 в 09:01 Источник Поделиться