AVL樹，C，旋轉實現

Question

代碼在這裏： http://pastebin.com/VAdc67bE

有一個在功能rotacao_esquerda問題。 這是一個AVL樹的旋轉。

如何解決？

Answer 1

有多種方式來解決這個問題：

• 的printf調試語句插入大量豐富整個代碼並運行它，檢查輸出。
• 在調試器中運行您的代碼，單步執行並在每個步驟後檢查變量。
• 請問這裏有一個開放式，模糊的問題，並試着讓我們做全部爲你工作。

只有兩種這些選項會讓你成爲更好的開發並不太可能會激怒我們在未來:-)

你應該先嚐試做的是縮小問題了。所有的問題報告（在SO和現實世界中）應該包含：

• 你在做什麼（非常詳細），導致問題。
• 你預計會發生什麼。
• 什麼實際上發生。

更少的是用戶沒有保持他們討價還價的結束。

---

AVL *rotacao_direita(AVL *no) { 
    AVL *temp; 
    temp = no->esq; 
    no->esq = temp->dir; 
    if (temp->dir != NULL) 
     temp->dir->pai = no; 
    temp->dir = no; 
    temp->pai = no->pai; 
    no->pai->dir = temp; 
    no->pai = temp; 
    no->fb = 0; 
    return temp; 
} 

好吧，這是你的功能，它似乎要向右旋轉通過的no（以下A）節點。並根據您的意見：pai =父親，dir =右和esq =左。

X 
    \ 
    A 
/\ 
B C 
/\/\ 

所以你最終的東西，如：

X 
    \ 
    B 
/\ 
    A 
    /\ 
     C 

我看到一個即時可能出現的問題。您正試圖更改該節點的父指針，以使其指向旋轉的節點B。

但是你正在改變no->pai->dir這是正確的節點X。如果樹的結構如下，會發生什麼？

 X 
    /\ 
    A Y 
/\ 
B C 
/\/\ 

如果試圖通過樹代碼的A節點旋轉，你會嚴重危及Y子樹。

從走馬臺檢查，我想你可以通過改變開始：

no->pai->dir = temp; 

到：

if (no->pai->esq == no) 
    no->pai->esq = temp; 
else 
    no->pai->dir = temp; 

應該更改父正確的指針。請記住，我沒有檢查大量可能的樹，僅這一項：

 _____X_____ 
    /   \ 
    __A__   Y 
/ \ 
    B  C 
/\ /\ 
D E F G 

與DBEAFCGXY的中序遍歷，如果您的權利，通過A的代碼改變我給它旋轉，你得到：

 _____X_____ 
    /   \ 
    __B__   Y 
/ \ 
    D  A 
     /\ 
     E C 
     /\ 
      F G 

它看起來正確（順序DBEAFGCXY，與以前一樣）。

因此，底線，試試這個：

AVL *rotacao_direita(AVL *no) { 
    AVL *temp; 
    temp = no->esq; 
    no->esq = temp->dir; 
    if (temp->dir != NULL) 
     temp->dir->pai = no; 
    temp->dir = no; 
    temp->pai = no->pai; 
    if (no->pai->esq == no) 
     no->pai->esq = temp; 
    else 
     no->pai->dir = temp; 
    no->pai = temp; 
    no->fb = 0; 
    return temp; 
} 

，看看它是如何去。

---

Diogo，我會給你留下一些代碼來說明我的意思。查看下面的代碼。它基本上創建了一個虛擬結構並將其轉儲出來，然後在其上運行您的旋轉例程。您可以從輸出中看到生成的樹是錯誤的。

它然後重新創建原始樹並運行固定的旋轉功能，產生我認爲是正確的結果。

如果您還有其他問題，請隨時在調試工作中使用dumpAvl函數。它輸出一個格式相對較好的樹，其中一個節點後跟縮進的子節點（左側爲<，右側爲>）。

#include <stdio.h> 
#include <string.h> 

typedef struct AVL { 
    struct AVL *pai, *esq, *dir; 
    char chr; int fb; 
} AVL; 

 

