「みんなのデータ構造」学習メモ：6.1 BinaryTree 二分木

みんなのデータ構造（紙書籍+電子書籍） – 技術書出版と販売のラムダノート

amazon

みんなのデータ構造

これまでのメモ

• 「みんなのデータ構造」学習メモ：2.1 ArrayStack
• 「みんなのデータ構造」学習メモ：2.3 ArrayQueue
• 「みんなのデータ構造」学習メモ：2.4 ArrayDeque
• 「みんなのデータ構造」学習メモ：3.1 SLList 単方向連結リスト
• 「みんなのデータ構造」学習メモ：3.2 DLList 双方向連結リスト
• 「みんなのデータ構造」学習メモ：5.1 ChainedHashTable, 5.2 LinearHashTable

今回は第6章。ここから木構造の話。

TypeScript によるソースコード
https://github.com/zaki-yama/open-data-structures-typescript/blob/master/src/BinaryTree.ts

用語

• 二分木とは
  • 閉路（cycle）を持たない
  • 次数が3以下
  • コンピュータサイエンスにおける二分木では、ふつう根（root）を持つ。r と表記

• （ノード u の）高さ： u から u の子孫への経路の長さの最大値（下図では1）
  • 木の高さ：根の高さ（下図では4）
• （ノード u の）深さ： u から根までの経路の長さ（下図では3）
• 葉：ノード u が子を持たない場合、u は葉と呼ぶ
• 外部ノード：子を持たないノードに対して、外部ノードを子として持つとみなす
  • n >= 1 個の（本物の）ノードを持つ二分木は、 n + 1 個の外部ノードを持つ（帰納法で示せる）

6.1 BinaryTree：基本的な二分木

ノード u を表現するには、u に隣接するノードを明示的に保持すればいい。

// typescript のサンプル
class Node {
  left: Node | null;
  right: Node | null;
  parent: Node | null;

  constructor() {
    this.left = this.right = this.parent = null;
  }
}

ノードが存在しない部分を null で表現すると、外部ノードや根の親は null に対応する。

6.1.1 再帰的なアルゴリズム

6.1 節ではこの後、二分木のサイズ（ノードの数）や高さを計算するためのノードの走査方法として3種類紹介している。

最初は再帰を使うもの。

traverse(u: Node | null) {
  if (u === null) return;
  this.traverse(u.left);
  this.traverse(u.right);
}

6.1.2 二分木の走査

再帰の問題点：再帰の深さの最大値は、ノードの深さの最大値 = 木の高さ。
これが非常に大きいと、再帰のためのスタックとして利用できる量以上の領域を要求し、プログラムがクラッシュしてしまうことがある。
いわゆるスタックオーバーフロー。

再帰なしで二分木を走査するためには、どこから来たかによって次の行き先を決めるアルゴリズムを使えばいい。

1. u に u.parent から来たときは、次は u.left へ
2. u に u.left から来たときは、次は u.right へ
3. u に u.right から来たときは、次は u.parent へ戻る

幅優先（breadth-first）走査

別の走査方法として紹介されていたのが、幅優先走査と呼ばれる手法。
これは、文字通り根から下に向かって深さごとにすべてのノードを操作する。
同じ深さのノードは左から右の順に訪問する。

幅優先の走査はキュー q を使って実装できる。

1. キューからノード u を取り出
2. ノード u.left および u.right があればキューに追加する

というのを根 r から始めてキューが空になるまで繰り返す。

余談：深さ優先（depth-first）探索

幅優先と聞いて連想したのが深さ優先（探索）というワードだ。これは 12.3.2 項で登場するっぽい。

• 深さ優先探索 - Wikipedia
• DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【前編】 - Qiita

などを読むと、深さ優先の場合はキューではなくスタックを使うのかな。
というか、6.1.2 で紹介された方法で parent 使わない実装がまさにそうなんじゃないだろうか。

わからなかったこと

サイズや高さを求めるロジックや、走査については詳しく説明されていたが、
ノードに値をどう追加／削除するのか、とかは触れられてなかった（ので、書いたコードの動作確認ができなかった）。
6.2 節以降の木構造でやるのかな。