1

手作業で要求されたツリー(bst>avl)のバランシングを実行しましたが、本当に簡単だったので、正しく実行できたかどうかはわかりません。

        a
       / \
      e3になる
     / \
    e1 e2

初期状態: 'a' は 'b' (左) と 'e3' (右) の親、'b' は 'e1' (左) と 'e2' (右) の親です。

右回転を適用すると、次のようになります。

        b
       / \
     e1a
         / \
       e2 e3

左側に子 'e1'、右側に子 'a' を持つ 'a' の代わりに 'b' を使用すると、'a' は左側に 'b' の 'e2' を取得します。

だから質問：

  1. e1 自体が他の要素を含むサブツリーまたはノードである場合でも、このローテーションを実行できますか?
  2. 2. e2 と e3 がない場合でも、このローテーションを実行できますか?

例 11; 12;16

     16
     /
   13
  /
10

初期状態: 16 は 13 の親であり、13 は 10 の親です。それから実行できますか: 13 は 10 (左) と 16 (右) の親です

私はそれが単純化されていることを知っていますが、理論は、それが明確であると仮定して、これらのことをカバーしていないことがよくあります。手伝ってくれてありがとう、

4

1 に答える 1

0

はい、本当にすべてに。順序プロパティについて考えてみましょう: 左の子孫 < ノードおよびノー​​ド < 右の子孫。回転がこれを保持する方法に注意してください。a と b をローテーション前の e1、e2、e3 と比較し、ローテーション後の順序と子孫の関係を確認します。捨てる前に考えさせてもらいます。

于 2010-12-06T05:49:34.253 に答える