二分探索木とは何ですか

二分探索木は、二分探索木または二分ソート ツリーとも呼ばれます。二分探索木は二分木として編成され、各ノードがオブジェクトであるリンク リスト データ構造で表すことができます。一般に、 、キー データとサテライト データに加えて、各ノードには属性 lchild、rchild、parent も含まれます。

二分探索ツリー (バイナリ検索ツリー)、(別名: 二分探索ツリー、二分ソート ツリー) 空のツリーか、バイナリ ツリーです。次のプロパティを持ちます: 左のサブツリーが空でない場合、左のサブツリー上のすべてのノードの値はルート ノードの値より小さくなります; 右のサブツリーが空でない場合、すべてのノードの値は右側のサブツリーのノードはルート ノードの値より小さく、すべてのノードの値はルート ノードの値より大きく、左側と右側のサブツリーもそれぞれバイナリ ソート ツリーです。二分探索木は古典的なデータ構造であり、連結リストの挿入・削除操作が高速であるという特徴と、配列の検索が高速であるという利点があるため、ファイルシステムやデータベースなどで広く使用されています。データ構造は、効率的な並べ替えおよび検索操作を実行します。

原理

二分探索木 (BST) は、二分探索木または二分ソート ツリーとも呼ばれます。二分探索木は二分木として編成され、各ノードがオブジェクトであるリンク リスト データ構造で表すことができます。一般に、各ノードには、キー データとサテライト データに加えて、lchild、rchild、parent という属性も含まれており、それぞれノードの左の子、右の子、親 (親ノード) を指します。子ノードまたは親ノードが存在しない場合、対応する属性の値は NIL になります。ルート ノードは、親ポインタが NIL であるツリー内の唯一のノードであり、リーフ ノードの子ノード ポインタも NIL です。

構造

二分探索木は、以下の操作を効率的に実行できるデータ構造です。

1. 値の挿入

2. 特定の値が含まれているかどうかの問い合わせ

3. 特定の値の削除

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