avl-tree - AVL树，c，旋转实现

Question

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

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

如何解决？

score 2 · Accepted Answer

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

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

avl-tree - AVL树，c，旋转实现

1 回答 1

Related

Reference