13/01/01 02:58:17.72
>>599
削除時に回転が必要になるのは左右の木の高さの差が2になったとき。
左右の木の高さの差が2になるのは木の高さが1減ったとき。
木の高さが1減るのは木のバランスがイーブンになったとき。
木のバランスがイーブンになるのは
左に傾いている木の左のノードを削除したとき。
右に傾いている木の右のノードを削除したとき。
木の回転が行われたとき。
木のバランスがイーブンでなかったら木の高さは変わってないわけだから
平衡がとれてるってことでその上のノードでは回転は必要なくなる。
削除時の回転は、回転後にバランスがイーブンになるものと、
回転後にバランスがイーブンにならないものとがある。
分類するとこうなる。
URLﾘﾝｸ(i.imgur.com)
ノードのバランスをチェックすることで左への回転か右への回転かを
わけることができる。子のバランスをチェックすることで一重回転か
二重回転かをわけることができる。一重回転のときは子のバランスを
チェックすることで回転後のバランスをわけることができる。
二重回転のときは孫のバランスをチェックすることで回転後のバランスを
わけることができる。
削除時はパターンが2個増えて、平衡したという判断の仕方が変わるだけ。難しくないっしょ。