応用情報技術者 2015年 秋期 午後 問03

　 　2分探索木とは、全てのノードNに対して、次の条件が成立している2分木のことである。 　・Nの左部分木にある全てのノードのキー値は、Nのキー値よりも小さい。 　・Nの右部分木にある全てのノードのキー値は、Nのキー値よりも大きい。 　ここで、ノードのキー値は自然数で重複しないものとする。2分探索木の例を図1に示す。図中の数はキー値を表している。

　2分探索木を実現するために、ノードを表す構造体Nodeを定義する。構造体Nodeの構成要素を表1に示す。

　構造体の実体を生成するためには、次のように書く。 　new Node(key) 　生成した構造体への参照が戻り値となる。構造体の構成要素のうち、keyは引数keyの値で初期化され、leftとrightはnullで初期化される。 　変数pが参照するノードをノードpという。ノードを参照する変数からそのノードドの構成要素へのアクセスには“.”を用いる。例えば、ノード p のキー値には、p.key でアクセスできる。 　なお、変数 p の値が null の場合、木は空である。 　

〔2分探索木でのノードの探索〕 　与えられたキー値をもつノードを探索する場合、親から子の方向へ、木を順次たどりながら探索を行う。 　探索する 2 分探索木にノードがない場合は、目的のノードが見つからず、探索は失敗と判断して終了する。探索する 2 分探索木にノードがある場合は、与えられたキー値と木の根のキー値を比較し、等しければ、目的のノードが見つかったので探索は成功と判断して終了する。与えられたキー値の方が小さければ左部分木に、大きければ右部分木に移動する。移動先の部分木でも同様に探索を続ける。 　この手順によって探索を行う関数 search のプログラムを図2に示す。このプログラムでは、探索が成功した場合は見つかったノードへの参照を返し、失敗した場合は null を返す。

〔2 分探索木へのノードの挿入〕 　2 分探索木にノードを挿入する場合、探索と同様に、親から子の方向へ、木を順次たどりながら、適切な位置にノードを挿入する。 　挿入する 2 分探索木にノードがない場合は、挿入するキー値のノードを作成する。挿入する2分探索木にノードがある場合は、挿入するキー値と木の根のキー値を比較し、挿入するキー値の方が小さければ左部分木に、大きければ右部分木に移動する。移動先の部分木でも同様の処理を続ける。 　この手順によって挿入を行う関数 addNode のプログラムを図3に示す。このプログラムでは、挿入の結果として得られた2分探索木の根のノードへの参照を返す。ただし、このプログラムは、挿入するキー値と同じキー値をもつノードが2分探索木に既に存在するときは何もしない。

〔2分探索木からのノードの削除〕 　2分探索木から、あるキー値をもつノードを削除する場合、次の（1）～（3）の手順を行う。

（1）2分探索木にノードがない場合は、何もしないで処理を終了する。 （2）削除するキー値と木の根のキー値を比較し、削除するキー値の方が小さければ左部分木に、大きければ右部分木に移動する。移動先の部分木でも同様の処理を続ける。 （3）削除するキー値と木の根のキー値が等しい場合、削除するキー値をもつノードを削除するため、次の（3-1）～（3-3）を実行する。 　（3-1）削除するノードが子ノードをもたない場合、そのノードを削除する。 　（3-2）削除するノードがノードを一つだけもつ場合、削除するノードの位置にその子ノードを置く。 　（3-3）削除するノードが左右両方に子ノードをもつ場合、削除するノードの左部分木の中で最大のキー値をもつノードを左部分木から取り除き、削除するノードの位置に置く。 　 　この手順を使って2分探索木からノードの削除を行う関数removeNodeのプログラムを図4に示す。このプログラムでは、削除した後の2分探索木の根のノードへの参照を返す。ただし、このプログラムは、削除するキー値をもつノードが2分探索木に存在しないときは何もしない。 　図4中の関数extractMaxNodeは、引数で指定されたノードを根とする2分探索木の中で最大のキー値をもつノードを木から削除し、削除されたノードへの参照を大域変数extractedNodeに設定した上で、削除した後の2分探索木の根のノードへの参照を返す。関数extractMaxNodeのプログラムを図5に示す。

〔2分探素木の計算量〕 　2分探素木における計算量は、木の高さに依存する。図2の関数searchを使ってn個のノードから成る2分探索木を探索する場合、想定される最大の計算量は、O(ク)である。木構造が完全2分木であれば、その計算量は最大でもO(ケ)である。