Algorithm

木の回転

一次元領域探索の解説を呼んでいるうちに分かってない概念が多すぎて愕然とした。

結局

Kd-Tree→一次元領域探索→平衡二分探索木→赤黒木→木の回転

にまで遡ることになった。どんだけプログラマとしてモノを知らんねん…

木の回転


 

  R

  ∧

  P C

 ∧

A B

 


これを右回転すると


  P

  ∧

  A R

   ∧

  B C


となる。当然これを左回転すると元に戻る。


イメージ的には、木はそれぞれリングに棒が一つないしは二つくっついていて、それらが

ダラーんとぶら下がっているイメージだ。当然上から下までの長さは短い方が探索が速い。



で、回転のイメージは、右回転時は左下のリングを持って重力に任せるといい。

だが、そうだとすると回転の際にBの位置が変わっている。



これは、回転のルールとして

  • 要素の順序を崩さずに構造を変更する

というルールがあるためだ。二分木である以上は特定の順序付けルールで並んでいるため、その順序が変われば意味がなくなるからだ。


左の木:((A,P,B),Q,C)⇔右の木:(A,P,(B,Q,C))


というわけである。右回転疑似コードを書くと…


Pivot = Root.LChild

Root.LChild = Pivot.RChild

Pivot.RChild = Root

Root = Pivot

ついでに左回転

Pivot = Root.RChild

Root.RChild = Pivot.LChild

Pivot.LChild = Root

Root = Pivot



となる。

| | コメント (0) | トラックバック (0)