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

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

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

 こちらのページ では、 Java によるAVL木の実装を紹介しました。しかし、近年、 プログラミングの初学者に Python を教えるところが増えているそうなので、 Python による実装も用意してみました。 AVL木のアルゴリズムの説明は Java のページ を参照してください。

avlmap.py

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