読者です 読者をやめる 読者になる 読者になる

破棄されたブログ

このブログは破棄されました。

木の回転の図メモ

アルゴリズムとデータ構造

f:id:namidamexx:20130919001112p:plain

木の回転がイマイチわからなかったので、 Wikipedia に載ってた擬似コードの流れを図にしてみた。

  • 根ノード R を Root、新たに根ノードとなるノード P (== Root.OS )を Pivot とする。
  • RS は回転側(Rotate side、内側)の子ノード
  • OS は回転と反対側(opposite side、外側)の子ノード
Pivot = Root.OS
Root.OS = Pivot.RS
Pivot.RS = Root
Root = Pivot

擬似コードでの回転処理イメージの仕方

  1. Pivot (== Root.OS) を Root から取り出す
  2. Pivot から RS (== Pivot.RS) を取り出して、Root の OS (== Root.OS) とする
  3. Root の木を Pivot の RS とする
  4. Pivot を Root とする
広告を非表示にする