1

そのため、AVL ツリーのバランスをとる方法を理解するのに苦労しています。回転については理解していますが、ノードの高さのバランス係数を見つける方法がわかりません。たとえば、次のようになります。

http://i.imgur.com/yh5zNIl.png

各ノードのバランス係数を実際に見つける方法を誰か説明してもらえますか?

[(左のサブツリー) - (右のサブツリー)] の高さが (-1<= x <= 1) 内にない場合、バランスが取れていないことはわかっていますが、「x」を見つける方法がわかりません。

（編集：コードは必要ありません。BFを見つける方法を理解したいだけです）。

4

3 に答える 3

1

あなたの質問を正しく理解できれば、特定のノードのバランス係数を維持する方法を知りたいでしょう。追跡を維持する最善の方法は、ツリーで「挿入」を行うときです。これは、新しいノードが「現在の」ノードの左側または右側のどちらに移動するかを知っているためです。左に行くと残高が減り、右に行くと残高が増えます。アイデアは、「挿入」メソッドを終了する前に、ツリーのバランスを既に取っておくことです。

私が見た別のアプローチは、「挿入」中にバランスをとらないことです。BST の場合と同じように挿入するだけです。挿入後、各ノードで左側のサブツリーと右側のサブツリーの高さを取得し、ポインターのシャッフルを開始するバランス作業を開始します。高さを見つける際にすべてのノードで O(logn) が発生し、すべてのノードでこれを行うため、n*O(logn) になるため、これは適切なアプローチではありません。

私がかつて書いた「挿入」メソッドを投稿しています。これは、挿入ごとにツリーのバランスを保ち、挿入中のどの時点でも高さを個別に計算しません。それが役立つかどうかを確認してください：

Node*
AVL::insert(Node* node, int key, int value)
{
    if(node == NULL)
        node = new Node(key, value);

    else if (key <= node->key)
    {
        node->balance--;
        node->left = insert(node->left, key, value);
    }

    else if (key > node->key)
    {
        node->balance++;
        node->right = insert(node->right, key, value);  
    }

    // Right Tree Heavy
    if (node->balance == 2) 
    { 
        // Left tree unbalanced
        if (node->right && node->right->balance == 1) 
        {
            // LL
            node = singleLeftRotation(node);
            node->balance = 0;
            node->left->balance = 0;
        }
        if (node->right && node->right->balance == -1) 
        {
            // LR
            int nodeRLBalance = node->right->left->balance;
            node = doubleLeftRotation(node);
            node->balance = 0;
            node->left->balance = nodeRLBalance == 1 ? -1 : 0;
            node->right->balance = nodeRLBalance == -1 ? 1 : 0;
        }
    }

    // Left Tree Heavy
    if (node->balance == -2) 
    {
        // Right tree unbalanced
        if (node->left && node->left->balance == -1) 
        {
            // RR
            node = singleRightRotation(node);
            node->balance = 0;
            node->right->balance = 0;
        }
        if (node->left && node->left->balance == 1) 
        {
            // RL
            int nodeLRBalance = node->left->right->balance;
            node = doubleRightRotation(node);
            node->balance = 0;
            node->left->balance = nodeLRBalance == 1 ? -1 : 0;
            node->right->balance = nodeLRBalance == -1 ? 1 : 0;
        }
    }

    return node;
}
于 2013-10-06T18:09:54.767 に答える