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 
==================================================