0

MarkAllenWesisによるデータ構造とアルゴリズムのスプレーツリーについて読んでいます

スプレイ戦略はローテーションのアイデアに似ていますが、ローテーションの実行方法についてもう少し選択的である点が異なります。アクセスパスに沿って下から上に回転します。xを、回転しているアクセスパス上の（ルート以外の）ノードとします。xの親がツリーのルートである場合、xとルートを回転させるだけです。これは、アクセスパスに沿った最後の回転です。それ以外の場合、xには親（p）と祖父母（g）の両方があり、考慮すべき2つのケースと対称性があります。最初のケースはジグザグのケースです。ここで、xは右の子で、pは左の子です（またはその逆）。この場合、AVLの2回転とまったく同じように、2回転を実行します。それ以外の場合は、ジグジグの場合があります。xとpは、両方とも左の子、または両方とも右の子です。

上記のテキストで、「2つのケースと対称性があります」というステートメントの後に著者はどういう意味ですか？2つのケースが示されていますが、ここでの対称性は何ですか？

ありがとう！

4

2 に答える 2

2

私はそれがかなり基本的な軸対称だと思います：

ジグザグの場合の例、ここに 2 つの対称ツリーがあります。

     g
    / \ 
    p  d
   /\
  c  x
    / \
   a   b

     g
    / \ 
   d   p
      /\
     x  c
    / \
   a   b
于 2011-09-05T09:41:31.560 に答える
0

たとえば、「問題のノードがその親の右の子であり、親が祖父母の左の子である場合」というケースがあるとします。この場合、左に回転してから右に回転します。したがって、ノードは祖父母に到達します。

この場合の対称部分は、「問題のノードがその親の左の子であり、親が祖父母の右の子である場合」です。この場合、右回転を行ってから左回転を行います。したがって、ノードは祖父母に到達します。

左を右に、右を左に置き換えると、対称のケースが得られます。

スプレイ ツリーの回転には 3 つのケースしかありません。ここにリストされてい ます スプレーを使用する場合と使用しない場合の検索の実行時の違いを確認できます。

于 2012-01-18T03:53:32.450 に答える