%=====================================================================
% 秋田高専 2E 情報工学概論 テキスト
%　　テーマ　ツリー構造(2分木)
%    本テキストの内容
%        ・
%        ・
%        ・
%        ・
%　　　 　・
%
% last updated 2005.12.19
%    created by  Masashi Yamamoto
%     e-mail yamamoto@akita-nct.jp
%=====================================================================
\documentclass[10pt,a4paper]{jarticle}
\usepackage{graphicx,amsmath,amssymb,ascmac,float}
\usepackage{html, listings, jlisting}
\usepackage{url}
\oddsidemargin 0mm  %左の余白 25.4mm-0mm　奇数ページ
\evensidemargin 0mm %左の余白 25.4mm-0mm　偶数ページ
\textwidth 160mm
\newcommand{\command}[1]{「\texttt{#1}」}
\newcommand{\cl}[1]{\texttt{#1}}
\newcommand{\tw}[1]{\texttt{#1}}
%
\newcounter{toi_num}
\newcommand{\toi}{\textbf{\texttt [問\arabic{toi_num}]}
   \addtocounter{toi_num}{1}}
%
\newcommand{\qbox}[2]{
{\fboxsep=0pt \fboxrule=0.4pt\fbox{\hspace{#1}#2\hspace{#1}}}
}
%
\renewcommand{\lstlistingname}{リスト}
\lstset{language=C,%
        basicstyle=\footnotesize,%
        commentstyle=\textit,%
        classoffset=1,%
        keywordstyle=\bfseries,%
	frame=tRBl,framesep=5pt,%
	showstringspaces=false,%
        numbers=left,stepnumber=1,numberstyle=\footnotesize%
	}%
%
\begin{htmlonly}
\usepackage{verbatimfiles}
 \providecommand{\lstinputlisting}[2][]{\verbatimlisting{#2}}
\end{htmlonly}
%
\begin{document}
\title{ツリー構造(その2)}
\author{山本昌志\thanks{独立行政法人　秋田工業高等専門学校　電気情報工学科}}
\date{2006年1月23日}
\maketitle
%
%
%=====================================================================
\section{本日の学習内容}
%=====================================================================
%---------------------------------------------------------------------
\subsection{前回の復習}
%---------------------------------------------------------------------
前回はツリー構造を学習した．これは，樹形図のように階層構造を持つデータ構造であっ
た．ノードの位置は親子関係により示される．特に，2分木と呼ばれる図
\ref{fig:B_tree}のデータ構造は重要である．以下のことをしっかり理解する必要があ
る．
\begin{itemize}
 \item データの追加方法
 \item データの削除方法
 \item データのサーチ(探索)方法
\end{itemize}
%
\begin{figure}[H]
 \begin{center}
  \includegraphics[keepaspectratio,scale=1.0]
  {figure/B_tree.eps}
  \caption{ツリー構造(2分木)}
  \label{fig:B_tree}
 \end{center}
\end{figure}
%
%---------------------------------------------------------------------
\subsection{本日の学習内容}
%---------------------------------------------------------------------
前回の講義でツリー構造の概要は分かったと思う．本日は，ツリー構造をC言語で実装す
る方法を教科書~\cite{text_algorithm_data}のプログラムを例にして，説明する．
%
%=====================================================================
\section{C言語でのツリー構造}
%=====================================================================
%---------------------------------------------------------------------
\subsection{ツリー構造}
%---------------------------------------------------------------------
C言語でツリー構造を実装する方法を教科書~\cite{text_algorithm_data}のList 6-1(p.169)〜
List 6-4(p.176-180)のプログラムをつかって説明する．このプログラムのツリー構造は，
図\ref{fig:tree}のようになっている．このデータ構造をC言語で取り扱うことにする．
そのためには，以下のようなことが必要である．
\begin{itemize}
 \item ノードを表す構造体の定義
 \item ノードの追加(ノードの作成を含む)
 \item ノードのサーチ(探索)
 \item ノードの削除(メモリーの解放を含む)
\end{itemize}
これらのことを，説明する．
%
\begin{figure}[H]
 \begin{center}
  \includegraphics[keepaspectratio,scale=0.9]
  {figure/tree.eps}
  \caption{教科書 List6-1〜List 6-4のツリー構造}
  \label{fig:tree}
 \end{center}
\end{figure}
%
%-------------------------------
\subsubsection{ノードを表す構造体}
%-------------------------------
図\ref{fig:tree}が2分木のツリー構造である．一つのノードは，データとその2つの子
を表すポインターからなる．このように複数の異なる型のデータから成る情報を表すため
には，構造体を用いる．その構造体をリスト\ref{prog:B_tree_node}に示す．

このツリー構造を使うためには，型宣言として以下のものが必ず必要である．
\begin{description}
 \item[ノードを表す構造体]データと子を示すポインターから構成され，ノードを表す．
 \item[ルートを表すポインター]ツリー構造のデータをたどるために，ルートを示すポイ
	    ンターが必ず必要である．
\end{description}
%----------- 2分木の構造体 --------------------
\lstinputlisting
[caption=2分木のノードを表す構造体(教科書 List 6-1),label=prog:B_tree_node]
{program/list6-1e.c}
%
ツリーはノードのみならず，ルートを表すポインターが必要である．教科書のList
6-4(p.176)のように，
%
\begin{quote}
 \setlength{\baselineskip}{12pt}
 \begin{verbatim}
	tree_node *tree_root=NULL;
 \end{verbatim}
\end{quote}\vspace{-5mm}
とそのポインターを宣言しておく．もちろん，これはノードを表す構造体のよりも後で宣
言する必要がある．先に宣言すると，\tw{tree\_node}という型がコンパイラーが分からない
からである．また，初期値は意味のないポインター(\tw{NULL})を入れておく．最初はルー
トがないため，それを表すポインターは意味が無いためである．
%
%--------------------------
\subsubsection{ノードの作成}
%--------------------------
データである整数値を引数に取るノード生成の関数は，リスト
\ref{prog:creat_new_node}の通りである．この関数の動作は，以下の通りである．
\begin{enumerate}
 \item \tw{malloc}関数でノードを表す構造体(型は\tw{tree\_node})ひとつ分のメモリー
       を確保する．そして，確保されたメモリーの先頭アドレスを\tw{tree\_new}という
       ポインターに代入している．
 \item メモリーの確保に失敗すると，\tw{tree\_new}は\tw{NULL}ポインターとなる．確
       保に失敗した場合は，\tw{exit}関数によりプログラムを終了する．
 \item メモリーの確保に成功したならば，ノードを表す構造体のメンバーに初期値を与
       える．
 \begin{itemize}
  \item 左側の子を示すポインター\tw{left}には，\tw{NULL}ポインターを代入する．これ
	は，まだ子が未定なのでこのポインターは意味がないと言うことを明記している．
  \item 右側の子を示すポインター\tw{left}も，\tw{NULL}ポインターを代入する．
  \item メンバー\tw{value}には，ノードの値\tw{num}を代入する．
 \end{itemize}
\end{enumerate}
%----------- ノードの作成 --------------------
\lstinputlisting
[caption=2分木のノードの作成(教科書 List 6-2の一部),label=prog:creat_new_node]
{program/list6-2-1e.c}
%
%--------------------------
\subsubsection{ノードの追加}
%--------------------------
ノードを追加する関数は，リスト\ref{prog:insert_tree}の通りである．この関数の引数
は2つで，
\begin{itemize}
 \item 追加する整数データ(\tw{num})
 \item 追加するノードの親を表すポインター(\tw{*node})．最初に関数を呼
       び出すときには，ルートのポインターを与える(教科書 List 6-4のp.180参照)．
\end{itemize}
である．戻り値は無い(\tw{void})．

リスト\ref{prog:insert_tree}の動作は，以下の通りである．
\begin{enumerate}
 \item ポインター\tw{node}が何も示していない(\tw{NULL})ならば，新たにノードを作
       成(\tw{creat\_new\_node(num)})して，メモリーの先頭アドレスをルートを示す
       ポインター(\tw{tree\_root})に代入する(4-8行)．これが実行されるのは，
       \tw{node}がルートを示すポインター(\tw{tree\_root})の場合に限る．次に示す
       再帰呼び出しで呼び出された場合には\tw{node}は\tw{NULL}にならない．
 \item \tw{node}が\tw{NULL}とならない場合，ノードの値(\tw{node->value})と追加す
       る値(\tw{num})の大小関係により，2つの場合に分けられる．
       \begin{itemize}
	\item {\bf ノードの値(\tw{node->value}) $>$ 追加する値(\tw{num})}\qquad
	      要するにノードの左側の子になる可能性がある場合である(12-18行)．
	      \begin{itemize}
	       \item もし左側の子があれば(\tw{node->left!=NULL})，左側の子を親と
		     して再帰呼び出しをする．
	       \item 子が無ければ(\tw{else})，新たにノードを作成して，それを左側
		     の子にする．
	      \end{itemize}
	\item {\bf さもなければ(else)}\qquad
	      要するにノードの右側の子になる可能性がある場合である(21-27行)．
	      \begin{itemize}
	       \item もし右側の子があれば(\tw{node->right!=NULL})，右側の子を親と
		     して再帰呼び出しをする．
	       \item 子が無ければ(\tw{else})，新たにノードを作成して，それを右側
		     の子にする．
	      \end{itemize}
       \end{itemize}
\end{enumerate}
%----------- ノードの追加 --------------------
\lstinputlisting
[caption=2分木のノードの追加(教科書 List 6-2の一部),label=prog:insert_tree]
{program/list6-2-2e.c}
%
%---------------------------
\subsubsection{ノードのサーチ}
%---------------------------
ノードを探索する関数は，リスト\ref{prog:find_value}の通りである．この関数の引数
は2つで，
\begin{itemize}
 \item 探索するノードを表すポインター(\tw{*node})．最初に関数を呼
       び出すときには，ルートのポインターを与える(教科書 List 6-4のp.180参照)．
 \item 追加する整数データ(\tw{val})
\end{itemize}
である．戻り値は，探索で整数データ(\tw{val})と一致するノードがあった場合，そのノー
ドのポインター(\tw{node})を返す．見つからなかった場合は，\tw{NULL}ポインターを返
す．

リスト\ref{prog:find_value}の動作は，以下の通りである．要するにルートから，大小
関係を調べて，ツリーをたどって探索をしているのである．
\begin{enumerate}
 \item {\bf ノードの値(\tw{node->value}) $>$ 探索する値(\tw{num})}\qquad
       要するにノードの左側の子と一致する可能性がある場合である(6-10行)．
	      \begin{itemize}
	       \item もし左側の子が無ければ(\tw{node->left==NULL})，一致するデー
		     タは無いので，\tw{NULL}ポインターを返して，探索は終了．
	       \item 左側に子があれば，それを探索するノードとし，再帰呼び出しす
		     る．．
	      \end{itemize}
 \item {\bf ノードの値(\tw{node->value}) $<$ 探索する値(\tw{num})}\qquad
       要するにノードの右側の子と一致する可能性がある場合である(13-17行)．
	      \begin{itemize}
	       \item もし左側の子が無ければ(\tw{node->right==NULL})，一致するデー
		     タは無いので，\tw{NULL}ポインターを返して，探索は終了．
	       \item 右側に子があれば，それを探索するノードとし，再帰呼び出しを
		     する．
	      \end{itemize}
 \item 上の2つに当てはまらなければ，それは {\bf ノードの値(\tw{node->value}) = 探
       索する値(\tw{num})} の場合である．探索のデータが見つかったので，ノードのポ
       インターを返す．
\end{enumerate}
%----------- ノードの追加 --------------------
\lstinputlisting
[caption=2分木のサーチ(教科書 List 6-3),label=prog:find_value]
{program/list6-3e.c}
%
%-------------------------
\subsubsection{ノードの削除}
%-------------------------
ノードを削除する関数は，リスト\ref{prog:find_value}の通りである．この関数の引数
は1つで，削除するデータ(\tw{val})である．戻り値は整数で，削除成功ならば 1 を，削
除すべきデータが無いならば 0 を返す．

この関数の動作に先立って，使われている変数の役割を示しておく．\\
\begin{center}
\begin{minipage}{100mm}
 \begin{itemize}
  \item[\tw{node}]削除するべきか否か，調査しているノードを示すポインター．初期値
		  は，ルート(\tw{tree\_root})．
  \item[\tw{parent\_node}]調査しているノードの親ノードを示すポインター．初期値は
		  \tw{NULL} ポインター．
  \item[\tw{left\_biggest}]削除すべきノードの左側の子孫で最大の値をもつノードを示
		  すポインター
  \item[\tw{direction}]削除すべきノードが左側の子(\tw{-1})か右側の子(\tw{1})かを示す
		  整数．初期値は \tw{0} である．
 \end{itemize}
\end{minipage}
\end{center}

リスト\ref{prog:find_value}の動作は，以下の通りである．
\begin{enumerate}
 \item 削除すべきノードのサーチ(12-28行)
       \begin{itemize}
	\item 削除すべきノードが見つかったならば，そのノードをポインター\tw{node}で
	      示す．削除すべきノードの親ノードはポインター\tw{parent\_node}で示す．
	      \tw{node}が左の子の場合 \tw{direction=-1} で，右側の子の場合
	      \tw{direction=1} である．
	\item 削除すべきノードがない場合，\tw{node} は \tw{NULL} ポインターとし
       て，呼び出し元へ \tw{0} を返す．
       \end{itemize}
 \item 削除すべきノードを削除
       \begin{itemize}
	\item 削除すべきノードの両方に子が無い，あるいは片方に子が無い場合．30行
	      で判断し，31-56行で処理している．ここで，注意すべきは，
	      \tw{direction=0}の時である．これは，削除すべきノードがルートである
	      ことを示している．
	\item 削除すべきノードの両方に子がある場合．58-80行で処理している．
	      \begin{itemize}
	       \item 左側の子孫の最大値を探索する(65-70行)．
	       \item 削除すべきノードの値を，左側の子孫の最大値を代入している(74
		     行)．左側の子孫の最大値を持つノードの親ノードのポインターを
		     付け替えている(75-78行)．
	      \end{itemize}
       \end{itemize}
\end{enumerate}
%----------- ノードの削除 --------------------
\lstinputlisting
[caption=2分木の削除(教科書 List 6-4の一部),label=prog:delete_tree]
{program/list6-4-1e.c}
%
%---------------------------
\subsubsection{メモリーの解放}
%---------------------------
メモリーを解放する関数は，リスト\ref{prog:free_tree}の通りである．引数で渡された
ポインターが示すノードとその子孫が使っているメモリーを解放している．
%----------- メモリーの解放 --------------------
\lstinputlisting
[caption=メモリーの解放(教科書 List 6-4の一部),label=prog:free_tree]
{program/list6-4-2e.c}
%
%=====================================================================
\section{多数の子を持つツリー}
%=====================================================================
これには，いろいろな方法がある．あまり踏み込まないことにする．興味のある者は，自
分で調べよ．
%
%=====================================================================
\section{平衡木}
%=====================================================================
%---------------------------------------------------------------------
\subsection{計算量のオーダー}
%---------------------------------------------------------------------
データの数が$N$個の場合，サーチの計算回数を考えよう．もっともバランス良く，ツリー
構造ができたとする．その深さを$m$とすると，
\begin{align}
 \sum_{n=1}^{m-1} 2^{n-1}\leq N=1+2+4+8+\cdots\leq\sum_{n=1}^{m} 2^{n-1} \\
\end{align}
が成り立つ．これから，
\begin{align}
 2^{m-1}-1 \leq N \leq 2^{m}-1
\end{align}
となる．これから，深さ$m$は
\begin{align}
 m-1 \leq \log_2(N+1) \leq m
\end{align}
を満たす整数となる．サーチの回数はツリーの深さと同程度であることが直感的に分かる
だろう．従って，データ数$N$が大きい場合，その計算回数(比較回数)は$O(\log_2 N)$と
なることが分かるだろう．

バランスが悪い木(教科書 Fig 6-19右図)の場合の，比較の回数は平均で$N/2$回である．
従って，計算量は$O(N)$となる．

データ量が非常に多い場合，すなわち$N$が非常に大きい場合，この計算量の差は顕著な
者となる．したがって，バランスの良いツリー構造を作らなくてはならないことが分かるだろう．
%
%---------------------------------------------------------------------
\subsection{平衡木の作成}
%---------------------------------------------------------------------
%--------------------
\subsubsection{AVL木}
%--------------------
教科書を使って，説明する．
%-------------------
\subsubsection{B木}
%-------------------
教科書を使って説明する．
%
%
%=====================================================================
%  参考文献
%=====================================================================
\bibliographystyle{jplain}
\bibliography{reference}
%=====================================================================
\end{document}