AVL树，c，旋转实现

Question

代码在这里： http://pastebin.com/VAdc67bE

函数 rotacao_esquerda 存在问题。 这是 AVL 树的旋转。

如何修复它？

Answer 1

有多种方法可以解决此问题：

• 在整个代码中插入大量 printf 调试语句并运行它，检查输出。
• 在调试器中运行代码，单步执行并在每个步骤后检查变量。
• 在这里提出一个关于 SO 的开放式、模糊的问题，并尝试让我们为您完成所有工作。

这些选项中只有两个会让您成为更好的开发人员，并且将来不太可能惹恼我们:-)

您首先应该尝试做的是缩小问题范围。所有问题报告（此处关于 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;
}

当您运行它时，它会生成以下内容。您可以看到原始代码具有某些子树的多个副本，因为代码假设旋转点始终位于其父树的右侧。固定代码没有做出这样的假设。

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