二分探索木のクイックガイド

1. 概要

このチュートリアルでは、二分探索木（BST）のデータ構造について説明します。

最初に、BSTがどのように機能し、いつ使用するかについての概要から始め、次に、ルックアップ、挿入、およびトラバーサルの基本的な操作を実装します。

簡単に言えば、バイナリ検索ツリーは、アイテムの迅速な挿入、削除、検索を可能にすると同時に、並べ替えられた順序でアイテムを反復する効率的な方法を提供するデータ構造です。

これらの理由から、要素の順序を維持しながらコレクションにアクセスまたは変更する効率的な方法が必要な場合は、バイナリ検索ツリーを使用します。

単純な二分木とは対照的に、二分探索木の基本的な特徴は、二分探索特性を満たすことです。このプロパティは、各ノードのの値は、右側のサブツリーの値よりも小さく、左側のサブツリーの値よりも大きくなければならないことを示しています：

その結果、ルックアップ、挿入、および削除の操作は複雑になります。これは、ツリーをルートからリーフにトラバースするときに、入力値が現在のノードの値よりも大きいか小さいかに応じて、各ステップでツリーの半分を破棄できるためです。

たとえば、左側のツリーに値9が含まれているかどうかを確認する場合、9は8より大きいため、ルートノードの右側のサブツリーを調べるだけでよいことはすでにわかっています。ルートの。

二分探索木のルックアップは、ルートからツリーを下にトラバースし、各ステップで、右または左に移動して続行するかどうかを選択することによって実行されます。値または現在の値が見つかるまで、このプロセスを繰り返します。ノードに右/左の子がありません。

これは、再帰を使用した実装です。

ツリーに要素を挿入するとき、ツリーはまだ二分探索特性を満たさなければならないため、最初にそれを配置する正しい位置を見つける必要があります。

アルゴリズムは最終的にルックアップ操作と非常に似ていますが、現在のノードに子がない場合に false を返す代わりに、新しいノードを作成する点が異なります。

ツリーは非線形データ構造です。つまり、ツリーの要素の順序はデフォルトでは定義されていません。代わりに、さまざまなトラバーサルアルゴリズムを使用して、さまざまな順序でその要素にアクセスできます。

深さ優先の順序どおりのトラバーサルを実行するだけでよいため、要素を昇順で取得することは、BSTのコンテキストで簡単に実装できます。

逆に、降順で要素にアクセスする場合は、逆順トラバーサルを使用する必要があります。これを行うには、右側のサブツリーで深さ優先探索を開始します。実際には、アルゴリズムへの参照とアルゴリズム内の参照を反転する必要があります。

ツリーにはノードがあり、各ノードは1回しかアクセスされないため、この操作には時間計算量があります。

この簡単な記事では、二分探索木がどのように機能するか、そしてなぜそれらが非常に役立つのかについての基本を探りました。

また、要素を見つけて挿入する方法、および深さ優先順方向または逆順順トラバーサルを使用して昇順または降順で要素を印刷する方法についても説明しました。