1. 概要

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

2. 序章

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

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

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

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

例えば:

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

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

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

3. 基本操作

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

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

その他の便利な操作は、BSTから特定の文字列を挿入または削除することです。 この変更を反映するようにデータ構造を変更する必要がありますが、binary-search-treeプロパティが引き続き保持されるようにします。 新しい文字列を挿入する場合、基本的にBST-Searchメソッドを使用してツリー内の文字列を検索します。 NULLポインターに到達すると(文字列がツリーに存在しないため)、入力文字列を含むノードを挿入します。

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

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

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

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

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

4. 複雑さの分析

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

5. 結論

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