python - Pythonのビルトイン二分探索木?

Question

Python 2.7 または Python 3.x に組み込まれている自己平衡二分探索木( RED-BLACK、AVLなど) はありますか?

Java のTreeMapまたはTreeSetに相当するものを探しています。

そのようなビルトインがない場合、なぜ省略されたのでしょうか? そのようなツールを含めない特別な理由はありますか?

Answer 1

私の知る限り、特別な理由はありません。その理由は、非常に多くのアプリケーションで、高度に調整されたdict実装set(ハッシュ テーブル) がうまく機能するためだと思います。ほとんどの場合、それらで十分です。バランスの取れた二分探索木のパフォーマンス特性 (加算順ではなくキーに基づく順序付けされたトラバーサルなど) が必要な状況は確かにありますが、それらは、人々がサードパーティのパッケージを手に入れることに満足しているほど、人里離れた道からはほど遠いものです。その場合。

PyPI でbintreesパッケージを使用して、良い経験をしました。これには、純粋な Python とCythonで記述された拡張機能の両方で、アンバランスな AVL および赤黒のバイナリ ツリーが実装されています。

残りの理由は本質的に歴史的な事故だと思います。bintrees を書いた人が stdlib に含めるよう働きかけ、メンテナンスとリリースに課す制約を喜んで我慢するなら、おそらく入ってくるでしょう。 .)

アルゴリズムの複雑さ:

ハッシュ テーブル (ディクテーションやセットなど) の場合、挿入とルックアップは O(1) ですが、バランス ツリーの場合は O(log(n)) です。キーの順序通りのトラバーサルはツリーでは O(n) ですが、ハッシュ テーブルで同じことを行うには、最初にキーを並べ替える必要があるため、O(n*log(n)) になります。使用するデータ構造の種類を選択するときは、使用する操作について検討し、アプリケーションで最も意味のあるトレードオフを選択する必要があります。

Answer 2

標準ライブラリにはツリーがありません。Python は、その内部にハッシュ テーブルであるディクショナリを多用します (オブジェクト、クラス、およびモジュールはすべてディクショナリに基づいています)。したがって、dicts は大幅に最適化されています。これにより、検索ツリーの必要性がはるかに小さくなります。また、効率的にするために、そのようなツリーは拡張タイプで実装されます。