バイナリツリーとは

  • ツリー構造で、すべてのノードの持つ子が最大でも2つ。
  • ひとつのノードがあり、親をもたない (ルートノード)
  • ルートノードを除く全てのノードは親を必ずひとつ持つ。
  • ノード間の親子関係は循環しない。

用語

  • leaf - 末端のノード

  • depth (深さ)
    • ルートノードからの距離。 ルートノードは深さ 0.
    • バランス木では、全ての葉はほぼ同じ深さとなる。
      • たとえば 1023 のノードからなるツリーの葉はすべて深さ9.
  • height (高さ)
    • 木の中の葉の深さのうち、最大のもの。

走査

  • Preorder traversal
    • ルートノードが最初に走査される。そして左の木、右の木という順で走査される。
  • Postorder traversal
    • 左の木が最初に走査され。次に右の木が走査され、最後にルートノードが走査される。
  • Inorder traversal
    • 左の木が先に走査され、次にルートノードが走査され、最後に右の木が走査される。

バイナリソートツリー Binary Sort Tree

  • バイナリツリー。
  • ノードの左にはノードよりも小さい値が、右にはノードと同じかそれ以上の値が入る。

少数の要素であれば Linked List でも序列を保ったまま操作可能だが、 要素が多くなると非効率になる。 リストに要素を追加した後でその位置を調べる場合、平均でリスト内の半分の要素を調べることになる。

ソートされた配列であればバイナリサーチを使うことができて効率的だが、新しい要素を追加する際には要素の移動を伴うため非効率である。 平均では新しい要素を追加する際に、既存の要素の半分を移動させる必要がある。

バイナリツリーは探索と挿入を効率的にできる構造として使われ、そのようなバイナリツリーを特にバイナリソートツリー(Binary Sort Tree, Binary Search Tree, 2分探索木)という。

  • 左の木にはそのノード以下の値が入る。
  • 右の木にはそのノード以上の値が入る。