66

AVL-treeでノードのバランスを計算する最良の方法を探しています。私はそれが機能していると思っていましたが、いくつかの重い挿入/更新の後、正しく機能していないことがわかりました(まったく)。

これは一種の 2 つの部分からなる質問です。最初の部分は、サブツリーの高さを計算する方法です。「ノードの高さは、そのノードから葉までの最長の下り経路の長さです」という定義を知っています。 ." 私はそれを理解していますが、実装に失敗しています。さらに混乱させるために、ツリーの高さに関するウィキペディアでこの引用を見つけることができます。

2番目の部分は、AVLツリーのサブツリーのバランス係数を取得することです。 「あなたLとサブツリーの高さを取得してからR差し引く」RLという概念を理解するのに問題はありません。そして、これは次のように定義されています。BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]

ウィキペディアを読むと、AVL ツリーへの挿入を説明する最初の数行で次のように述べられています。

続いて、「バランス ファクターが 2 または -2 になる場合、このノードをルートとするツリーはバランスが取れていないため、ツリーのローテーションが必要です。ツリーのバランスをとるには、せいぜい 1 回または 2 回のローテーションが必要です。」- 問題なく把握できます。

しかし（はい、常にしかしがあります）。

ここで混乱します。テキストには、「R のバランス係数が 1 の場合、そのノードの (外部) 右側で挿入が発生し、左回転が必要であることを意味します」と記載されています。しかし、私が引用したように、バランス係数が範囲内[-1, 1]にある場合、バランスをとる必要はないとテキストが述べていることを理解していますか?

概念の理解に非常に近づいていると感じています。ツリーのローテーションを減らし、通常のバイナリ検索ツリーを実装し、AVL ツリーを把握しようとしていますが、その本質的なひらめきが欠けているようです。

編集：私は常にコードで何かを把握するのが簡単だったので、コード例は学術的な公式よりも好まれていますが、どんな助けも大歓迎です.

編集：すべての回答を「承認済み」としてマークできたらいいのにと思いますが、私にとっては、NIckの回答が最初に「あはは」になったものでした。

4

9 に答える 9

82

パート1-高さ

starblueが言うように、高さは再帰的です。擬似コードの場合：

height(node) = max(height(node.L), height(node.R)) + 1

これで、高さは2つの方法で定義できます。ルートからそのノードへのパス内のノードの数、またはリンクの数である可能性があります。参照したページによると、最も一般的な定義はリンクの数です。この場合、完全な擬似コードは次のようになります。

height(node): 
   if node == null:
        return -1
   else:
        return max(height(node.L), height(node.R)) + 1

ノードの数が必要な場合、コードは次のようになります。

height(node): 
   if node == null:
        return 0
   else:
        return max(height(node.L), height(node.R)) + 1

いずれにせよ、私が思うリバランスアルゴリズムは同じように機能するはずです。

ただし、高さ情報を毎回計算するのではなく、ツリーに保存して更新すると、ツリーの効率が大幅に向上します（O（ln（n）） ）。（O（n））

パート2-バランシング

「Rのバランスファクターが1の場合」とは、一番上のバランスファクターが2の場合の右枝のバランスファクターのことです。二回転。（Pythonのような）擬似コード：

if balance factor(top) = 2: // right is imbalanced
     if balance factor(R) = 1: // 
          do a left rotation
     else if balance factor(R) = -1:
          do a double rotation
else: // must be -2, left is imbalanced
     if balance factor(L) = 1: // 
          do a left rotation
     else if balance factor(L) = -1:
          do a double rotation

これが理にかなっているといいのですが

于 2009-02-22T21:37:36.863 に答える
6

  • 高さは再帰によって簡単に実装できます。サブツリーの高さの最大値に1を加えたものを取ります。

  • 「Rのバランス係数」とは、バランスが崩れているツリーの右側のサブツリーを指していると思います。

于 2009-02-22T21:31:08.533 に答える
4

高さを見つける別の方法は次のとおりです。ノードにheightという属性を追加します。

class Node
{
data value; //data is a custom data type
node right;
node left;
int height;
}

ここで、ツリーの単純な幅優先走査を実行し、各ノードの高さの値を更新し続けます。

int height (Node root)
{
Queue<Node> q = Queue<Node>();
Node lastnode;
//reset height
root.height = 0;

q.Enqueue(root);
while(q.Count > 0)
{
   lastnode = q.Dequeue();
   if (lastnode.left != null){
      lastnode.left.height = lastnode.height + 1; 
      q.Enqueue(lastnode.left);
   }

   if (lastnode.right != null){
      lastnode.right.height = lastnode.height + 1;
      q.Enqueue(lastnode.right);
   }
}
return lastnode.height; //this will return a 0-based height, so just a root has a height of 0
}

