0

したがって、パラメータ化されたリストを使用してバイナリ検索ツリーを実装しました。

List<Node> tree = new List<>();

ツリーは正常に動作します。ノード自体は、その親または子について何も知りません。これは、インデックスに基づいて場所を計算するためです。

                         If i is the index of some None N then:
                                N's left child is in tree[i*2] 
                                N's right child is in tree[(i*2)+1]

このバイナリ ツリーは正常に動作します。しかし、今は AVL ツリー機能を追加したいと考えています。リストでローテーションを行う方法がわからないため、この時点で立ち往生しています。回転時に、新しいルートの子を移動するにはどうすればよいですか? 実際、彼らはインデックスをシフトしなければなりませんね。また、リストでこれを行うと、ノードを追加するたびにツリーを表示するにはリストをループする必要があるという問題が発生します。これは O(logn) では発生せず、AVL ツリーのポイント全体が破壊されます。

私はC＃でこれをやっています。リストまたはリンクリストではなくインデックス可能な配列ベースのデータ構造を使用して、このAVLツリーを効率的に作成する方法を知りたいだけです。これは重要です。説明するコードがあれば大歓迎です。

4

3 に答える 3

3

あなたがやっている方法で配列/リストでツリーを表現することは、ヒープデータ構造では一般的ですが、事実上他の種類のツリーでは機能しません。特に、AVL ツリーではこれを (効率的に) 行うことはできません。

于 2013-05-07T11:15:51.770 に答える
0

malloc を使用できない組み込みアプリケーションでこれが必要でした。それができるかどうかを試みる前に、いかなる種類のデータ構造アルゴリズムの実装も行っていませんでした。コードを書いているうちに、多くのものを動かさなければならないことに気付きました。救済策を検索し、この投稿にたどり着きました。

Chris の返信のおかげで、これ以上時間を費やすつもりはありません。必要なものを実装する別の方法を見つけます。

于 2013-05-30T16:54:23.603 に答える
0

答えが見つかったと思います。トリックは、サブツリーをリストの上下に移動して、ローテーション中に有効なノードを上書きしないようにすることです。

void shiftUp(int indx, int towards) {
    if (indx >= size || nodes[indx].key == NULL) {
        return;
    }
    nodes[towards] = nodes[indx];
    nodes[indx].key = NULL;
    shiftUp(lChild(indx), lChild(towards));
    shiftUp(rChild(indx), rChild(towards));
}

void shiftDown(int indx, int towards) {
    if (indx >= size || nodes[indx].key == NULL) {
        return;
    }

    // increase size so we can finish shifting down
    while (towards >= size) { // while in the case we don't make it big enough
        enlarge();
    }

    shiftDown(lChild(indx), lChild(towards));
    shiftDown(rChild(indx), rChild(towards));
    nodes[towards] = nodes[indx];
    nodes[indx].key = NULL;
}

ご覧のとおり、これは NULL (これで -1 として定義されている) ノードまで各サブツリーを再帰的に探索し、各要素を 1 つずつ上下にコピーすることによって行われます。

これにより、このウィキペディア Tree_Rebalancing.gifに従って名前が付けられた 4 種類の回転を定義できます。

void rotateRight(int rootIndx) {
    int pivotIndx = lChild(rootIndx);

    // shift the roots right subtree down to the right
    shiftDown(rChild(rootIndx), rChild(rChild(rootIndx)));
    nodes[rChild(rootIndx)] = nodes[rootIndx]; // move root too

    // move the pivots right child to the roots right child's left child
    shiftDown(rChild(pivotIndx), lChild(rChild(rootIndx)));

    // move the pivot up to the root
    shiftUp(pivotIndx, rootIndx);

    // adjust balances of nodes in their new positions
    nodes[rootIndx].balance--; // old pivot
    nodes[rChild(rootIndx)].balance = (short)(-nodes[rootIndx].balance); // old root
}

void rotateLeft(int rootIndx) {
    int pivotIndx = rChild(rootIndx);

    // Shift the roots left subtree down to the left
    shiftDown(lChild(rootIndx), lChild(lChild(rootIndx)));
    nodes[lChild(rootIndx)] = nodes[rootIndx]; // move root too

    // move the pivots left child to the roots left child's right child
    shiftDown(lChild(pivotIndx), rChild(lChild(rootIndx)));

    // move the pivot up to the root
    shiftUp(pivotIndx, rootIndx);

    // adjust balances of nodes in their new positions
    nodes[rootIndx].balance++; // old pivot
    nodes[lChild(rootIndx)].balance = (short)(-nodes[rootIndx].balance); // old root
}


// Where rootIndx is the highest point in the rotating tree
// not the root of the first Left rotation
void rotateLeftRight(int rootIndx) {
    int newRootIndx = rChild(lChild(rootIndx));

    // shift the root's right subtree down to the right
    shiftDown(rChild(rootIndx), rChild(rChild(rootIndx)));
    nodes[rChild(rootIndx)] = nodes[rootIndx];

    // move the new roots right child to the roots right child's left child
    shiftUp(rChild(newRootIndx), lChild(rChild(rootIndx)));

    // move the new root node into the root node
    nodes[rootIndx] = nodes[newRootIndx];
    nodes[newRootIndx].key = NULL;

    // shift up to where the new root was, it's left child
    shiftUp(lChild(newRootIndx), newRootIndx);

    // adjust balances of nodes in their new positions
    if (nodes[rootIndx].balance == -1) { // new root
        nodes[rChild(rootIndx)].balance = 0; // old root
        nodes[lChild(rootIndx)].balance = 1; // left from old root
    } else if (nodes[rootIndx].balance == 0) {
        nodes[rChild(rootIndx)].balance = 0;
        nodes[lChild(rootIndx)].balance = 0;
    } else {
        nodes[rChild(rootIndx)].balance = -1;
        nodes[lChild(rootIndx)].balance = 0;
    }

    nodes[rootIndx].balance = 0;
}

