AVL Tree by Java & Python - これで分かったAVL木

【これで分かったAVL木】 AVL木(AVL Tree)は、 マップ(連想配列)と呼ばれるデータ構造の実装に使われる平衡２分探索木の１つです。 平衡２分探索木では木のバランスが適度にとれており、 キーの検索・要素の挿入・削除などの処理が、いかなる場合でも O(log n) の計算量で行えます(n は要素数)。 何の工夫もしない単なる２分探索木では、 挿入や削除のパターンによっては木の茂り方のバランスが崩れてしまい、 各種操作に O(n) の計算量が必要になる場合があります。 AVL木の他にも 赤黒木 という平衡２分探索木がありますが、 AVL木は赤黒木に比べてより厳密に平衡性を維持しようとします。つまり、 よりバランスがとれているということです。 そのため赤黒木より検索の性能が良いとされています。 かつては、挿入や削除の性能は、 AVL木より赤黒木の方が良いとされていました。しかし、 私の

[oinume]

わかりやすい