二分探索木は、要素の挿入、要素の削除、および検索（キーが存在するかどうかのチェック）の三つの主要な操作をサポートしています。

SearchingEdit

特定のキーのバイナリ検索ツリーでの検索は、再帰的または反復的にプログラムすることができます。

ルートノードを調べることから始めます。 ツリーがnullの場合、検索しているキーはツリーに存在しません。 そうでなければ、キーがルートのキーと等しい場合、検索は成功し、ノードを返します。 キーがルートのキーよりも小さい場合は、左のサブツリーを検索します。, 同様に、キーがルートのキーよりも大きい場合は、右のサブツリーを検索します。 この処理は、キーが見つかるか、残りのサブツリーがnullになるまで繰り返されます。 Nullサブツリーに達した後に検索されたキーが見つからない場合、そのキーはツリー内に存在しません。 これは再帰アルゴリズム（Pythonで実装）として簡単に表現されます。

同じアルゴリズムを反復的に実装することができます。

これら二つの例は重複をサポートしていません。

再帰アルゴリズムは末尾再帰的であることに注意することができます。, 言語支援テールの通話による最適化の場合、再帰的な解析例をコンパイルに相当します。

最悪の場合、このアルゴリズムはツリーのルートからルートから最も遠いリーフまで検索する必要があるため、検索操作にはツリーの高さに比例した時間がかかります（ツリー用語を参照）。 平均して、ノードキーを持つバイナリ検索ツリーの高さはO（log|Nodes|）です。 しかし、最悪の場合、バイナリ検索ツリーは、不均衡なツリーがリンクリスト（縮退ツリー）に似ている場合、O（|Nodes|）の高さを持つことができます。,

重複allowedEditを使用した検索

注文関係が合計プリオーダーのみである場合、機能の合理的な拡張は次のとおりです。 これにより、これまでのツリー内のすべての重複の右または左のいずれかに、重複を挿入する方向を指定（またはハードワイヤー）することができます。 方向がハードワイヤーで接続されている場合、右と左の両方の選択肢は、プッシュ操作としてinsert duplicateを使用し、pop操作としてdeleteを使用してスタックをサポート,:155

このような検索機能を備えた二分木ソートが安定になります。

InsertionEdit

検索が開始されると挿入が開始されます。キーがルートのキーと等しくない場合は、前と同じように左または右のサブツリーを検索します。 最終的に、外部ノードに到達し、ノードのキーに応じて、新しいキーと値のペア（ここではレコード’newNode’としてエンコードされます）を右または左の子として追加します。, 言い換えれば、ルートを調べ、そのキーがルートのキーよりも小さい場合は左のサブツリーに新しいノードを再帰的に挿入し、そのキーがルート以上の場合は右のサブツリーに挿入します。

c++のバイナリツリーで典型的なバイナリ検索ツリー挿入がどのように実行されるかは次のとおりです。

あるいは、非再帰バージョンは次のように実装されるかもしれません。, どこから来たのかを追跡するためにポインタツーポインタを使用すると、コードはツリーのルートにノードを挿入する必要がある場合の明示的なチェックと処理を避けることができます。

上記の破壊的な手続き型バリアントは、ツリーを所定の位置に変更します。 定数ヒープ領域のみを使用します（反復バージョンでは定数スタック領域も使用します）が、以前のバージョンのツリーは失われます。, あるいは、次のPythonの例のように、挿入されたノードのすべての祖先を再構築することもできます。元のツリールートへの参照は有効なままで、ツリーを永続的なデータ構造にします。

再構築される部分は、平均的な場合にはO(log n)スペースを使用し、最悪の場合にはO(n)を使用します。

どちらのバージョンでも、この操作は最悪の場合にはツリーの高さに比例する時間を必要とします。,

挿入を説明するもう一つの方法は、ツリーに新しいノードを挿入するために、そのキーが最初にルートのキーと比較されることです。 そのキーがルートのキーよりも小さい場合は、ルートの左の子のキーと比較されます。 そのキーが大きい場合は、ルートの右側の子と比較されます。 このプロセスは、新しいノードがリーフノードと比較され、そのキーに応じてこのノードの右または左の子として追加されるまで続きます。キーがリーフのキーよりも小さい場合は、リーフの左の子として挿入され、そうでない場合はリーフの右の子として挿入されます。,

ノードをバイナリツリーに挿入する方法は他にもありますが、これは葉にノードを挿入する唯一の方法であり、同時にBST構造を保持します。

DeletionEdit

バイナリ検索ツリーからノードを削除するときは、ノードの順序の順序を維持することが必須です。 これを行うには多くの可能性があります。 しかし、1962年にT.Hibbardによって提案された以下の方法は、対象部分木の高さが最大で一つだけ変化することを保証する。, /P>

• 子を持たないノードを削除する：ツリーからノードを削除するだけです。
• 一つの子を持つノードを削除する：ノードを削除し、その子に置き換えます。
• 二つの子を持つノードDを削除する:Dの順序付きの先行ノードまたは順序付きの後続ノードEを選択します(図参照)。 Dを削除する代わりに、そのキーと値をeで上書きします。Eに子がない場合は、前の親GからEを削除します。Eに子Fがある場合、それは正しい子であるため、eの親でEを置き換えることになります。Eのキーと値をeで上書きします。,li>

