C++, Java, Pythonにおける赤黒木の実装

はじめに

赤黒木は平衡二分木の一種で、探索・挿入・削除の時間計算量がO(log n)である。この記事では、C++, Java, Pythonでそれぞれどのように利用するかをメモしておく。

C++

std::mapを使えばOK。
https://en.cppreference.com/w/cpp/container/map

Java

java.util.TreeMapを使えばOK。
https://docs.oracle.com/javase/jp/1.4/api/java/util/TreeMap.html

Python

組み込み型であるdictはハッシュテーブルで実装されているようです。
https://docs.python.org/ja/3/library/stdtypes.html?highlight=dict#mapping-types-dict
https://stackoverflow.com/questions/327311/how-are-pythons-built-in-dictionaries-implemented
https://softwareengineering.stackexchange.com/questions/234793/why-does-python-use-hash-table-to-implement-dict-but-not-red-black-tree

赤黒木を利用したい場合は以下のライブラリを用いると良さそうです。
https://pypi.org/project/bintrees/

記事情報

• 投稿日：2021年8月21日
• 最終更新日：2021年8月21日