アニメーション|二分探索木とは(擬似コード付き)



Animation What Is Binary Search Tree



青をクリックしてください」5分間の学習アルゴリズム'フォローしてください

'を追加'、毎日正午12:15、一緒にアルゴリズムを学ぶ



ソース|アルゴリズム



二分探索木のプロパティ




多くの二分探索木があり、いくつかは二分探索木と呼ばれ、いくつかは二分探索木、または順序付けられた二分探索木と呼ばれます。次のプロパティを持つ空のツリーまたはバイナリツリーを参照します。

1.いずれかのノードの左側のサブツリーが空でない場合、左側のサブツリーのすべてのノードの値は、そのルートノードの値よりも小さくなります

2.いずれかのノードの右側のサブツリーが空でない場合、右側のサブツリーのすべてのノードの値は、そのルートノードの値よりも大きくなります

3.任意のノードの左右のサブツリーも二分探索木です

4.等しいキー値を持つノードはありません。

検索、挿入、削除の時間計算量はツリーの高さに等しく、期待値はO(logn)であり、最悪の時間計算量はO(n)です。たとえば、ツリーは線形テーブルに縮退します。 。

要素を見つける

二分探索木は、迅速な検索のために生まれ、データの迅速な追加と削除もサポートしています。最初にルートノードと比較する要素を見つけ、チェックする要素がルートノードよりも小さい場合に等しい場合に返す方法、チェックする要素がルートノードよりも大きい場合は、左側のサブツリー再帰検索を実行します、検索の最後に一致する要素がない場合は、サブツリーの右再帰検索を実行します。nullが返されます。

再帰検索

レベルトラバーサル、プレオーダートラバーサル、ミドルオーダートラバーサル、ポストオーダートラバーサルなど、再帰的に検索する方法はたくさんあります。ここでは、最後の3つのトラバーサル方法を引用します。

コード

コードがこのように記述されている場合、そのトラバーサルプロセスはどのようになりますか?以下のアニメーションを参照してください。

アニメーション:プレオーダートラバーサル

(読者の提案に応えて、アニメーションはもはやBGMではありません )。

アニメーション:前面、中央、背面をトラバースします

上記のアニメーションから、中次走査によって取得されたシーケンスは正確に昇順のシーケンスであることがわかります。昇順が考慮されていない場合、順序後のトラバーサルは、バイナリ検索ツリーのメモリを早期に解放し、スタックによって使用されるスペースを早期に削減することもできます。

コード

要素を追加

バイナリツリーで要素を追加および削除するには、リンクリストストレージを使用することをお勧めします。配列ストレージを使用する場合、サブツリーを持つ要素を削除すると、一連の位置が変更されます。要素の位置を入れ替える必要があり、リンクリストよりもパフォーマンスが優れています。小さいの。したがって、後で表示される擬似コードは、リンクリストストレージの形式で操作されます。

コード

要素の削除:最小要素と最大要素を削除します

最小要素と最大要素を削除するのは非常に簡単です。二分木の頂点から始めて最小の要素を削除する場合は、ノードの左の子が空になるまで左の子を再帰的に再帰します。空になると、このノードが最小の要素になります。最大の要素を削除し、ノードの右の子が空になるまでその右の子を再帰的に削除する場合も同様です。

要素を削除します

要素を削除し、この要素に左右のサブツリーがある場合、どのようになりますか?

1962年、HibbardはHibbardDeletionのソリューションを提案しました。

ヒバードの名前を見ると覚えています ヒルソートはHibbardインクリメンタルシーケンスを導入しました 、また、対応する式をコードに反映します。ヒルの並べ替えを実行するためのヒルの増分シーケンスの代わりに、最悪の時間計算量もヒルの増分シーケンスよりも小さくなります。

左と右のサブツリーを持つ要素の削除に戻り、その左と右のサブツリーもバイナリソートツリー(バイナリ検索ツリー)に属していることを考慮してください。左側のサブツリーの最大値はそれよりも小さく、右側のサブツリーの最小値はそれよりも小さくなっています。大きい。したがって、左側のサブツリーの最大値と右側のサブツリーの最小値のどちらを選択し、削除する要素を置き換えても、バイナリツリー全体がバイナリ検索ツリーのルールに準拠します。

アニメーション:要素を削除する

コード:要素を削除します

繰り返される要素を持つ二分探索木をサポートします

二分探索木の規則があります:等しいキー値を持つノードはありません。次に、追加する要素の値が同じノードをスキップし、次のステップで新しいノードが挿入されるまで比較を続けることはお勧めしません。たとえば、23を挿入します。挿入後、上部に23、下部に23があります。その場合、検索は無意味になり、時間計算量のO(logn)が破壊されます。

提案は、ノードに属性を追加することです:count。 23を挿入すると、カウントはそれ自体で計算できます++。これは、キーと値が等しくないという規則を満たすだけでなく、時間計算量の期待値も満たします。

コード

ホットレコメンデーション????

1.1。【【プログラマー私たちは認めなければなりません:この世界には解決できない多くの問題があります

二。【GitHubGitHubでクレイジーなオープンソースプロジェクトを見ました!

3.【アルゴリズムアニメーション:7分でKMPアルゴリズムとは何かを理解する

4.【データ構造10の古典的なソートアルゴリズムのアニメーションと分析、私を見てください!