すべての場合において、Dがたまたまルートである場合は、置換ノードrootを再度作ります。

二つの子を持つノードは削除するのが難しくなります。, ノードの順序内の後続は、その右側のサブツリーの左端の子であり、ノードの順序内の先行は、左側のサブツリーの右端の子です。 いずれの場合も、このノードは子を一つだけ持つか、まったく持ちません。 上記の二つの簡単なケースのいずれかに従って削除します。

二子ケースのすべてのインスタンスに対して順序付き後継者または順序付き先行を一貫して使用すると、不均衡なツリーにつながる可能性があるため、実装によっては異なる時間にどちらか一方を選択する場合があります。,

ランタイム分析：この操作は常にツリーをトラバースしてリーフに至るわけではありませんが、これは常に可能性があるため、最悪の場合はツリーの高さに比例した時間が必要になります。 それはまだ単一のパスをたどり、二度どのノードを訪問しないので、ノードが二人の子を持っている場合でも、より多くを必要としません。,

TraversalEdit

バイナリサーチツリーが作成されると、ルートノードの左サブツリーを再帰的にトラバースし、ノード自体にアクセスし、ノードの右サブツリーを再帰的にトラバースし、ツリー内の各ノードに対して再帰的にアクセスすることによって、その要素を順番に取得できるようになる。 すべての二分木と同様に、順序前走行または順序後走行を行うことができますが、二分木探索にはどちらも有用ではない可能性があります。, バイナリ検索ツリーの順序通りのトラバーサルは、常にノード項目（数字、文字列、またはその他の同等の項目）のソートされたリストになります。

Pythonで順番にトラバーサルするためのコードを以下に示します。 これは、ツリー内のすべてのノードに対してcallback（プログラマが画面に印刷するなど、ノードの値に対して呼び出したい関数）を呼び出します。

トラバーサルは、すべてのノードを訪問する必要があるため、O（n）時間が必要です。 このアルゴリズムもO（n）であるため、漸近的に最適です。

トラバーサルは反復的に実装することもできます。 ある特定の適用のため、例えば, より大きな等しい検索、近似検索、単一ステップ（反復）トラバーサルの操作は非常に便利です。 もちろん、これはコールバック構造なしで実装されており、平均してO（1）を、最悪の場合はO（log n）を取ります。

VerificationEdit

時にはバイナリツリーが既にあり、それがBSTであるかどうかを判断する必要があります。 この問題には単純な再帰的な解決策があります。,

BSTプロパティ—右側のサブツリーのすべてのノードは現在のノードよりも大きくなければならず、左側のサブツリーのすべてのノードは現在のノードよりも小さくなければならない—は、ツリーがBSTであるかどうかを判断するための鍵である。 貪欲なアルゴリズム—単にツリーをトラバースし、すべてのノードで、ノードに左の子の値より大きく、右の子の値より小さい値が含まれているかどうかをチェックします—すべてのケースで機能しません。, 次のツリーを考えてみましょう。

 20 / \ 10 30 / \ 5 40

上のツリーでは、各ノードは、ノードの左の子よりも大きく、右の子ホールドよりも小さい値を含むが、BSTではないという条件を満たしています。値5は、20を含むノードの右側のサブツリーにあり、BSTプロパティに違反しています。

ノードとその子の値だけに基づいて決定を下すのではなく、親からも流れる情報も必要です。, 上記のツリーの場合、値20を含むノードについて覚えておくことができれば、値5のノードがBSTプロパティ契約に違反していることがわかります。,

各ノードでチェックする必要がある条件は次のとおりです。

• ノードが親の左の子である場合、親よりも小さくなければならず、親から右のサブツリーに値を渡して、そのサブツリー内のノードのどれもが親よりも大きくないことを確認する必要があります。
• ノードが親の右の子である場合、親よりも大きくなければならず、親から左のサブツリーに値を渡す必要があります。そのサブツリー内のどのノードも親よりも小さくないことを確認してください。,p>

  node->key+1およびnode->key-1bstの異なる要素のみを許可するように行われます。

  同じ要素も存在させたい場合は、両方の場所でnode->keyのみを使用できます。

  この関数の最初の呼び出しは次のようになります。

  if (isBST(root, INT_MIN, INT_MAX)) { puts("This is a BST.");} else { puts("This is NOT a BST!");}

  基本的に有効な範囲を作成し続け、再帰的にダウンするにつれて各ノード,

  セクション#Traversalで指摘されているように、二分探索木の順序内トラバーサルは、ソートされたノードを返します。 したがって、ツリーをトラバースしながら最後に訪問したノードを保持し、そのキーが現在のキーと比較して小さい（またはツリー内で重複が許可されている場合

  Parallel algorithmsEdit

  複数の要素の挿入/削除、配列からの構築、特定の予測子によるフィルタリング、配列への平ten化、二つのツリーのマージ/substracting/交差など、バイナリサーチツリーの並列アルゴリズムもあります。, これらのアルゴリズムは、結合ベースのツリーアルゴリズムを使用して実装することができ、いくつかのバランススキーム（AVLツリー、赤-黒ツリー、重み均衡ツリー、treapを含む）を使用してツリー