avl-tree - AVL ツリー、c、ローテーションの実装

Question

コードはこちら: http://pastebin.com/VAdc67bE

関数 rotacao_esquerda に問題があります。これは AVL ツリーのローテーションです。

修正方法は？

score 2 · Accepted Answer

この問題を解決するには、いくつかの方法があります。

コード全体に大量のprintfデバッグステートメントを挿入して実行し、出力を調べます。
デバッガー内でコードを実行し、シングルステップで各ステップの後に変数を調べます。
ここ SO で自由回答形式の漠然とした質問をして、私たちにすべての作業を任せるようにしてください。

これらのオプションのうち 2 つだけを使用すると、より優れた開発者になり、将来的に私たちを悩ませる可能性が低くなります :-)

最初にすべきことは、問題を絞り込むことです。すべての問題レポート (ここでは 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;
}

さて、それはあなたの機能であり、（下の）ノードを右に回転させたいようです。そして、あなたのコメントによると、=父、=右、=左。noApaidiresq

 X
  \
   A
  / \
 B   C
/ \ / \

したがって、次のような結果になります。

 X
  \
   B
  / \
     A
    / \
       C

すぐに考えられる問題が 1 つあります。そのノードの親ポインターを変更して、回転したノードを指すようにしようとしています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

これはほぼ正しいように見えます（ inorder 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;
}

そしてそれがどうなるか見てください。

ディオゴ、私が何を言おうとしているのかを説明するために、コードをいくつか残しておきます。次のコードを見てください。基本的に、ダミー構造を作成してダンプし、回転ルーチンを実行します。出力から、結果のツリーが間違っていることがわかります。

次に、元のツリーを再作成し、固定された回転関数を実行して、正しいと思われる結果を生成します。

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