AVL *rotacao_direita(AVL *no) { 
    AVL *temp; 
    temp = no->esq; 
    no->esq = temp->dir; 
    if (temp->dir != NULL) 
     temp->dir->pai = no; 
    temp->dir = no; 
    temp->pai = no->pai; 
    no->pai->dir = temp; 
    no->pai = temp; 
    no->fb = 0; 
    return temp; 
} 

 

AVL *rotacao_direita_fixed(AVL *no) { 
    AVL *temp; 
    temp = no->esq; 
    no->esq = temp->dir; 
    if (temp->dir != NULL) 
     temp->dir->pai = no; 
    temp->dir = no; 
    temp->pai = no->pai; 
    if (no->pai->esq == no) 
     no->pai->esq = temp; 
    else 
     no->pai->dir = temp; 
    no->pai = temp; 
    no->fb = 0; 
    return temp; 
} 

 

static AVL *newNode (AVL *pai, char which, AVL *esq, AVL *dir, char chr) { 
    AVL *node = malloc (sizeof (AVL)); 
    node->pai = pai; 
    node->esq = esq; 
    node->dir = dir; 
    node->chr = chr; 
    if (pai != NULL) { 
     if (which == '<') { 
      node->pai->esq = node; 
     } else { 
      node->pai->dir = node; 
     } 
    } 
    return node; 
} 

 

static void dumpAvl (char *desc, AVL *node, int spc, char which) { 
    int i; 
    if (desc != NULL) { 
     printf ("%s:\n", desc); 
     for (i = 0; i < strlen (desc); i++) 
      printf ("-"); 
     printf ("-\n"); 
    } 
    for (i = 0; i < spc; i++) printf (" "); 
    if (node == NULL) { 
     printf ("%c#\n", which); 
    } else { 
     printf ("%c%c\n", which, node->chr); 
     if ((node->esq != NULL) || (node->dir != NULL)) { 
      dumpAvl (NULL, node->esq, spc+2, '<'); 
      dumpAvl (NULL, node->dir, spc+2, '>'); 
     } 
    } 
    if (spc == 0) 
     printf ("==================================================\n"); 
} 

 

static AVL *setupTree (void) { 
    AVL *root = newNode (NULL, '-', NULL, NULL, 'X'); 

    AVL *node = newNode (root, '<', NULL, NULL, 'A'); 
    node = newNode (root, '>', NULL, NULL, 'Y'); 

    node = newNode (root->esq, '<', NULL, NULL, 'B'); 
    node = newNode (root->esq, '>', NULL, NULL, 'C'); 

    node = newNode (root->esq->esq, '<', NULL, NULL, 'D'); 
    node = newNode (root->esq->esq, '>', NULL, NULL, 'E'); 

    node = newNode (root->esq->dir, '<', NULL, NULL, 'F'); 
    node = newNode (root->esq->dir, '>', NULL, NULL, 'G'); 

    return root; 
} 

 

int main (void) { 
    AVL *root, *junk; 

    root = setupTree(); 
    dumpAvl ("Original code", root, 0, '-'); 
    junk = rotacao_direita (root->esq); 
    dumpAvl (NULL, root, 0, '-'); 

    root = setupTree(); 
    dumpAvl ("Fixed code", root, 0, '-'); 
    junk = rotacao_direita_fixed (root->esq); 
    dumpAvl (NULL, root, 0, '-'); 

    return 0; 
} 

當你運行它，它產生以下。您可以看到原始代碼具有某些子樹的多個副本，這是因爲代碼假定roration點始終位於其父代的右側。固定的代碼沒有做出這樣的假設。

Original code: 
-------------- 
-X 
    <A 
    <B 
     <D 
     >E 
    >C 
     <F 
     >G 
    >Y 
================================================== 
-X 
    <A 
    <E 
    >C 
     <F 
     >G 
    >B 
    <D 
    >A 
     <E 
     >C 
     <F 
     >G 
================================================== 

 

Fixed code: 
----------- 
-X 
    <A 
    <B 
     <D 
     >E 
    >C 
     <F 
     >G 
    >Y 
================================================== 
-X 
    <B 
    <D 
    >A 
     <E 
     >C 
     <F 
     >G 
    >Y 
==================================================