2分木、2分探索木

2分木の実装

以下は，2分木を実現するC言語プログラムであり，教科書リスト2.11 ~ 2.12 (pp.40 ~ 41) をベースに実装されている． ソースコードは，binarytree.h，binarytree.c，main_binarytree.c に分割されている．

サンプルコードはこちらからダウンロード可能．

ヘッダーファイル binarytree.h

#ifndef INCLUDE_GUARD_BINARYTREE_H
#define INCLUDE_GUARD_BINARYTREE_H

typedef struct node {
  char *label;
  struct node *left;
  struct node *right;
} Node;

Node *create_tree(char *label, Node *left, Node *right);
void preorder(Node *n);
void inorder(Node *n);
void postorder(Node *n);
void display(Node *n);
void breadth_first_search(Node *n);
int height(Node *n);
void delete_tree(Node *n);

#endif  // INCLUDE_GUARD_BINARYTREE_H

ソースファイル main_binarytree.c

#include <stdio.h>
#include <stdlib.h>
#include "binarytree.h"

int main(void) {
  // Build a binary tree
  Node *f = create_tree("F", NULL, NULL);
  Node *i = create_tree("I", NULL, NULL);
  Node *d = create_tree("D", f, NULL);
  Node *g = create_tree("G", NULL, NULL);
  Node *a = create_tree("A", i, d);
  Node *l = create_tree("L", NULL, g);
  Node *c = create_tree("C", a, l);

  printf("preorder: ");
  preorder(c);
  printf("\n");

  printf("inorder: ");
  inorder(c);
  printf("\n");

  printf("postorder: ");
  postorder(c);
  printf("\n");

  printf("bfs: ");
  breadth_first_search(c);
  printf("\n");

  display(c);
  printf("\n");

  printf("height: %d\n", height(c));

  delete_tree(c);

  return EXIT_SUCCESS;
}

コンパイルと実行

以下の内容の Makefile を作成する．

ファイル Makefile

binarytree: binarytree.o main_binarytree.o

コマンドラインでmakeコマンドを実行すると，Cコンパイラによって実行ファイルが生成される． 実行ファイル binarytree を実行すると，図2.21 (p.38) の節点 'B' 'K' 'J' 'H' 'E' が欠けた2分木を構築し，以下のような結果が表示される．

mac$ make
cc    -c -o binarytree.o binarytree.c
cc    -c -o main_binarytree.o main_binarytree.c
cc   binarytree.o main_binarytree.o   -o binarytree
mac$ ./binarytree
preorder: C A I D F L G
inorder: I A F D C L G
postorder: I F D A G L C
bfs: C A L I D G F
C(A(I(null,null),D(F(null,null),null)),L(null,G(null,null)))
height: 4
mac$

基本課題

1. ラベルとして文字列をとる2分木を実現するプログラム binarytree を実装せよ．binarytree.c には，最低限以下の関数を定義すること．
   • Node *create_tree(char *label, Node *left, Node *right)
     • label を根のラベル，左部分木の根を left，右部分木の根を right とする2分木を作成し，作成した2分木の根のポインタを返す．
   • void preorder(Node *n)
     • 節点 n を根とする2分木を探索し，行きがけ順で節点のラベルを標準出力する．
   • void inorder(Node *n)
     • 節点 n を根とする2分木を探索し，通りがけ順で節点のラベルを標準出力する．
   • void postorder(Node *n)
     • 節点 n を根とする2分木を探索し，帰りがけ順で節点のラベルを標準出力する．
   • void display(Node *n)
     • 節点 n を根とする2分木の構造が完全に分かる形式で標準出力する．例えば，"C(A(I(null,null),D(F(null,null),null)),L(null,G(null,null)))"はその一例である．
   • void breadth_first_search(Node *n)
     • 節点 n を根とする2分木を幅優先探索し，ラベルを標準出力する．課題2で実装したキューを上手く活用すること．
   • int height(Node *n)
     • 節点 n を根とする2分木の高さを返す．ただし，教科書の定義の高さ + 1とする．つまり NULL の高さが0，根のみの木が高さ 1 とすること．
   • void delete_tree(Node *n)
     • 節点 n を根とする2分木を削除 (2分木の節点用に確保されたメモリ領域を全て解放) する．
2. 以下の2分木に対して，1 で実装した関数が正しく動作することを確認すること．

発展課題

display関数を改良，表示方法を工夫し，2分木の構造がよりわかりやすく表示されるようにしなさい．表示がよりわかりやすくなったことを，例を示しながら説明すること．

例えば，以下のような表示を出力すれば及第点とする．これは，基本課題 2 の2分木を90度左に回転して出力したものである． しかし，決して美しい表示とは言えないので，是非これよりも美しい形式で2分木を表示する自分だけのdisplay関数を実装して欲しい．

    B
      \
            G
          /
        F
          \
            H
  /
