広さの木に関して

Question

私はマーク・アレン・ウェシスによるデータ構造とアルゴリズムの広がった木について読んでいます

スプレイ戦略は、回転の実行方法についてもう少し選択的であることを除いて、回転のアイデアに似ています。アクセスパスに沿ってボトムアップを回転させます。 xを回転しているアクセスパス上の（非ルート）ノードとします。 Xの親がツリーのルートである場合、Xとルートを回転させるだけです。これは、アクセスパスに沿った最後の回転です。それ以外の場合、xには親（p）と祖父母（g）の両方があり、考慮すべき2つのケースと対称性があります。最初のケースはZig-Zagケースです。ここではXは右の子供で、Pは左の子供です（またはその逆）。この場合、AVLダブル回転とまったく同じように、二重回転を実行します。それ以外の場合は、Zig-Zigケースがあります。XとPは、左の子供または両方の正しい子供の両方です。

上記のテキストでは、著者は「2つのケースと対称性があります」という声明に従うこととはどういう意味ですか？ 2つのケースが与えられますが、ここでの対称とは何ですか？

ありがとう！

Answer 1

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

ジグザグケースの例では、ここに2つの対称ツリーがあります。

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

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

Answer 2

たとえば、ケースは「質問のノードが親の正しい子であり、親が祖父母の左の子である場合」と言うと、この場合、左回転してから右の回転を行います。したがって、ノードは壮大な親になります。

このケースの対称部分は、「質問のノードが親の左の子であり、親が祖父母の右子である場合」です。したがって、ノードは壮大な親になります。

左右に左と右に置き換えて、対称ケースを取得します。

スプレーツリーでの回転には3つのケースしかありません。リストしました ここスプレイなしの有無にかかわらず、検索のランタイムの違いを確認できます。