// Where rootIndx is the highest point in the rotating tree
// not the root of the first Left rotation
void rotateRightLeft(int rootIndx) {
    int newRootIndx = lChild(rChild(rootIndx));

    // shift the root's left subtree down to the left
    shiftDown(lChild(rootIndx), lChild(lChild(rootIndx)));
    nodes[lChild(rootIndx)] = nodes[rootIndx];

    // move the new roots left child to the roots left child's right child
    shiftUp(lChild(newRootIndx), rChild(lChild(rootIndx)));

    // move the new root node into the root node
    nodes[rootIndx] = nodes[newRootIndx];
    nodes[newRootIndx].key = NULL;

    // shift up to where the new root was it's right child
    shiftUp(rChild(newRootIndx), newRootIndx);

    // adjust balances of nodes in their new positions
    if (nodes[rootIndx].balance == 1) { // new root
        nodes[lChild(rootIndx)].balance = 0; // old root
        nodes[rChild(rootIndx)].balance = -1; // right from old root
    } else if (nodes[rootIndx].balance == 0) {
        nodes[lChild(rootIndx)].balance = 0;
        nodes[rChild(rootIndx)].balance = 0;
    } else {
        nodes[lChild(rootIndx)].balance = 1;
        nodes[rChild(rootIndx)].balance = 0;
    }

    nodes[rootIndx].balance = 0;
}

シフトによってノードが上書きされる場合は、単一のノードをコピーするだけであることに注意してください

各ノードで高さの差を取得するのは非常にコストがかかるため、効率については、各ノードにバランスを格納することが必須です。

int getHeight(int indx) {
    if (indx >= size || nodes[indx].key == NULL) {
        return 0;
    } else {
        return max(getHeight(lChild(indx)) + 1, getHeight(rChild(indx)) + 1);
    }
}

これを行うには、リストを変更するときに影響を受けるノードでバランスを更新する必要がありますが、これは厳密に必要なケースのみを更新することである程度効率的になります. 削除の場合、この調整は

// requires non null node index and a balance factor baised off whitch child of it's parent it is or 0
private void deleteNode(int i, short balance) {
    int lChildIndx = lChild(i);
    int rChildIndx = rChild(i);

    count--;
    if (nodes[lChildIndx].key == NULL) {
        if (nodes[rChildIndx].key == NULL) {

            // root or leaf
            nodes[i].key = NULL;
            if (i != 0) {
                deleteBalance(parent(i), balance);
            }
        } else {
            shiftUp(rChildIndx, i);
            deleteBalance(i, 0);
        }
    } else if (nodes[rChildIndx].key == NULL) {
        shiftUp(lChildIndx, i);
        deleteBalance(i, 0);
    } else {
        int successorIndx = rChildIndx;

        // replace node with smallest child in the right subtree
        if (nodes[lChild(successorIndx)].key == NULL) {
            nodes[successorIndx].balance = nodes[i].balance;
            shiftUp(successorIndx, i);
            deleteBalance(successorIndx, 1);
        } else {
            int tempLeft;
            while ((tempLeft = lChild(successorIndx)) != NULL) {
                successorIndx = tempLeft;
            }
            nodes[successorIndx].balance = nodes[i].balance;
            nodes[i] = nodes[successorIndx];
            shiftUp(rChild(successorIndx), successorIndx);
            deleteBalance(parent(successorIndx), -1);
        }
    }
}

同様に挿入の場合、これは

void insertBalance(int pviotIndx, short balance) {
    while (pviotIndx != NULL) {
        balance = (nodes[pviotIndx].balance += balance);

        if (balance == 0) {
            return;
        } else if (balance == 2) {
            if (nodes[lChild(pviotIndx)].balance == 1) {
                rotateRight(pviotIndx);
            } else {
                rotateLeftRight(pviotIndx);
            }
            return;
        } else if (balance == -2) {
            if (nodes[rChild(pviotIndx)].balance == -1) {
                rotateLeft(pviotIndx);
            } else {
                rotateRightLeft(pviotIndx);
            }
            return;
        }

        int p = parent(pviotIndx);

        if (p != NULL) {
            balance = lChild(p) == pviotIndx ? (short)1 : (short)-1;
        }

        pviotIndx = p;
    }
}

ご覧のとおり、これは単純な「ノード」の配列を使用するだけで、gitHub array-avl-treeと最適化とバランシング (コメントに投稿するリンク) を指定して C コードから変換しましたが、リスト

最後に、私は AVL ツリーまたは最適な実装について最小限の知識しか持っていないので、これがバグがない、または最も効率的であるとは主張しませんが、少なくとも私の目的のためには予備テストに合格しています。

于 2016-05-15T13:25:17.963 に答える