二分探索木の用途は何ですか?

二分探索木は主に検索や動的ソートに使用され、二分木の「挿入・問い合わせ・削除」の時間計算量は「O(log(n))」ですが、一般的には使用されません。広告掲載オーダーで使用される「真ん中」は通常それほど正確ではないため、非常に高速です。

バイナリ検索ツリーの役割

私が知っている主な役割は、検索と動的並べ替えです。バイナリ ツリーでの挿入/クエリ/削除の時間計算量は O(log(n)) です。ただし、挿入順序で使用される中間値は通常それほど正確ではないため、実際の使用ではそれほど高速ではありません。特にデータの挿入順序が順序付けされている場合、または基本的に順序付けされている場合、バイナリ ツリーのバランスが著しく崩れます。この場合、リンクされたリストと同じレベルに下がります。

バイナリソートツリーの主な操作は次のとおりです:

1. 検索: キーが存在するかどうかを再帰的に検索します。

2. 挿入: キーは元のツリーに存在しません。キーが挿入された場合は true を返し、そうでない場合は false を返します。

3. 構成: 循環挿入操作。

4. 削除: (1) リーフ ノード: 元のツリーに影響を与えずに直接削除します。

(2) 左または右のサブツリーを持つノードのみ: ノードが削除された後、その左のサブツリーまたは右のサブツリー全体を削除されたノードの位置に移動するだけで、息子が父親の遺産を継承します。

(3) 左右両方のサブツリーを持つノード: 削除する必要があるノード p の直接の先行者または直接の後継者 s を見つけ、ノード p を s に置き換えてから、ノード s を削除します。

以上が二分探索木の用途は何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。