A
  \
            I
          /
        E
      /
    C
      \
        D

2分探索木の実装

以下は，2分探索木を実現するC言語プログラムであり，教科書リスト 4.3 ~ 4.7 (pp.69 ~ 77) をベースに実装されている． ソースコードは，binarysearchtree.h，binarysearchtree.c，main_binarysearchtree.c に分割されている．

サンプルコードはこちらからダウンロード可能．

ヘッダーファイル binarysearchtree.h

#ifndef INCLUDE_GUARD_BINARYSEARCHTREE_H
#define INCLUDE_GUARD_BINARYSEARCHTREE_H

#include <stdbool.h>

typedef struct node {
  int value;
  struct node *left;
  struct node *right;
} Node;

// binarysearchtree-specific functions
int min_bst(Node *root);
bool search_bst(Node *root, int d);
void insert_bst(Node **root, int d);
void delete_bst(Node **root, int d);

// Reuse the following functions implemented for the binarytree
void inorder(Node *root);
void display(Node *root);
void delete_tree(Node *root);

#endif  // INCLUDE_GUARD_BINARYSEARCHTREE_H

ソースファイル main_binarysearchtree.c

#include <stdio.h>
#include <stdlib.h>
#include "binarysearchtree.h"

int main(void) {
  // Build a binary search tree
  Node *root = NULL;
  insert_bst(&root, 20);
  insert_bst(&root, 10);
  insert_bst(&root, 26);
  insert_bst(&root, 14);
  insert_bst(&root, 13);
  insert_bst(&root,  5);

  printf("inorder: ");
  inorder(root);
  printf("\n");

  display(root);
  printf("\n");

  if (search_bst(root, 14)) {
    printf("Found!: 14\n");
  } else {
    printf("Not found!: 14\n");
  }
  if (search_bst(root, 7)) {
    printf("Found!: 7\n");
  } else {
    printf("Not found!: 7\n");
  }

  printf("Minimum value of this bst: %d\n", min_bst(root));

  delete_bst(&root, 10);
  printf("Value 10 deleted\n");

  printf("inorder: ");
  inorder(root);
  printf("\n");

  display(root);
  printf("\n");

  delete_tree(root);

  return EXIT_SUCCESS;
}

コンパイルと実行

以下の行を Makefile に加える．

binarytree: binarytree.o main_binarytree.o

binarysearchtree: binarysearchtree.o main_binarysearchtree.o  # added

さらに，

make binarysearchtree

を実行することでコンパイル出来る． 実行ファイル binarysearchtree を実行すると，以下のような結果が表示される．

mac$ ./binarysearchtree
inorder: 5 10 13 14 20 26
20(10(5(null,null),14(13(null,null),null)),26(null,null))
Found!: 14
Not found!: 7
Minimum value of this bst: 5
Value 10 deleted
inorder: 5 13 14 20 26
20(13(5(null,null),14(null,null)),26(null,null))
mac$

2分探索木は，葉を除く任意の節点 n に対して，その節点のデータ n->value は，n の左の子を根とする部分木 (左部分木) 内の任意の節点 l のデータ l->value より大きく (l->value < n->value)，n の右の子を根とする部分木 (右部分木) 内の任意の節点 r のデータ r->value より小さい (n->value < r->value) という条件の下に構築されている．

これにより，2分探索木を根から通りがけ順 (inorder) でなぞると全てのデータが整列して出力される．

この特徴は「挿入」や「削除」を正しく実装されているかのデバッグに役立つ (それらの操作後の2分探索木に対して，通りがけ順でなぞって出力されるデータが整列されたものでなければ，実装が間違っているということになる) ので，2分木の実装の基本課題で実装したinorder関数の積極的な利用を推奨する (当然だが，このデバッグはinorder関数が正しく実装されていることが前提であることに注意すること)．また，構築した2分探索木の構造を把握するために，display関数を利用することも推奨する．

そして，確保したメモリ領域を解放しないまま放置するのは，C言語の作法としてよろしくないので，delete_tree関数の利用も推奨する．

基本課題

