-
25-10-2019 - |
質問
私はマーク・アレン・ウェシスによるデータ構造とアルゴリズムの広がった木について読んでいます
スプレイ戦略は、回転の実行方法についてもう少し選択的であることを除いて、回転のアイデアに似ています。アクセスパスに沿ってボトムアップを回転させます。 xを回転しているアクセスパス上の(非ルート)ノードとします。 Xの親がツリーのルートである場合、Xとルートを回転させるだけです。これは、アクセスパスに沿った最後の回転です。それ以外の場合、xには親(p)と祖父母(g)の両方があり、考慮すべき2つのケースと対称性があります。最初のケースはZig-Zagケースです。ここではXは右の子供で、Pは左の子供です(またはその逆)。この場合、AVLダブル回転とまったく同じように、二重回転を実行します。それ以外の場合は、Zig-Zigケースがあります。XとPは、左の子供または両方の正しい子供の両方です。
上記のテキストでは、著者は「2つのケースと対称性があります」という声明に従うこととはどういう意味ですか? 2つのケースが与えられますが、ここでの対称とは何ですか?
ありがとう!
解決
私はそれがかなり基本的な軸対称だと思います:
ジグザグケースの例では、ここに2つの対称ツリーがあります。
g
/ \
p d
/\
c x
/ \
a b
g
/ \
d p
/\
x c
/ \
a b
他のヒント
たとえば、ケースは「質問のノードが親の正しい子であり、親が祖父母の左の子である場合」と言うと、この場合、左回転してから右の回転を行います。したがって、ノードは壮大な親になります。
このケースの対称部分は、「質問のノードが親の左の子であり、親が祖父母の右子である場合」です。したがって、ノードは壮大な親になります。
左右に左と右に置き換えて、対称ケースを取得します。
スプレーツリーでの回転には3つのケースしかありません。リストしました ここスプレイなしの有無にかかわらず、検索のランタイムの違いを確認できます。