バランスの取れたバイナリ ツリーとソートされたバイナリ ツリーの関係

バランス二分木と二分ソート木の間に直接の関係はありませんが、二分ソート木の検索効率は二分木の形状に関係します。このように均一であること 二分木はバランス二分木と呼ばれます。

1. バイナリソートツリー

バイナリ ソート ツリー、

バイナリ検索ツリー (バイナリ検索ツリー)、バイナリ検索ツリーとも呼ばれます。

• バイナリ ソート ツリーの定義:

バイナリ ソート ツリーは、空のツリーであるか、次のプロパティを持つバイナリ ツリーです。

左のサブツリーが空でない場合、左のサブツリー上のすべてのノードの値はそのルート ノードの値より小さくなります。
1. 右のサブツリーが空でない場合は、空でない場合、右のサブツリー上のすべてのノードの値がそのルート ノードの値より大きい;
2. 左と右のサブツリーもそれぞれバイナリ ソート ツリーです。

下の図に示すように、これはバイナリ ソート ツリーです。

バイナリ ソート ツリーで順序トラバーサルを実行して、キーワード シーケンスでソートされた結果を取得します。たとえば、上図を順番に走査すると、順序付けられたシーケンス 10、42、45、55、58、63、67、70、83、90、98

を取得できます。 #バイナリ ソート ツリーの検索分析
検索の平均時間パフォーマンスの観点からは、バイナリ ソート ツリーでの検索はハーフ検索と似ていますが、テーブルの順序性 効率の点では、バイナリ ソート ツリーの方が効率的です。これは、ノードを移動する必要がなく、ポインタを変更するだけでバイナリ ソート ツリーの挿入および削除操作を完了できるためです。

バイナリソートツリー検索 最悪の場合、必要な検索時間はツリーの

深さに依存します

:

1. バイナリソートツリーがフルバイナリツリーに近い場合、その深さは$\#\#l\#\#です。\mathrm{\#o}g{2}_{\mathrm{}}log\_2n$n log_2n$l\#o{}_{\mathrm{}}\#\#2$

以上がバランスの取れたバイナリ ツリーとソートされたバイナリ ツリーの関係の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。