木勉強メモ

アルゴリズム scala

木構造の取扱はプログラマなら基本なのかもだけれど、アルゴリズムとデータ構造をちゃんと勉強したことなかったので、必要ベースで勉強していく。

用語

用語説明
根(root)親を持たないノード。1つの木に対して1つ根。
辺(edge)親から子へのリンク。
葉(leaf)子を持たないノード。
兄弟(siblings)親が同じ子たち。
祖先(ancestor)p → q への経路がある場合、pをqの祖先と呼ぶ。
子孫(descendant)p → q への経路がある場合、qをpの子孫と呼ぶ。
レベル(level)ある木の深さの全ノードの集合を木のレベルと呼ぶ。
(ノードの)深さ(depth)根からノードまでの経路の長さ。
(ノードの)高さ(height)ノードから、一番深いノードまでの経路の長さ
木の高さ(Height of the tree)
木の深さ(depth of the tree)		木の全ノードの最大の高さ。
ノードのサイズ自分自身を含めた子孫の数
木に関する用語

二分木

どのノードも、子を、1または2しか持たない時、二分木(binary tree)と呼ぶ。

二分木の構造はデータフィールドの脇に左右の子を指すリンクを持たせる形。参考資料に合わせてCだと下記のようになる。

struct BinaryTreeNode {
    int data;
    struct BinaryTreeNode *left;
    struct BinaryTreeNode *right;
};

Scalaの場合は、left と right プロパティとして自身と同じ型の値を持つと考えて。

case class BinaryTreeNode(
    data: Int,
    left: Option[BinaryTreeNode],
    right: Option[BinaryTreeNode]
)

二分木の演算

二分木には基本演算と補助的演算が存在する

基本演算

  • 木に要素を挿入
  • 木から要素を削除
  • 要素を探索
  • 木を横断

補助的演算

  • 木のサイズを求める
  • 木の高さを求める
  • 最大和をもつレベルを求める
  • あるノード対の最小共通祖先（LCA）を求める。など。

二分木を横断する

前順序横断

  1. 根を訪問
  2. 前順序で左部分木を横断
  3. 前順序で右部分木を横断

Cでの実装（Cちゃんと書いたことないから変かもしれない）

#include <stdio.h>

struct BinaryTreeNode {
    int data;
    struct BinaryTreeNode *left;
    struct BinaryTreeNode *right;
};

void PreOrder(struct BinaryTreeNode *root) {
    if (root) {
        printf("%d", root->data);
        PreOrder(root->left);
        PreOrder(root->right);
    }
}

struct BinaryTreeNode makeBinaryTreeNode(int data, struct BinaryTreeNode *left, struct BinaryTreeNode *right) {
    struct BinaryTreeNode temp;
    temp.data = data;
    temp.left = left;
    temp.right = right;
    return temp;
}

int main() {

    struct BinaryTreeNode node7 = makeBinaryTreeNode(7, NULL, NULL);
    struct BinaryTreeNode node6 = makeBinaryTreeNode(6, NULL, NULL);
    struct BinaryTreeNode node5 = makeBinaryTreeNode(5, NULL, NULL);
    struct BinaryTreeNode node4 = makeBinaryTreeNode(4, NULL, NULL);
    struct BinaryTreeNode node3 = makeBinaryTreeNode(3, &node6, &node7);
    struct BinaryTreeNode node2 = makeBinaryTreeNode(2, &node4, &node5);
    struct BinaryTreeNode node1 = makeBinaryTreeNode(1, &node2, &node3);

    PreOrder(&node1);

    return 0;
}

// 実行結果
// 1245367</pre>

Scalaで同じことをする。

def preOrder(root: BinaryTreeNode): Unit = {
  print(root.data)
  root.left.foreach(preOrder)
  root.right.foreach(preOrder)
}

val node7 = BinaryTreeNode(7, None, None)
val node6 = BinaryTreeNode(6, None, None)
val node5 = BinaryTreeNode(5, None, None)
val node4 = BinaryTreeNode(4, None, None)
val node3 = BinaryTreeNode(3, Some(node6), Some(node7))
val node2 = BinaryTreeNode(2, Some(node4), Some(node5))
val node1 = BinaryTreeNode(1, Some(node2), Some(node3))

preOrder(node1) // 1245367

もう少し、Scalaらしく書いて見る。Scalaで二分木を表現するならば、sealed trait を用いて

sealed trait Tree[+A]
case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A]</pre>

のように表現できる。trait Tree のメソッドとして preOrder を定義すると

sealed trait Tree[+A] {
  def preOrder: Unit = this match {
    case Leaf(value) =&gt; print(value)
    case Branch(value, left, right) =&gt;
      print(value)
      left.preOrder
      right.preOrder
  }
}

val leaf7 = Leaf(7)
val leaf6 = Leaf(6)
val leaf5 = Leaf(5)
val leaf4 = Leaf(4)
val branch3 = Branch(3, leaf6, leaf7)
val branch2 = Branch(2, leaf4, leaf5)
val branch1 = Branch(1, branch2, branch3)

branch1.preOrder // 1245367
branch2.preOrder // 245
branch3.preOrder // 367</pre>

全要素を走査できるならば、map が定義できそう。

sealed trait Tree[+A] {
  ...

  def map[B](f: A =&gt; B): Tree[B] = this match {
    case Leaf(value) =&gt; Leaf(f(value))
    case Branch(value, left, right) =&gt; Branch(f(value), left.map(f), right.map(f))
  }
}

branch1.map(v =&gt; v * 10).preOrder // 10204050306070</pre>

foreach を定義してあげれば、preOrder 不要。

sealed trait Tree[+A] {
  ...

  def foreach[U](f: A =&gt; U): Unit = {
    this match {
      case Leaf(value) =&gt; f(value)
      case Branch(value, left, right) =&gt;
        f(value)
        left.foreach(f)
        right.foreach(f)
    }
  }
}

二分木で要素を探索する。C言語版。要素が存在したら、1を返し、無ければ0を返す。

int FindInBinaryTreeUsingRecursion(struct BinaryTreeNode *root, int data) {
    int temp;
    if (root == NULL) return 0;
    else {
        if (data == root-&gt;data)
            return 1;
        else {
            temp = FindInBinaryTreeUsingRecursion(root-&gt;left, data);
            if (temp != 0) return temp;
            else return (FindInBinaryTreeUsingRecursion(root-&gt;right, data));
        }
    }
}

これを参考にScala版。引数に A を引数にとって Boolean を返す関数をとり、Option[A] を返す。左から順に調べる。

def find(f: A =&gt; Boolean): Option[A] = {
    this match {
      case Leaf(value) =&gt; if (f(value)) Some(value) else None
      case Branch(value, left, right) =&gt;
        if (f(value)) Some(value)
        else {
          val temp = left.find(f)
          if (temp.isDefined) temp else right.find(f)
        }
    }
  }

参考