AVL木の更新状況が見たい
AVL木は平衡二分木の一つで、ノードの追加・削除のたびに木の再構成を行い、検索時の計算時間を最小に抑えるようなデータ構造を維持する。木の再構成を行わない場合、最悪の場合には木の片側のみを使ってしまい検索時にO(n)の時間がかかってしまうが、再構成を行うことにより木を厳密に平衡に保つためO(logn)の時間で検索できる。更新・削除にも時間がかかるが、その分検索の時間を速くすることを目的としている。
実装を進めるにあたって、更新時の回転操作を正しく理解するためにも、木構造そのものを見ることが出来る方が分かり易いだろう、ということで、まず木構造をデバッグできるよう実装した。
ノードは双方向の連結リストになっているが、可視化する場合には幅優先探索によって同じ階層のノードを取得し、それをヒープ構造に入れることにした。ある階層の全てのノードがNULLになるまで、あるノードがNULLであっても子ノードの取得を続けるようにしているため、こうしておくと、あるノードの親がNULLかどうかも確認しやすい。見やすさのため、親がNULLの場合は何も出力が行わないようにする。NULLノードは[]で示している。
数字の隣はラベルで、AVL木において重要な役割を持つ。LEFT、EQUAL、RIGHT、はそれぞれ左部分木が深いか、平衡か、右部分木が深いか、が分かるようになっている。
Thanks to :
$ java AVLTree
Please input the value for root node. : 8
('q' for quit, 'p' for print, 's' for search.)
Please input. : p
8E---|
[] []
Please input. : 3
Please input. : 14
Please input. : p
8E-------|
3E---| 14E---|
[] [] [] []
Please input. : 2
Please input. : 6
Please input. : p
8L---------------|
3E-------| 14E-------|
2E---| 6E---| [] []
[] [] [] []
Please input. : 12
Please input. : 15
Please input. : p
8E---------------|
3E-------| 14E-------|
2E---| 6E---| 12E---| 15E---|
[] [] [] [] [] [] [] []
Please input. : 1
Please input. : 4
Please input. : p
8L-------------------------------|
3E---------------| 14E---------------|
2L-------| 6L-------| 12E-------| 15E-------|
1E---| [] 4E---| [] [] [] [] []
[] [] [] []
Please input. : 5
Rotate left at 6!
Please input. : p
8L-------------------------------|
3E---------------| 14E---------------|
2L-------| 5E-------| 12E-------| 15E-------|
1E---| [] 4E---| 6E---| [] [] [] []
[] [] [] [] [] []
Please input. : 7
Rotate left at 8!
Please input. : p
5E-------------------------------|
3L---------------| 8E---------------|
2L-------| 4E-------| 6R-------| 14E-------|
1E---| [] [] [] [] 7E---| 12E---| 15E---|
[] [] [] [] [] [] [] []
Please input. : 0
Rotate left at 2!
Please input. : p
5E-------------------------------|
3L---------------| 8E---------------|
1E-------| 4E-------| 6R-------| 14E-------|
0E---| 2E---| [] [] [] 7E---| 12E---| 15E---|
[] [] [] [] [] [] [] [] [] []
Please input. : 20
Please input. : p
5R---------------------------------------------------------------|
3L-------------------------------| 8R-------------------------------|
1E---------------| 4E---------------| 6R---------------| 14R---------------|
0E-------| 2E-------| [] [] [] 7E-------| 12E-------| 15R-------|
[] [] [] [] [] [] [] [] [] 20E---|
[] []
Please input. : 22
Rotate right at 15!
Please input. : p
5R---------------------------------------------------------------|
3L-------------------------------| 8R-------------------------------|
1E---------------| 4E---------------| 6R---------------| 14R---------------|
0E-------| 2E-------| [] [] [] 7E-------| 12E-------| 20E-------|
[] [] [] [] [] [] [] [] 15E---| 22E---|
[] [] [] []
Please input. : q
$
- のべ16ノードを挿入した木を100回作成（検索の確認は無し（0回））
- のべ10,000,000ノードを挿入した木を作成し、10回検索を実施して各時間を測定
- 計算時間はO(logn)、つまり対数をeとするとlog(10,000,000)=16.118で、これはO(n)と比べると、60万倍以上早い（つまり、数十〜数百msかかる可能性がある）
$ java AVLTree 10000000 10 Found node 7443458 in 11830 ns. Found node 1542990 in 7199 ns. Found node 9059491 in 5348 ns. Found node 2189518 in 5501 ns. Found node 5773482 in 3459 ns. Found node 7512803 in 4832 ns. Found node 7103487 in 6813 ns. Found node 5575799 in 5398 ns. Found node 5292306 in 84161 ns. Found node 8909173 in 20869 ns. $
実装はこちら。削除は複雑なため未実装です。