1. ラベルとして整数値をとる2分探索木を実現するプログラム binarysearchtree を実装せよ．binarysearchtree.c には，最低限以下の関数を定義すること．
   • int min_bst(Node *root)
     • root を根とする2分探索木における最小値を探索し，その値を返す．2分探索木が空の場合は -1 を返す．
   • bool search_bst(Node *root, int d)
     • 整数 d が root を根とする2分探索木に存在するか検査し，存在すれば true，存在しなければ false を bool 型で返す．
   • void insert_bst(Node **root, int d)
     • root を根とする2分探索木に整数 d を追加する．2分探索木が空の場合は，整数 d の根を作成する．
       • insert_bst関数内でNode型ポインタ root が保持する内容 (アドレス) を書き換えるため，insert_bstにはNode型ポインタ root のポインタ (ダブルポインタ) を第一引数にセットしている．こうしないと，insert_bst関数内で書き換えた内容はmain関数側で反映されないので注意すること．
       • シングルポインタだと所謂「アドレスの値渡し」となるので，関数内でアドレスを変更しても，それは関数にコピーされた値を操作しただけなので，関数の呼び出し側には反映されない
   • void delete_bst(Node **root, int d)
     • root を根とする2分探索木から整数 d を削除する．insert_bst関数と同様に，第一引数にNode型ポインタ root のポインタをセットしている．
2. 以下の要件を全て満たすことを確認すること．
   • 空の2分探索木に対して，値 10, 15, 18, 6, 12, 20, 9をこの順で挿入したときの作られる2分探索木を確認せよ
   • 以下のすべての場合に対して探索が正しく動作することを確認せよ
     • 探索するデータが根にある場合
     • 葉にある場合
     • 根以外の非終端節点にある場合
     • データが2分探索木にない場合
   • 2分探索木が空の場合，空でない場合それぞれに対して，最小値の探索が正しく動作することを確認せよ
   • 削除のアルゴリズムは複雑なので，以下のようなことを考慮しながら十分にテストし，正しく動作することを確認せよ．また，各テストがどのような場合のテストであるかを明確かつ簡潔に説明すること．
     • 切除される節点が子供を何個持つか
     • 切除される節点が根であるか

発展課題

各節点にその節点を根とする部分木の高さの情報を持たせた2分探索木プログラム bst_advanced を実装してみよう． このようなデータ構造にしておくと，木の高さをO(1)で求められるようになり，AVL木のような平衡2分探索木の実装に役立つ．

以下に bst_advanced のソースコードを示す．ソースコードは bst_advanced.h，bst_advanced.c，main_bst_advanced.c に分割されている．

サンプルコードはこちらからダウンロード可能．

ヘッダーファイル bst_advanced.h

#ifndef INCLUDE_GUARD_BST_ADVANCED_H
#define INCLUDE_GUARD_BST_ADVANCED_H

#include <stdbool.h>

typedef struct node {
  int value;
  int height;
  struct node *left;
  struct node *right;
} Node;

// advanced bst-specific functions
Node *insert_bst(Node *root, int d);
Node *delete_bst(Node *root, int d);

// Reuse the following functions implemented for the binarytree and binarysearchtree
int min_bst(Node *root);
bool search_bst(Node *root, int d);
void inorder(Node *root);
void display(Node *root);
void delete_tree(Node *root);

#endif  // INCLUDE_GUARD_BST_ADVANCED_H

ソースファイル bst_advanced.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "bst_advanced.h"

int min_bst(Node *root) { ... }

bool search_bst(Node *root, int d) { ... }

int get_height(Node *root) {
  if (root == NULL) return 0;
  else              return root->height;
}

int reset_height(Node *root) {
  int lh = get_height(root->left);
  int rh = get_height(root->right);
  return 1 + (lh > rh ? lh : rh);
}

Node *insert_bst(Node *root, int d) { ... }

Node *delete_min_bst(Node *root) { ... }

Node *delete_bst(Node *root, int d) { ... }

void inorder(Node *root) { ... }

void display(Node *root) { ... }

void delete_tree(Node *root) { ... }

ソースファイル main_bst_advanced.c

#include <stdio.h>
#include <stdlib.h>
#include "bst_advanced.h"

int main(void) {
  // Build an advanced binary search tree
  Node *root = NULL;
  root = insert_bst(root, 20);
  root = insert_bst(root, 10);
  root = insert_bst(root, 26);
  root = insert_bst(root, 14);
  root = insert_bst(root, 13);
  root = insert_bst(root,  5);

  printf("inorder: ");
  inorder(root);
  printf("\n");

  display(root);
  printf("\n");

  if (search_bst(root, 14)) {
    printf("Found!: 14\n");
  } else {
    printf("Not found!: 14\n");
  }
  if (search_bst(root, 7)) {
    printf("Found!: 7\n");
  } else {
    printf("Not found!: 7\n");
  }

  printf("Minimum value of this bst: %d\n", min_bst(root));

  root = delete_bst(root, 10);
  printf("Value 10 deleted\n");

  printf("inorder: ");
  inorder(root);
  printf("\n");

  display(root);
  printf("\n");

  delete_tree(root);

  return EXIT_SUCCESS;
}

ソースコードの説明

ヘッダーファイル bst_advanced.h に記述されているように，構造体 Node に height というメンバ変数を持たせ，そこに自身を根とした2分探索木の高さの情報を格納している．高さは，2分木の基本課題1と同様に，教科書の定義の高さ + 1とするので注意すること．

