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

Red-Black Tree by Python -- Python による赤黒木

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

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

rbmap.py

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