トップページ   関連リンク: これで分かったAVL木   Python による赤黒木   おすすめリンク: Stockham FFT アルゴリズムの解説  

AVL Tree by Python -- Python によるAVL木

 このページは、 マップ(連想配列)と呼ばれるデータ構造の実装の1つであるAVL木(AVL Tree)の Python による実装を紹介するページです。 AVL木は、要素の挿入・削除・検索などの操作が、 いかなる場合でも O(log n) の計算量で実行出来る平衡2分探索木です(n は要素数)。 何の工夫もしない単なる2分探索木では、 挿入や削除のパターンによっては木の茂り方のバランスが崩れてしまい、 各種操作に O(n) の計算量が必要になる場合があります。


トップページ   関連リンク: これで分かったAVL木   Python による赤黒木   おすすめリンク: Stockham FFT アルゴリズムの解説