その情報は，ソースファイル bst_advanced.c に実装されているget_height関数によってO(1)の時間計算量で取得でき，子供の木の高さの情報から自身の高さの情報を再設定するreset_height関数に利用されている．

bst_advanced を完成させるためには，insert_bst関数およびdelete_bst関数をbst_advanced用に実装し直す必要がある (基本課題とは違って，この実装ではそれらの関数はNode型のポインタを返していることに注意) が，それ以外の関数は基本課題で実装した関数を流用できる．そのため，以下に各関数の説明を示すが，既出のものは割愛する．

• Node *insert_bst(Node *root, int d)
  • root を根とする2分探索木に整数 d を追加する．2分探索木が空の場合は，整数 d の根を作成する．基本課題とは違い，この関数は再帰呼び出しを用いて実装される．
• Node *delete_min_bst(Node *root)
  • root を根とする2分探索木における最小値を削除し，その節点が子を持つ場合は木の回復を行った後，その木の根のポインタを返す．
• Node *delete_bst(Node *root, int d)
  • root を根とする2分探索木から整数 d を削除する．insert_bst関数と同様に再帰呼び出しを用いて実装される．
  • delete_bst関数の実装では，削除すべき節点の左右の子が両方とも NULL でないときに，min_bst関数およびdelete_min_bst関数を用いる．min_bst関数により探索した右部分木の最小値を削除対象の節点にコピーし (右部分木の最小値をもつ節点を削除対象の節点の位置に移動させ)，delete_min_bst関数により最小値をコピーされた節点の削除を行う．

コンパイルと実行

以下の行を Makefile に加える．

binarytree: binarytree.o main_binarytree.o

binarysearchtree: binarysearchtree.o main_binarysearchtree.o

bst_advanced: bst_advanced.o main_bst_advanced.o  # added

さらに，

make bst_advanced

を実行することでコンパイル出来る． 実行ファイル bst_advanced を実行すると，以下のような結果が表示される．display関数は，n->value#n->heightの形式で，各節点のデータと高さの情報を表示している (正直，非常に分かりづらいので，発展課題で実装したdisplay関数を積極的に活用していこう)．

mac$ ./bst_advanced
inorder: 5 10 13 14 20 26
20#4(10#3(5#1(null,null),14#2(13#1(null,null),null)),26#1(null,null))
Found!: 14
Not found!: 7
Minimum value of this bst: 5
Value 10 deleted
inorder: 5 13 14 20 26
20#3(13#2(5#1(null,null),14#1(null,null)),26#1(null,null))
mac$

発展課題では，bst_advanced を完成させ，以下の要件を全て確認すること．

1. 空の2分探索木に対して，値 10, 15, 18, 6, 12, 20, 19, 9をこの順で挿入して構築された2分探索木の各節点が正しい高さの情報を保持していることを確認せよ．

2. 1 で構築された2分探索木から 15 を削除する．15 を削除後の2分探索木の各節点が正しい高さの情報を保持していることを確認せよ．

3. 2 の操作後の2分探索木から 19 を削除する．19 を削除後の2分探索木の各節点が正しい高さの情報を保持していることを確認せよ．

LaTeXで木構造の図を作成する

今回のレポートでは，2分木・2分探索木の図を描いて説明した場合には加点するので，是非，読みやすくかつ分かりやすいレポートの作成に励んでもらいたい． LaTeXで木構造の図を作成することができるので，そのためのサンプルを以下に示す．このサンプルをコンパイルすると2分木の基本課題 2 で示した図が出力される．

\documentclass[a4paper]{article}
\def\pgfsysdriver{pgfsys-dvipdfmx.def}
\usepackage{tikz}
\usetikzlibrary{trees}
\thispagestyle{empty}

\begin{document}

\tikzstyle{level 1}=[sibling distance=3.8cm]
\tikzstyle{level 2}=[sibling distance=1.8cm]
\tikzstyle{level 3}=[sibling distance=1cm]
\tikzstyle{edge from parent}=[draw,-]
\begin{tikzpicture}
[node distance=1cm,tnode/.style={draw,circle,thick,minimum size=2em}]
\node [tnode] (root) {A}
child { node [tnode] {C}
  child {node [tnode] {D}}
  child {node [tnode] {E}
    child[fill=none] {edge from parent[draw=none]}
    child {node [tnode] {I}}
  }
}
child { node [tnode] {B}
  child {node [tnode] {F}
    child {node [tnode] {H}}
    child {node [tnode] {G}}
  }
  child[fill=none] {edge from parent[draw=none]}
};
\end{tikzpicture}

\end{document}

提出締切

2022年11月21日（月）13:30