5

rebalance()AVL の機能の実装に関する記事をいくつか見ました。
各挿入の後、挿入ノードの先祖のバランスをチェックする必要があります。
ということで、先祖のバランスを確認するために、挿入ノードの親を知りました。

しかし、親ポインターを使用せずにそれを行う方法は他にあるのでしょうか?
たとえば、ノード構造体:

struct Node {
    int data;
    struct Node *lchild, *rchild; //*parent;
};
4

5 に答える 5

4

ツリーをたどっている間、現在のノードへのスタックを維持できます

stack<Node*> nodeStack;

新しいノードにたどり着いたら、それをスタックに追加すると、祖先が得られます。ノードの処理が終了したら、スタックからポップします。

** 編集 **

配置コメントの詳細:

struct Node {
    int data;
    struct Node *children, *parent
};

子を作成するときは、次のようにします。

node.children = new Node[2]; or node.children = malloc(sizeof(Node) * 2);
node.children[0].parent = node;
node.children[1].parent = node;
于 2011-08-27T00:49:54.047 に答える
3

二重ポインター (または C++ で要求したポインターへの参照) を使用すると、親ポインターの必要性が完全になくなります。

typedef struct Node {
    int value;
    int height;
    struct Node *left;
    struct Node *right;
} Node;

int height(Node *node) {
    return (node == NULL) ? -1 : node->height;
}

void insert(Node * & node, int value) {
    if (node == NULL) {
        node = new Node();
        node->value = value;
    } else if (value < node->value) {
        insert(node->left, value);
        if (height(node->left) - height(node->right) == 2) {
            if (value < note->left->value) {
                singleRotateWithLeftChild(node);
            } else {
                doubleRotateWithLeftChild(node);
            }
        }
    } else if (value > node->value) {
        // Symmetric case
    }

    node->height = 1 + max(height(node->left), height(node->right));
}
于 2011-08-27T01:05:24.083 に答える
3

データ構造の宿題を正しく覚えていれば:

あなたがすることは、次のいずれかの int としてノード自体にバランス係数を格納することです。

  • -1 : ノードの左のサブツリーは、右のサブツリーよりも 1 つ上のレベルです (左が重い)。
  • 0ノードはバランスが取れています。また
  • 1右側のサブツリーが高い (右側が重い)。

insert(Node subtree) 関数はブール値を返します。これは、挿入によってサブツリーの高さが増加した場合に true になります。再帰的な insert() 呼び出しから戻ったときに、バランス ファクターを更新し、ツリーのバランスを取り直します。

これはおそらく、いくつかの例で最もよく説明されています。

現在のノードのバランス係数が-1で、右側のサブツリーに挿入していて、insert(rchild) がtrueを返す場合:

  1. 現在のノードのバランス係数を 0 に更新します。左のサブツリーは挿入前により高く、右のサブツリーの高さが増加したため、現在は同じ高さです。と
  2. false を返す- より浅いツリーの高さが増加したため、現在のノードの高さは同じままです

いずれかのサブツリーに挿入する場合、insert(…) はfalseを返します:

  1. 現在のノードのバランス係数は変更されません。サブツリーの高さは以前と同じで、バランスも同じです。
  2. falseを返す- サブツリーの高さは変更されていないため、現在のノードの高さも変更されていません

現在のノードのバランス係数が0の場合、左側のサブツリーに挿入しているため、insert(lchild) はtrueを返します。

  1. バランス係数が -1 に変わります - サブツリーは挿入前は同じ高さでしたが、挿入により左のサブツリーが高くなりました
  2. 真を返す

(同様に、右側のサブツリーに挿入すると、バランス係数は 1 に変わります。)

現在のノードのバランス ファクターが-1の場合、左側のサブツリーに挿入し、insert(lchild) はtrueを返します。

バランス係数は -2 に変わります。これは、適切な回転を行ってノードのバランスを取り直す必要があることを意味します。4 つのローテーションのそれぞれがバランス ファクターに対して何を行うか、および insert(current) が何を返すかについて、空白を描いていることを認めます。うまくいけば、前の例で、ノードのバランスを十分に追跡するためのアプローチを説明できます。

于 2011-08-27T01:22:35.207 に答える
0

私がコーディングした方法は、削除する要素をツリーで検索しているときに、トラバースする子リンク (左または右) をトラバースしたノードのスタック内のリンクに一時的に変更することです (事実上、一時的な親ポインター)。 . 次に、このスタックから各ノードをポップし、子ポインターを復元して、バランスを取り直します。

C++ エンコーディングについては、 https://github.com/wkaras/C-plus-plus-intrusive-container-templates/blob/master/avl_tree.hの remove member 関数 (現在は 882 行目) を参照してください。

C エンコーディングについては、 http://wkaras.webs.com/gen_c/cavl_impl_h.txt のマクロ呼び出し L__(remove) によって名前が生成される関数を参照してください。

親ポインタを持つことは、挿入には何の役にも立たないと思います。

一意のキーではなく、ノード ポインターによって識別されるノードを削除する場合は、おそらく親ポインターを使用した方が高速になると思います。

于 2016-10-24T13:46:58.523 に答える