0

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

リバランスされるノードが X であると仮定します。修正しなければならないケースが 4 つあります (2 つは他の 2 つのミラー イメージです): X の左の子の左のサブツリーへの挿入、右のサブツリーへの挿入X の左の子の、 X の右の子の左のサブツリーへの挿入、または X の右の子の右のサブツリーへの挿入。

バランスは木の回転によって復元されます。

以下は、上記のテキスト スニペットに関する質問です。

  1. 著者は、他の 2 つのミラー イメージによって何を意味しますか?
  2. 一回転と二回転の対称ケースとは？

ありがとう

4

1 に答える 1

2

挿入されるノードが I だとします。本には 4 つの場合があると書かれています。I が X の左の子の左の子であるものを考えてみましょう:

    X
   / \
  ?   ?
 / \ / \
I  ? ?  ?

これの「鏡」は、私が X の右の子の右の子であるときです。

    X
   / \
  ?   ?
 / \ / \
?  ? ?  I

これが「ミラー」である理由は、両方のケースで行う必要がある回転が同じであり、左右が逆になっているだけだからです。I が X の右子の左子であり、I が X の左子の右子である他の 2 つのケースについても同じことが言えます。

2 番目の質問については、考え方は同じです。対称の場合 (つまりミラーの場合) は、左右を逆にして同じ回転を行います。

于 2011-09-05T09:38:43.327 に答える