C: Создание сбалансированного дерева AVL

Question

Я пытаюсь написать код для создания сбалансированного двоичного дерева AVL. Целью является то, что поддерево должно вращаться, чтобы поддерживать баланс (AVL) каждый раз, когда вставлен новый узел.

(Все значения в левом поддереве узла должно быть меньше, чем это значение узла; Все значения в правом поддереве узла должен быть выше, чем это значение узла)

Код я просто написал работу для чисел, вставленных в определенном порядке, но не в других. Например, следующие входы работают отлично:

10 7 14 12 15 3 0 

16 8 20 14 23 0 

Это один не будет:

10 7 3 15 12 14 0 

10 7 5 14 13 0 

Почему?

#include <stdio.h> 
#include <stdlib.h> 

typedef enum {false, true} Boolean; 
typedef enum {minus = -1, zero, plus} balance; 

typedef struct nohh { 
    int info; 
    balance bal; 
    struct nohh *left; 
    struct nohh *right; 
} nohh, *noh; 

void PrintTree(noh p); 
Boolean Insert(noh *p, int x, Boolean *alt); 
void RotateLL(noh p, noh p1); 
void RotateLR(noh p, noh p1); 
void RotateRR(noh p, noh p1); 
void RotateRL(noh p, noh p1); 

int main(){ 
    noh p = NULL; 
    int x; 
    Boolean check = false, *bol = &check; 

    printf("int number ('0' to exit): "); 
    scanf("%d", &x); 

    do{ 
     check = Insert(&p, x, bol); 
     printf("check = %d\n", check); 

     printf("int number: "); 
     scanf("%d", &x); 
    }while(x != 0); 

    PrintTree(p); 

    return 0; 
} 

void PrintTree(noh p){ 
    printf("%d >> bal = %d\n", p->info, p->bal); 
    if(p->left != NULL) 
     PrintTree(p->left); 
    if(p->right != NULL) 
     PrintTree(p->right); 
} 

Boolean Insert(noh *p, int x, Boolean *alt){ 
    int info; 

    if((*p)==NULL){ 
     *p = malloc(sizeof(nohh)); 
     (*p)->left = (*p)->right = NULL; 
     (*p)->info = x; 
     (*p)->bal = zero; 
     *alt = true; 
     return true; 
    } else { /* if p isnt pointing to NULL */ 
     info = (*p)->info; 
     if(x == info) 
      return false; 
     else if(x < info){ /* follow left */ 
      Boolean res = Insert(&(*p)->left, x, alt); 
      if(!res) 
       return false; 
      if(*alt){ /* height increase */ 
       noh p1; 
       switch((*p)->bal){ 
       case plus: 
        (*p)->bal = zero; *alt = false; 
        break; 
       case zero: 
        (*p)->bal = minus; 
        break; 
       case minus: /* -1 -1 = -2 => not balanced!! */ 
        p1 = (*p)->left; 
        if(p1->bal == minus){ 
         /* Rotation LL */ 
         RotateLL(*p, p1); 
         *alt = true; 
        } else if(p1->bal == plus){ 
         /* Rotation LR */ 
         RotateLR(*p, p1); 
         *alt = true; 
        } else { 
         /* Rotation LL */ 
         RotateLL(*p, p1); 
         *alt = false; 
        } 
        p1->bal = zero; *alt = false; 
        break; 
       } 
      } 
      return true; 
     } else { /* follow right */ 
      Boolean res = Insert(&(*p)->right, x, alt); 
      if(!res) 
       return false; 
      if(*alt){ /* height increase */ 
       noh p1; 
       switch((*p)->bal){ 
       case minus: 
        (*p)->bal = zero; *alt = false; 
        break; 
       case zero: 
        (*p)->bal = plus; 
        break; 
       case plus: /* 1 +1 = 2 => Not balanced! */ 
        p1 = (*p)->right; 
        if(p1->bal == plus){ 
         /* Rotation RR */ 
         RotateRR(*p, p1); 
         *alt = true; 
        } else if(p1->bal == minus){ 
         /* Rotation RL */ 
         RotateRL(*p, p1); 
         *alt = true; 
        } else { 
         /* Rotation RR */ 
         RotateRR(*p, p1); 
         *alt = false; 
        } 
        p1->bal = zero; *alt = false; 
        break; 
       } 
      } 
      return true; 
     } 
    } 
} 

void RotateLL(noh p, noh p1){ 
    noh p2, aux; 

    p2 = p1->left; 

    aux = p; 
    p = p1; 
    p->right = aux; 

    aux->left = aux->right = NULL; 
    aux->bal = p2->bal = p->bal = zero; 
} 

void RotateLR(noh p, noh p1){ 
    noh p2, aux; 
    aux = p; 
    p2 = p1->right; 

    p = p2; 
    p2->left = p1; 
    p2->right = aux; 

    aux->left = aux->right = NULL; 
    p1->left = p1->right = NULL; 
    aux->bal = p1->bal = p->bal = zero; 
} 

void RotateRR(noh p, noh p1){ 
    noh p2, aux; 

    p2 = p1->right; 

    aux = p; 
    p = p1; 
    p->left = aux; 

    aux->left = aux->right = NULL; 
    aux->bal = p2->bal = p->bal = zero; 
} 

void RotateRL(noh p, noh p1){ 
    noh p2, aux; 
    aux = p; 
    p2 = p1->left; 

    p = p2; 
    p2->right = p1; 
    p2->left = aux; 

    aux->left = aux->right = NULL; 
    p1->left = p1->right = NULL; 

    aux->bal = p1->bal = p->bal = zero; 
} 

Answer 1

Ваши реализации RotateLL/LR/RL/RR несовершенны - они приспосабливаются указатели правильно между узлами, участвующими в ротации, но они не меняют указатель на старый корневой узел. Это приводит к утере узлов при поворотах.

Вы увидите, что происходит, если вы вставляете вызов в PrintTree() внутри цикла в main(). Например:

int number ('0' to exit): 1 
check = 1 
1 >> bal = 0 
int number: 2 
check = 1 
1 >> bal = 1 
2 >> bal = 0 
int number: 3 
check = 1 
1 >> bal = 0 

Это, вероятно, будет проще всего иметь каждая из функций Поворот возвращает указатель на новый корневой узел и обновления указателей соответственно в Insert(). Помните, что есть ситуации, когда Insert() необходимо будет обновить *p, чтобы отразить тот факт, что корневой узел переместился!