4

AVL ツリーのバランスを取るのに問題があります。それらのバランスをとる方法の手順を高低で検索しましたが、役立つものは何も得られません.

私が知っているのは以下の4種類です。

  • 1 回左回転
  • シングル右回転
  • ダブル左右回転
  • ダブル左右回転

しかし、それらのどれをどのノードに適用するかを選択する方法がわかりません!

どんな助けでも大歓迎です！

4

2 に答える 2

2

これは Java 実装であり、そこでアルゴリズムのアイデアを得ることができます:

private Node<T> rotate(Node<T> n) {
    if(n.getBf() < -1){
            if(n.getRight().getBf() <= 0){
                return left(n);         
            }
            if(n.getRight().getBf() > 0){
                return rightLeft(n);
            }
    }   
    if(n.getBf() > 1){
            if(n.getLeft().getBf() >= 0){
                return right(n);
            }
            if(n.getLeft().getBf() <  0){
                return leftRight(n);
            }
    }
    return n;
}

4回転の個別の方法は次のとおりです。

/**
 * Performs a left rotation on a node
 * 
 * @param n The node to have the left rotation performed on
 * @return The new root of the subtree that is now balanced due to the rotation
 */
private Node<T> left(Node<T> n) {
    if(n != null){
        Node<T> temp = n.getRight();
        n.setRight(temp.getLeft());
        temp.setLeft(n);
        return temp;
    }
    return n;   
}

/**
 * Performs a right rotation on a node
 * 
 * @param n The node to have the right rotation performed on
 * @return The new root of the subtree that is now balanced due to the rotation
 */
private Node<T> right(Node<T> n) {
    if(n != null){
        Node<T> temp = n.getLeft();
        n.setLeft(temp.getRight());
        temp.setRight(n);
        return temp;
    }
    return n;
}

/**
 * Performs a left right rotation on a node
 * 
 * @param n The node to have the left right rotation performed on
 * @return The new root of the subtree that is now balanced due to the rotation
 */
private Node<T> leftRight(Node<T> n) {
    n.setLeft(left(n.getLeft()));
    Node<T> temp = right(n);
    return temp;
}

/**
 * Performs a right left rotation on a node
 * 
 * @param n The node to have the right left rotation performed on
 * @return The new root of the subtree that is now balanced due to the rotation
 */
private Node<T> rightLeft(Node<T> n) {
    n.setRight(right(n.getRight()));
    Node<T> temp = left(n);
    return temp;
}
于 2013-03-04T18:39:35.500 に答える
0

AVLツリーの重要な不変条件は、各ノードのバランス係数が-1、0、または+1のいずれかであることです。ここで、「バランス係数」とは、左右のサブツリー間の高さの差です。+1は、左側のサブツリーが右側のサブツリーより1つ高いことを意味し、-1は、左側のサブツリーが右側のサブツリーより1つ短いことを意味し、0は、サブツリーのサイズが同じであることを意味します。この情報は通常、各ノードにキャッシュされます。

バランス係数が-2または+2のノードを取得する場合は、ローテーションを実行する必要があります。回転が必要な場合の1つの可能な設定は次のとおりです。

          u (-2)
         / \
        A   v (-1)
           / \
          B   C

これらの木の高さを埋めると、

          u h + 2
         / \
    h-1 A   v h + 1
           / \
      h-1 B   C h

これが発生した場合、右回転を1回実行すると次のようになります。

         v h+1
        / \ 
     h u   C h
      / \
 h-1 A   B h-1

そしてねえ！木はバランスが取れています。この木の鏡像は、左に1回転するだけでも修正できます。

すべてのAVLツリーの回転は、狭い範囲内で可能なバランス係数を列挙し、各ステップでどの回転を適用するかを決定するだけで決定できます。これは読者の練習問題として残しておきます。:-)答えを調べたいだけなら、AVLツリーに関するウィキペディアの記事に、適用する必要があるかもしれないすべての回転を要約した素晴らしい写真があります。

お役に立てれば！

于 2013-01-19T22:05:46.370 に答える