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