スレッドバイナリツリー

コンピューティングにおいて、スレッド化されたバイナリツリーは、特定の順序でのトラバーサルを容易にするバイナリツリーのバリエーションです。

バイナリ検索ツリー全体をメインキーの順に簡単にトラバースできますが、ノードへのポインターのみが与えられた場合、次のノードを見つけるのに時間がかかるか、不可能になることがあります。たとえば、定義によりリーフノードには子孫がないため、リーフノードへのポインターのみが与えられた場合、他のノードに到達することはできません。スレッド化されたツリーは、一部またはすべてのノードに追加情報を追加するため、任意の単一のノードに対して「次の」ノードをすばやく見つけることができ、再帰なしでツリーをトラバースでき、再帰に必要な追加のストレージ (ツリーの深さに比例) も不要になります。

スレッド

「バイナリツリーは、通常ヌルであるすべての右側の子ポインタをノードの順序どおりの後続ノード（存在する場合）にポイントし、通常ヌルであるすべての左側の子ポインタをノードの順序どおりの前続ノードにポイントすることによってスレッド化されます。」^[1]

これは、トラバース順序がツリーのインオーダートラバースと同じであることを前提としています。ただし、ポインターを置き換えるのではなく、代わりに (または追加で) ツリーノードに追加することができます。このように定義されたリンクリストは一般に「スレッド」とも呼ばれ、任意の順序でトラバースできるようにするために使用できます。たとえば、ノードが人に関する情報を表すツリーは名前でソートされますが、追加のスレッドを使用して、生年月日、体重、またはその他の既知の特性の順序ですばやくトラバースすることができます。

モチベーション

ツリー (バイナリサーチツリーを含むが、これに限定されない) は、各ノードに格納されているプロパティの値(キーと呼ばれることが多い) などの項目を特定の順序で格納するために使用できます。このようなツリーで役立つ操作の 1 つは、トラバーサル (キーの順序ですべての項目を参照する操作) です。

バイナリ検索ツリーの各ノードを訪問する単純な再帰的トラバーサルアルゴリズムは次のとおりです。 $t$ はノードへのポインター、または $nil であると仮定します。$ $t$ を「訪問する」とは、ノード $t$ またはそのコンテンツに対して任意のアクションを実行することを意味します。

アルゴリズム traverse( $t$ ):

入力:ノードへのポインタ $t (または$ $nil$ )
$t = nil$ の場合は戻ります。
それ以外：
- トラバース(左の子( $t$ ))
- 訪問 $t$
- トラバース(右の子( $t$ ))

このアルゴリズムの問題点は、再帰のため、ツリーの高さに比例してスタック領域を使用することです。ツリーのバランスがかなり取れている場合、これは $n$ 個の要素を含むツリーに対して $O (log n) の$ 領域になります。最悪の場合、ツリーがチェーンの形をとると、ツリーの高さは $n$ になるため、アルゴリズムは $O$ $($ $n$ $) の$ 領域を使用します。2 つ目の問題は、ノードが子へのポインターのみを持つ場合、すべてのトラバーサルをルートから開始する必要があることです。特定のノードへのポインターを持つことは一般的ですが、スレッドポインターなどの追加情報を追加しない限り、それだけではツリーの残りの部分に戻るのに十分ではありません。

このアプローチでは、特定のノードの左および/または右のポインタが実際に子を指しているかどうか、またはスレッドの結果であるかどうかを判断できない場合があります。区別が必要な場合は、各ノードに 1 ビットを追加するだけで、それを記録できます。

1968年の教科書で、ドナルド・クヌースは、スタックを使用せず、ツリーを変更せずに、順序どおりにトラバーサルを行う非再帰アルゴリズムが存在するかどうかを尋ねました。^[2]この問題の解決策の1つは、1979年にジョセフ・M・モリスによって発表されたツリースレッドです。 ^[3]^[4] 1969年のフォローアップ版で、^{[5]クヌースはスレッド化されたツリー表現を}パーリスとソーントン（1960）に帰しました。 ^[6]

親ポインタとの関係

同様の目標を達成する別の方法は、各ノードにそのノードの親ノードへのポインターを含めることです。これにより、「次の」ノードには常に到達できますが、「右」ポインターは、右の子がない場合は null のままです。右ポインターが null のノードから「次の」ノードを見つけるには、「親」ポインターをたどって、右ポインターが null ではなく、先ほどまでいた子ではないノードに到達します。そのノードが「次の」ノードであり、その右側に子孫が続きます。

