1

私は次のAVLツリーを持っています：

                               10
                             /    \
                            5     12
                           / \   /  \
                          2  8   11  13
                        /  \ /\   
                        1  4 7 9

3を挿入すると、次のようになります。

                               10
                             /    \
                            5     12
                           / \   /  \
                          2  8   11  13
                        /  \ /\   
                        1  4 7 9
                          /
                         3

各ノードのバランス係数を計算すると、すべてのBFが有効であるように見えます:(ノード：BF）-> 10：1、5：0、2：-1、1：0、4：-1、8：0、 7：0、9：0、3：0、12：0、11：0、13：0しかし、どうやらこのツリーはバランスを取り直す必要があります。無効なBFはどこにあり、必要なローテーションをどのように行うのでしょうか。

4

1 に答える 1

1

10は、左側のサブツリー5-2-4-3と右側のサブツリー12-13のバランス係数が2である必要があります。1回転後の有効なツリーは、5|のようになります。2 10 | 1 4 8 12 | nil nil 3 nil 7 91113。

リバランスの可能な方法は、cut-link-algorithmです。1。不均衡なノードzに、その子yとその子xの1つに名前を付けます。2.ノードの名前をa、b、cに順番に変更し、子を左から右にT0、T1、T2、T3にします。3. bを新しいルート、aを左の子、cを右の子として設定します。4.左から右に対応する4つのサブツリーをT0、T1、T2、およびT3として追加します。

于 2011-02-02T22:59:14.703 に答える