1

私はインタビューのために木のバランスをとる方法を研究し始めています、そして私はいくつかの質問があります

  • 通常の二分木のバランスを取ることは可能ですか？はいの場合、どのアルゴリズムを使用する必要がありますか？
  • バランスの取れたツリーを取得するには、必ずAVLまたは赤黒木を使用する必要がありますか？これらはどのように機能しますか？これらをできるだけ簡単に説明するリンクを提供できますか？

回転やウェイトについて何か読んだのですが、今はちょっと混乱しています

4

2 に答える 2

2

ええと... AVL と赤黒木は、バランスのとれた「通常のバイナリ ツリー」であり、そのバランスを維持します (「バランスのとれた」の定義について)。私はコンピューター サイエンスの教師であり、アルゴリズムの独自の説明を考え出すつもりはありません。また、ウィキペディアからのカット アンド ペーストを探しているわけでもないと思います :-)

ここで、バイナリ ツリーのバランスをとります。ツリーが検索ツリーである場合 (つまり、「並べ替えられている」が、そうでない場合は「バランスが取れている」という意味がありません)、いつでもツリーを再作成できます。最も単純なアルゴリズムは、ツリーのすべての要素を並べ替えた順序で配列を使用することです (インオーダー トラバーサルから簡単に取得できます)。次に、この一般的なアイデアに基づいてアルゴリズムを構築します。

  • 配列の中央の要素をツリーのルートとして取得します。これにより、ツリー ノードと、左右のサブツリーを形成するための 2 つの配列 "left" と "right" が作成されます。
  • この同じアルゴリズムを再帰的に適用して、「左」配列からツリーを作成し、「右」配列からツリーを作成します。これらの 2 つのツリーは、親ノードの子になります。

配列の要素数が偶数の場合は、注意が必要な場合があります。明らかな「中間要素」はなく、2 つの候補のいずれかを削除すると、異なるサイズの配列が作成されます。これをさらに分析して、バランス調整全体を相殺できるかどうかを確認するのは面倒です。

もちろん、ツリーを変更するたびにこのようなことを行うのは、あまり良い考えではありません。そのためには、AVL のような自己均衡ツリーを本当に使用したいと考えています。ツリーを作成した後にそれを行うことも、それほど有用ではないかもしれません。ツリーを作成する代わりに、配列自体を使用して、それに対してバイナリ検索を実行することもできます。配列は二分木の単なる別の形式です...

編集: 多くのコンピューター科学者が、特定の状況でうまく機能するデータ構造とアルゴリズムの開発に多くの時間を費やしてきたのには理由があります。バランスの取れたバイナリ ツリーの独自のバージョンを作成しても、これらに勝るものはありません...

于 2012-08-18T15:20:00.293 に答える
2

通常の二分木のバランスを取ることは可能ですか? はいの場合、どのアルゴリズムを使用する必要がありますか?

では、完全なツリーを構築し、要素を順にトラバーサルO(n)で移入できます。

まれに、BST がチェーン (リンクされたリスト) に崩壊し、すべてのノードが 1 つの子をヌルとして持つため、これ以上のことはできません。この場合、途中の要素へのアクセスはO(n)それ自体です。

バランスの取れたツリーを取得するには、必ず AVL または赤黒ツリーを使用する必要がありますか?

B+ ツリーなどの他のバランス ツリーや、スキップ リストなどの他のデータ構造 (ツリーではない) があります。既知のデータ構造のリスト、特にツリー セクションを参照することをお勧めします。

これらはどのように機能しますか？これらをできるだけ簡単に説明するリンクを提供できますか?

AVLツリーとRed-Blackツリーの両方に関するウィキペディアの記事は非常に有益です。そこでわからないことがある場合は、質問する必要があります。

また、バランスの取れたツリーを独自に実装しようとする(もちろん、新しいツリーを発明するのではなく、既知のツリーを実装します) - 教育目的に最適です。そうすることで、それがどのように機能するかを確実に理解できます。

于 2012-08-18T15:20:22.433 に答える