遅くはなりますが、親ポインタやスタックを明示的に使用せずに、スレッド化されたバイナリツリーからノードの親を検出することも可能です。これを確認するには、右の子rを持つノードkについて考えます。この場合、 rの左ポインタは、子であるか、 kに戻るスレッドである必要があります。 rに左の子がある場合、その左の子は、それ自身の左の子またはkに戻るスレッドを持っている必要があり、後続の左の子すべてについて同様に続きます。したがって、rからの左ポインタのチェーンをたどることで、最終的にkに戻るスレッドが見つかります。 q がpの左の子である場合も状況は対称的に同様です。つまり、 qの右の子をたどって、 pを指すスレッドにたどり着くことができます。

Python の場合:

def  parent ( node ):
    ノードがnode . tree . root の場合 : Noneを返しますx = node y = node Trueの場合: is_thread ( y ): p = y . right pがNoneまたはp . leftがnodeでない場合: p = xの場合is_thread ( p . left )でない場合: p = p . left p = p . left pを返しますelif is_thread ( x ): p = x . left pがNoneまたはp . rightがnodeでない場合: p = yの場合is_thread ( p . right )でない場合: p = p . right p = p . right pを返しますx = x . left y = y . right

種類

シングルスレッド: 各ノードは、順序どおりに先行ノードまたは後続ノード (左または右) に向かってスレッド化されます。
ダブルスレッド: 各ノードは、順序どおりに先行ノードと後続ノード (左と右) の両方にスレッド化されます。

順序走査の配列

スレッドは、インオーダートラバーサルに従ってノードの前身と後続のノードを参照します。

スレッドツリーの順序どおりのA,B,C,D,E,F,G,H,Iトラバーサルは、の前身EはD、の後身はEですF。

例

通常のバイナリツリーからスレッドバイナリツリーを作成しましょう。

上記のツリーの順序付き走査は DBAE C です。したがって、それぞれのスレッドバイナリツリーは次のようになります。

ヌルリンク

n個のノードを持つm方向のスレッドバイナリツリーには、 n × m − ( n −1)個の空リンクがあります。

参考文献

^ Van Wyk, Christopher J. Data Structures and C Programs 、Addison - Wesley、1988年、p.175。ISBN 978-0-201-16116-8 。
^ Knuth, DE (1968).基本的なアルゴリズム. コンピュータプログラミングの芸術. 第 1 巻 (第 1 版). 読書/MA: Addison Wesley.
^ Morris, Joseph H. (1979). 「バイナリツリーを簡単かつ安価にトラバースする」. Information Processing Letters . 9 (5). doi :10.1016/0020-0190(79)90068-1.
^ Mateti, Prabhaker; Manghirmalani, Ravi (1988). 「Morris のツリー走査アルゴリズムの再考」.コンピュータプログラミングの科学. 11 : 29–43. doi :10.1016/0167-6423(88)90063-9.
^ Knuth, DE (1969).基本的なアルゴリズム. コンピュータプログラミングの芸術. 第 1 巻 (第 2 版). Addison Wesley.Hre: セクション 2.3.1「バイナリツリーのトラバース」。
^ Perlis, Alan Jay; Thornton, C. (1960年4月). 「スレッドリストによるシンボル操作」. Communications of the ACM . 3 (4): 195–204. doi : 10.1145/367177.367202 .

外部リンク

GNU libavl 2.0.2、スレッド化されたバイナリ検索ツリーのセクション

[1] Van Wyk, Christopher J. Data Structures and C Programs 、Addison - Wesley、1988年、p.175。ISBN 978-0-201-16116-8 。

[2] Knuth, DE (1968).基本的なアルゴリズム. コンピュータプログラミングの芸術. 第 1 巻 (第 1 版). 読書/MA: Addison Wesley.

[3] Morris, Joseph H. (1979). 「バイナリツリーを簡単かつ安価にトラバースする」. Information Processing Letters . 9 (5). doi :10.1016/0020-0190(79)90068-1.

[4] Mateti, Prabhaker; Manghirmalani, Ravi (1988). 「Morris のツリー走査アルゴリズムの再考」.コンピュータプログラミングの科学. 11 : 29–43. doi :10.1016/0167-6423(88)90063-9.

[5] Knuth, DE (1969).基本的なアルゴリズム. コンピュータプログラミングの芸術. 第 1 巻 (第 2 版). Addison Wesley.Hre: セクション 2.3.1「バイナリツリーのトラバース」。

[6] Perlis, Alan Jay; Thornton, C. (1960年4月). 「スレッドリストによるシンボル操作」. Communications of the ACM . 3 (4): 195–204. doi : 10.1145/367177.367202 .