乾杯、

于 2010-10-30T20:54:55.137 に答える
4

ここで混乱します。テキストには、「R のバランス係数が 1 の場合、そのノードの (外部) 右側で挿入が発生し、左回転が必要であることを意味します」と記載されています。しかし、私が引用したように、バランス係数が[-1、1]の範囲内にある場合、バランスを取る必要はないというテキストを理解しているからですか?

さて、ひらめきの時間。

回転が何をするかを考えてみましょう。左回転について考えてみましょう。

 P = parent
 O = ourself (the element we're rotating)
 RC = right child
 LC = left child (of the right child, not of ourself)

 P              10
  \               \
   O               15
    \                \
     RC               20
    /                /
   LC               18

          ↓
 P              10
   \               \
     RC              20
   /               /
  O              15
   \               \
   LC              18

 basically, what happens is;

 1. our right child moves into our position
 2. we become the left child of our right child
 3. our right child's left child becomes our right

さて、ここで注目していただきたいのは、この左回転は木の深さを変えていないということです。それをしたことで、私たちはもはやバランスが取れていません。

しかし、これが AVL の魔法です。右の子を最初に右に回転させると、次のようになります...

 P
  \
   O
    \
     LC
      \
       RC

そして、O を左に回転させると、次のようになります...

 P
   \
     LC
    /  \
   O   RC

魔法！ツリーのレベルを取り除くことができました -バランスのとれたツリーを作成しました。

ツリーのバランスをとるということは、余分な深さを取り除き、上位レベルをより完全に詰めることを意味します - これはまさに今行ったことです。

シングル/ダブルローテーションに関する全体的なことは、サブツリーを次のようにする必要があるということです。

 P
  \
   O
    \
     LC
      \
       RC

回転する前に - その状態にするには、右に回転する必要がある場合があります。しかし、すでにその状態にある場合は、左回転を行うだけで済みます。

于 2009-03-24T21:30:34.617 に答える
2

さて、次の再帰関数を使用して木の高さを計算できます。

int height(struct tree *t) {
    if (t == NULL)
        return 0;
    else
        return max(height(t->left), height(t->right)) + 1;
}

と を適切に定義max()しstruct treeます。これが、引用したパスの長さに基づく定義に対応する理由を理解するには、時間をかけてください。この関数は、空のツリーの高さとしてゼロを使用します。

ただし、AVL ツリーのようなものでは、必要になるたびに高さを実際に計算するとは思いません。代わりに、各ツリー ノードには、そのノードをルートとするサブツリーの高さを記憶する追加のフィールドが追加されます。ツリーは挿入や削除によって変更されるため、このフィールドは最新の状態に保つ必要があります。

上記のようにツリー内にキャッシュするのではなく、毎回高さを計算すると、AVL ツリーの形状は正しくなりますが、期待される対数パフォーマンスは得られないと思います。

于 2009-02-22T21:49:13.717 に答える
2

Here's where it gets confusing, the text states "If the balance factor of R is 1, it means the insertion occurred on the (external) right side of that node and a left rotation is needed". But from m understanding the text said (as I quoted) that if the balance factor was within [-1, 1] then there was no need for balancing?

R is the right-hand child of the current node N.

If balance(N) = +2, then you need a rotation of some sort. But which rotation to use? Well, it depends on balance(R): if balance(R) = +1 then you need a left-rotation on N; but if balance(R) = -1 then you will need a double-rotation of some sort.

于 2009-02-22T21:52:27.653 に答える
0

コンストラクターで 0 に初期化されBinaryTree<T, Comparator>::NodeたsubtreeHeightデータ メンバーを指定し、次のように毎回自動的に更新します。

template <typename T, typename Comparator>
inline void BinaryTree<T, Comparator>::Node::setLeft (std::shared_ptr<Node>& node) {
    const std::size_t formerLeftSubtreeSize = left ? left->subtreeSize : 0;
    left = node;
    if (node) {
        node->parent = this->shared_from_this();
        subtreeSize++;
        node->depthFromRoot = depthFromRoot + 1;
        const std::size_t h = node->subtreeHeight;
        if (right)
            subtreeHeight = std::max (right->subtreeHeight, h) + 1;
        else
            subtreeHeight = h + 1;
    }
    else {
        subtreeSize -= formerLeftSubtreeSize;
        subtreeHeight = right ? right->subtreeHeight + 1 : 0;
    }
}

template <typename T, typename Comparator>
inline void BinaryTree<T, Comparator>::Node::setRight (std::shared_ptr<Node>& node) {
    const std::size_t formerRightSubtreeSize = right ? right->subtreeSize : 0;
    right = node;
    if (node) {
        node->parent = this->shared_from_this();
        subtreeSize++;
        node->depthFromRoot = depthFromRoot + 1;
        const std::size_t h = node->subtreeHeight;
        if (left)
            subtreeHeight = std::max (left->subtreeHeight, h) + 1;
        else
            subtreeHeight = h + 1;
    }
    else {
        subtreeSize -= formerRightSubtreeSize;
        subtreeHeight = left ? left->subtreeHeight + 1 : 0;
    }
}

データ メンバsubtreeSizeおよびdepthFromRootも更新されることに注意してください。これらの関数は、ノードを挿入するときに呼び出されます (すべてテスト済み)。

template <typename T, typename Comparator>
inline std::shared_ptr<typename BinaryTree<T, Comparator>::Node>
BinaryTree<T, Comparator>::Node::insert (BinaryTree& tree, const T& t, std::shared_ptr<Node>& node) {
    if (!node) {
        std::shared_ptr<Node> newNode = std::make_shared<Node>(tree, t);
        node = newNode;
        return newNode;
    }
    if (getComparator()(t, node->value)) {
        std::shared_ptr<Node> newLeft = insert(tree, t, node->left);
        node->setLeft(newLeft);
    }
    else {
        std::shared_ptr<Node> newRight = insert(tree, t, node->right);
        node->setRight(newRight);
    }
    return node;
}

ノードを削除する場合は、別のバージョンのremoveLeftとremoveRightを に置き換えて使用subtreeSize++;しsubtreeSize--;ます。rotateLeftおよびのアルゴリズムrotateRightも問題なく適用できます。以下がテストされ、合格しました。

template <typename T, typename Comparator>
void BinaryTree<T, Comparator>::rotateLeft (std::shared_ptr<Node>& node) {  // The root of the rotation is 'node', and its right child is the pivot of the rotation.  The pivot will rotate counter-clockwise and become the new parent of 'node'.
    std::shared_ptr<Node> pivot = node->right;
    pivot->subtreeSize = node->subtreeSize;
    pivot->depthFromRoot--;
    node->subtreeSize--;  // Since 'pivot' will no longer be in the subtree rooted at 'node'.
    const std::size_t a = pivot->left ? pivot->left->subtreeHeight + 1 : 0;  // Need to establish node->heightOfSubtree before pivot->heightOfSubtree is established, since pivot->heightOfSubtree depends on it.
    node->subtreeHeight = node->left ? std::max(a, node->left->subtreeHeight + 1) : std::max<std::size_t>(a,1);
    if (pivot->right) {
        node->subtreeSize -= pivot->right->subtreeSize;  // The subtree rooted at 'node' loses the subtree rooted at pivot->right.
        pivot->subtreeHeight = std::max (pivot->right->subtreeHeight, node->subtreeHeight) + 1;
    }
    else
        pivot->subtreeHeight = node->subtreeHeight + 1;
    node->depthFromRoot++;
    decreaseDepthFromRoot(pivot->right);  // Recursive call for the entire subtree rooted at pivot->right.
    increaseDepthFromRoot(node->left);  // Recursive call for the entire subtree rooted at node->left.
    pivot->parent = node->parent;
    if (pivot->parent) {  // pivot's new parent will be its former grandparent, which is not nullptr, so the grandparent must be updated with a new left or right child (depending on whether 'node' was its left or right child).
        if (pivot->parent->left == node)
            pivot->parent->left = pivot;
        else
            pivot->parent->right = pivot;
    }
    node->setRightSimple(pivot->left);  // Since pivot->left->value is less than pivot->value but greater than node->value.  We use the NoSizeAdjustment version because the 'subtreeSize' values of 'node' and 'pivot' are correct already.
    pivot->setLeftSimple(node);
    if (node == root) {
        root = pivot;
        root->parent = nullptr; 
    }
}

どこ

inline void decreaseDepthFromRoot (std::shared_ptr<Node>& node) {adjustDepthFromRoot(node, -1);}
inline void increaseDepthFromRoot (std::shared_ptr<Node>& node) {adjustDepthFromRoot(node, 1);}

template <typename T, typename Comparator>
inline void BinaryTree<T, Comparator>::adjustDepthFromRoot (std::shared_ptr<Node>& node, int adjustment) {
    if (!node)
        return;
    node->depthFromRoot += adjustment;
    adjustDepthFromRoot (node->left, adjustment);
    adjustDepthFromRoot (node->right, adjustment);
}

コード全体は次のとおりです。 http://ideone.com/d6arrv

于 2015-10-24T00:16:17.470 に答える