4

バイナリ ツリーのスキルを磨くためにいくつかの演習を行った結果、ウィキペディア: スプレー ツリーで概説されているように、スプレー ツリーを実装することにしました。

私が得ていないことの1つは、挿入に関する部分です。

それは言います：

まず、splay ツリーで x を検索します。x がまだ存在しない場合、それは見つかりませんが、その親ノード y は見つかりません。次に、y に対してスプレイ操作を実行し、y をスプレイ ツリーのルートに移動します。3 番目に、適切な方法で新しいノード x をルートとして挿入します。このように、y は新しいルート x の左または右の子になります。

私の質問は次のとおりです。上記のテキストは、記事の他の例に比べて非常に簡潔に見えますが、それはなぜですか? ここにはいくつかの落とし穴が残っているようです。たとえば、y ノードをルートまで展開した後、やみくもにルートを x に置き換えて、y を左または右の子として x に追加することはできません。

値がツリーにまだ存在していないと仮定しましょう。

私はこの木を持っています：

           10
          /  \
         5    15
        / \    \
       1   6    20

8 を挿入します。上記の説明で、6 ノードを見つけます。通常のバイナリ ツリーでは、6 ノードの右の子として 8 が追加されますが、ここではまず、ルートまでの 6 ノード:

            6
           / \
          5   10
         /     \
        1       15
                 \
                  20

次に、これら2つのいずれかが明らかに間違っています。

          8                                  8
           \                                /
            6                              6
           / \                            / \
          5   10                         5   10
         /     \                        /     \
        1       15                     1       15
                 \                              \
                  20                             20

    6 is not greater than 8          10 is not less than 8

最初にスプレイを行い、次にルートとして新しい値を正しく追加する唯一の方法は、次の基準をチェックする必要があることを意味するように思えます(スプレイされたノードを新しいルートの左の子として追加するため):

  1. ルートに展開したノードは、新しいルートよりも小さい (6 < 8)
  2. ルートに展開したノードの右端の子も、新しいルート (20 8) より小さいです。

ただし、展開したノードを分割する場合、適切な子を取得して新しいノードの適切な子として追加すると、次のようになります。

                        8
                       / \
                      6   10
                     /     \
                    5       15
                   /         \
                  1           20

しかし、この単純な変更で常に正しいツリーが得られるのでしょうか? 例を思いつくのに苦労していますが、これは次のようになる可能性があります。

  • 追加したい新しい値は、一時ルート (ルートに展開したノード) よりも高いですが、一時ルートの右側の子の左端の子よりも高いですか?

すなわち。広げた後、基本的にこのように見えるツリーですが、ルートを置き換える前は?

                        10
                       /  \
                      5    15
                          /  \
                        11    20

13 を追加すると、新しいツリーは次のようになります。

                        13
                       /  \
                     10    15
                     /    /  \
                    5   11    20  <-- 11, on the wrong side of 13

または、これは決して起こり得ませんか？

私の 2 番目の質問は次のとおりです。操作を次のように書き直す方がはるかに簡単ではないでしょうか。

まず、splay ツリーで x を検索します。x がまだ存在しない場合、それは見つかりませんが、その親ノード y は見つかりません。次に、新しいノードを親ノードの左または右の子として追加します。3 番目に、追加したノードでスプレイ操作を実行し、新しい値をスプレイ ツリーのルートに移動します。

私が変更したものを示すために私のものを強調してください。

4

3 に答える 3

5

あなたが説明した問題がどのように発生するかわかりません。このツリーに 13 を挿入したい場合は、最初にそれがどこにあるかを見つける必要があります。

                    10
                   /  \
                  5    15
                      /  \
                    11    20

10 からは右に、15 からは左に、11 からは右に進みます...そして、それ以上の要素はありません。13 がツリーにあった場合、11 の右の子としてそれを見つけることができます。したがって、ルールに従って、11 に対してスプレイ操作を実行し、11 をスプレイ ツリーのルートに移動します。

                    11
                   /  \
                  10   15
                 /       \
                5         20

次に、13 を新しいルートとして追加し、11 を左の子として追加します。

                    13
                   /  \
                  11   15
                 /       \
                10        20
               /
              5

今は問題ありません。

まず、splay ツリーで x を検索します。x がまだ存在しない場合、それは見つかりませんが、その親ノード y は見つかりません。次に、新しいノードを親ノードの左または右の子として追加します。3 番目に、追加したノードでスプレイ操作を実行し、新しい値をスプレイ ツリーのルートに移動します。

これも機能するように思えますが、私があなたの場合は、多くの人がテストしており、すでに十分に文書化されているため、Wikipedia で説明されているバージョンを実装しようとします。

于 2010-01-05T20:09:10.193 に答える
1

「 Splay Tree」という言葉を聞いて、少し前に読んだ CUJ の記事をすぐに思い出しました。

3 番目に、適切な方法で新しいノード x をルートとして挿入します。このように、y は新しいルート x の左または右の子になります。

はい。しかし、この新しいルート x には 2 つの子が必要です。そのため、この文は混乱を招く可能性があります。

于 2010-01-05T19:52:36.347 に答える
1

通常の二分探索木と同じように、新しいノードがツリーに追加されます。次に、新しいノードがルートまたはルートからの最初のレベルになるように展開されます。また、新しいノードを挿入するときは、配置する場所を見つける必要があるため、検索を行います。また、splay ツリーでの検索を含むすべての操作は、splay 操作をトリガーします。ウィキペディアの記事でそのように説明されているのはそのためかもしれません。新しいノードを挿入して展開するだけです。いずれにせよ、ツリーは以前よりもバランスが良くなります。ここでうまく動作します

于 2012-01-17T18:12:43.837 に答える