三分木

コンピュータ サイエンスでは、三分木は各ノードが最大 3 つの子ノードを持つツリー データ構造であり、通常は「左」、「中央」、「右」として区別されます。子を持つノードは親ノードであり、子ノードには親への参照が含まれる場合があります。ツリーの外側には、多くの場合、「ルート」ノード (すべてのノードの祖先) への参照があります (存在する場合)。データ構造内のどのノードにも、ルート ノードから開始し、左、中央、または右の子への参照を繰り返したどることで到達できます。

三項木は、三項検索木と三項ヒープを実装するために使用されます。

• 有向エッジ- 親から子へのリンク。
• ルート- 親を持たないノード。ルート付きツリーにはルート ノードが最大 1 つ存在します。
• リーフ ノード- 子を持たないノード。
• 親ノード- 有向エッジによってその子または複数の子に接続された任意のノード。
• 子ノード- 有向エッジによって親ノードに接続された任意のノード。
• 深さ- ルートからノードまでのパスの長さ。特定の深さにあるすべてのノードのセットは、ツリーのレベルと呼ばれることもあります。ルート ノードは深さ 0 にあります。
• 高さ- ルートからツリーの最も深いノードまでのパスの長さ。 1 つのノード (ルート) のみを持つ (ルート付き) ツリーの高さは 0 です。 サンプル図では、ツリーの高さは 2 です。
• 兄弟- 同じ親ノードを共有するノード。
• ノード p がノードq からルートへのパス上に存在する場合、そのノード p はノード q の祖先となります。その場合、ノード q は p の子孫と呼ばれます。
• ノードのサイズは、ノード自体を含む子孫の数です。

• 最大ノード数

– を三分木の高さとします。 ${\displaystyle h}$

–高さhの三分木の最大ノード数を と する${\displaystyle M(h)}$

–${\displaystyle M(h)=1+3+9+\cdots +3^{h}=\sum _{i=0}^{h}3^{i}={\frac {3^{h+1}-1}{2}}}$

– 高さ h のすべてのツリーには最大で 個のノードがあります。 ${\displaystyle {\frac {3^{h+1}-1}{2}}}$

• ノードがTREE を占有する場合、その左の子はTREE に格納されます。${\displaystyle N}$${\displaystyle [k]}$${\displaystyle [3k-1]}$
• Mid Child はTREE に格納されます。${\displaystyle [3k]}$
• 右の子はTREE に格納されます。${\displaystyle [3k+1]}$

ノードは、他の 3 つのノードの間に 3 項ツリーに挿入することも、外部ノードの後に​​追加することもできます。3 項ツリーでは、挿入されるノードはどの子であるかが指定されます。

追加される外部ノードがノード A であるとします。ノード A の後に新しいノードを追加するには、A は新しいノードをその子の 1 つとして割り当て、新しいノードはノード A をその親として割り当てます。

内部ノードへの挿入は、外部ノードへの挿入よりも複雑です。内部ノードがノード A で、ノード B が A の子であるとします。(挿入が右の子を挿入するものである場合、B は A の右の子であり、左の子の挿入または中間の子の場合も同様です。) A は子を新しいノードに割り当て、新しいノードは親を A に割り当てます。次に、新しいノードは子を B に割り当て、B は親を新しいノードとして割り当てます。

削除は、ツリーからノードを削除するプロセスです。三分木では、特定のノードだけを明確に削除できます。

削除するノードがノード A であるとします。ノードに子がない場合 (外部ノード)、削除は A の親の子をnullに設定し、A の親を null に設定することで実行されます。子が 1 つある場合は、A の子の親を A の親に設定し、A の親の子を A の子に設定します。

下の図は、 12 個の 2 文字の単語を表すバイナリ検索ツリーです。左の子のすべてのノードの値は小さく、右の子のすべてのノードの値は大きくなります。検索はルートから始まります。「ON」という単語を見つけるには、それを「IN」と比較して右のブランチに進みます。すべての比較で、両方の単語の各文字にアクセスできます。

        で
      / \
     の
    / \ / \
   またはによって
    \ \ \ / \
    彼はそれを

デジタル検索では、文字列を文字ごとに保存しようとします。次の図は、同じ 12 語のセットを表すツリーです。

         _ _ _ _ _ _ _ _ _ _ _ _ _
        / / / \ \ \
       / / / \ \ \
      アビオット
     / \ / \ | / | \ /|\ |
    ステイエンストフンロ
   として、で、によって、彼で、それはの、またはに

各入力単語は、それを表すノードの下に表示されます。小文字の単語を表すツリーでは、各ノードに 26 方向の分岐があります。検索は非常に高速です。「IS」の検索はルートから始まり、「I」分岐、次に「S」分岐を経て、目的のノードで終了します。各ノードで、配列要素にアクセスし、null をテストして分岐します。

                    私
              / | \
             / | \
            ボソ
         / | \ / \ | \
        意味不明
        | \ | / \ |
        シェフロ
         \
          t

上の図は、同じ 12 語のセットに対するバランスのとれた 3 進検索ツリーです。低位ポインタと高位ポインタは斜めの線で示され、等位ポインタは垂直線で示されます。単語「IS」の検索はルートから始まり、等位の子ノードを下って値「S」のノードまで進み、2 回の比較の後にそこで停止します。単語「AX」の検索では、最初の文字「A」と 3 回の比較が行われ、2 番目の文字「X」と 2 回の比較が行われた後、単語がツリーに存在しないことが報告されます。^[1]

• 三項探索木
• 三分木
• 三元ヒープ
• すべての原始ピタゴラス数列を含む2つの無限三分木は、原始ピタゴラス数列のツリーとピタゴラス数列を生成するための公式で説明されています。両方のツリーのルートノードには、3つ組[3,4,5]が含まれています。^[2]

• 二分木
• ツリー構造