文字列を含む二分探索木

1. 概要

このチュートリアルでは、二分探索木（BST）データ構造について、ノード内のキーが文字列で表されるの場合に焦点を当てて説明します。

2. 序章

BST は、バイナリツリーであり、すべてのノードで次のプロパティを満たします。

• ノードの左側のサブツリーには、ノードのキーよりも小さいキーを持つノードのみが含まれています
• ノードの右側のサブツリーには、ノードのキーよりも大きいキーを持つノードのみが含まれています
• 左右のサブツリーもそれぞれ二分探索木でなければなりません。

この記事では、ノードのキーが数字ではなく文字列で表される場合に焦点を当てます。この場合、最初に文字列の順序を定義する必要があります。

辞書式順序は、辞書に表示される各文字列の順序として定義されます。 辞書式順序で大きい文字列を判別するために、2つの文字列の対応する文字を左から右に比較します。 2つの文字列が異なる最初の文字によって、どちらの文字列が最初に来るかが決まります。 文字はUnicode文字セットを使用して比較され、すべての大文字は小文字の前に配置されます。

例えば：

• リンゴ<オレンジ「a」は「o」の前にあるため
• オレンジ>オレンジ「O」は「o」の後に続くため
• apple = appleすべての文字が同じであるため、

文字列を持つ2つの二分木を見てみましょう。

左側のツリーは上記の基準を満たしているためBSTですが、右側のツリーは赤いノードでは基準が失敗しているためBSTではありません。 「Watson」は辞書式順序で「John」よりも大きく、「Chris」は辞書式順序で「John」よりも小さいです。

3. 基本操作

名前が示すように、文字列を使用するBSTで最も頻繁に実行される操作は、特定の文字列を検索することです。ルートから開始して、要求された文字列が見つかるまで下向きのパスをたどります。

遭遇したノードごとに、要求された文字列をノードの文字列と辞書式に比較します。 の場合、BSTプロパティは右側のサブツリーに格納できなかったことを意味するため、左側のサブツリーで検索を続行します。 対称的に、適切なサブツリーを検索すると。 手順全体は、上記の擬似コードに要約されています。

削除のプロセスは少し複雑です。 3つのケースがあります：

• ノードに子がない場合は、単に削除します
• ノードに子が1つしかない場合は、ノードをその子に置き換えます
• ノードに2つの子がある場合、右側のサブツリーにあり、左側の子がない後続ノードが見つかります。 次に、ノードを後続ノードに置き換えます

擬似コードを見てみましょう：

二分探索木内でサブツリーを移動するために、サブルーチンTRANSPLANTを定義します。これは、あるサブツリーをその親の子として別のサブツリーに置き換えます。 TRANSPLANTが、ノードをルートとするサブツリーをノードをルートとするサブツリーに置き換えると、ノードの親はノードの親になり、の親は最終的に適切な子になります。

TRANSPLANT関数の擬似コードは次のとおりです。

4. 複雑さの分析

BST検索では、挿入と削除は時間内に実行されます。ここで、はツリーの高さです。

5. 結論

この記事では、文字列をキーとして含むBSTの基本的な操作について説明しました。