90

Pythonの標準ライブラリにAVLツリー、赤黒木、またはその他のタイプの平衡二分木用のモジュールはありますか？

4

7 に答える 7

54

いいえ、stdlib にはバランスの取れたバイナリ ツリーはありません。ただし、コメントから、他にもいくつかのオプションがあるように思えます。

  • O(log n)あなたは、検索用のリストではなく BST が必要だと言っています。検索だけが必要で、データが既にソートされている場合、bisectモジュールはリストのバイナリ検索アルゴリズムを提供します。
  • Mike DeSimone が set と dicts を推奨し、リストがアルゴリズム的に遅すぎる理由を説明しました。セットとディクテーションは、O(1) ルックアップを持つハッシュ テーブルとして実装されます。Python のほとんどの問題の解決策は、実際には「dict を使用する」ことです。

どちらのソリューションもうまくいかない場合は、サード パーティのモジュールを使用するか、独自のモジュールを実装する必要があります。

于 2010-02-19T17:26:14.353 に答える
15

私が見る限り、stdlibにはこの種のものはありませんが、pypiをざっと見ると、いくつかの選択肢があります。

于 2010-02-19T17:10:56.690 に答える
11

heapq パッケージ(標準ライブラリ内) が役立つことがわかった例がいくつかあります。特に、コレクション内の最小要素への O(1) アクセス時間が必要な場合は特にそうです。

私にとっては、タイマーのコレクションを追跡していて、通常は最小の時間 (最初に実行される時間) がまだ準備できているかどうかを確認することに関心がありました。

于 2010-02-22T06:13:18.123 に答える
8

Sorted Containersプロジェクトもチェックしてください。

これについての PyCon の話は次のとおりです: https://www.youtube.com/watch?v=7z2Ki44Vs4E

于 2018-02-25T19:41:03.260 に答える
6

ubalanced、AVL、および RB ツリーをサポートする「bintrees」と呼ばれる新しいパッケージがあります。ここで見つけることができます。

于 2011-05-21T11:56:56.193 に答える
3

いいえ。ただし、Python用のAVLツリーオブジェクト（非常に古い！）とSourceForgeの（クローズド）プロジェクト（Python用のavl-trees ）があります。

于 2010-02-19T17:13:45.763 に答える