アルゴリズムA 第11回


二分木

前回学んだ「二分木」は、データを挿入する順番によってできあがる 木の状態が変わってしまいます。 探索の手間があまりかからない O(log n) 状態もあれば、 探索の手間がかかる O(n)状態もありえます。


平衡木

AVL木

教科書p.243-p.252

二分探索木に、

すべて節において、左部分木と右部分木の高さの差が 1 以内に収まらなければ ならない、
という制約を加えたものです。

一重回転

  1. 高さの差が1の木があったとき(図1a)
  2. 部分木Xに追加されると高さの差が2になる。(図1b)
  3. ノードAの親をノードBとすれば高さの差が0になる。(図1c)
図1a 図1b 図1c

二重回転

  1. 高さの差が1の木があったとき(図1a)
  2. 部分木Yに追加されると高さの差が2になる。(図2b)
  3. 部分木Yの中をノードCと部分木Y1, Y2に分解して(図2c)
  4. ノードAの親をノードBとすれば高さの差が0になる。(図2d)
図2b 図2c 図2d

AVL木に新しい要素を挿入した時に起きる、木のバランス見直し/修正作業は、 要素を挿入した葉から根に向かって上向きに伝播していきます。(p.250 Fig.10.4)

具体的な操作の例は p.251 Fig.10.5


B木 (B-tree)

教科書p.252-p.282

「二分木」においては節は最大2個の子までしか持てませんでしたが、 「多分木(multi-way tree)」では 節が最大m個 (m≧2)の子を持つことができます(m分木)。 「多分木(multi-way tree)」を使った探索木を 「多分探索木(multi-way search tree)」と呼びます。

「B木」とはm分探索木のうち、次の条件をみたすものです。(p.254,Fig.10.6参照)

  1. 根は、「葉である」か、あるいは「2〜m個の子を持つ節」である。
  2. 根、葉以外の節は、ceil(m/2)〜m個の子を持つ。
  3. 根からすべての葉までの経路の長さが等しい

ここで ceil(x)は「x以上で最も小さい整数」(=切り上げ)を表す。

B木では、データを保持するのは葉のみで、葉以外のノードはキーだけを保持します。 (二分探索木では、全てのノードがデータを保持していました。)

B木の構造

B木では、「葉でないNode (= 内部Node)」と 「葉」 の構造が異なります。 「内部ノードは右部分木のキーの最小値」を記録しています。 「葉」はキーと、「キーとデータの組」を交互に保持しています。

B木の探索

教科書p.255

最悪のケースは、どの節もceil(m/2) 個の子を持っている場合で、 この時のB木の高さはlogceil(m/2) n

最良のケースは、どの節もm個の子を持っている場合で、 この時のB木の高さは logm n

探索の計算量は木の高さに比例しますのでO(log n) で 実行できます。

B木への挿入

教科書p.256〜p.258

データを木の適切な場所に挿入する場合に、節に保持しているデータ(子)が m個を越えるとその節を2つの節に分割します(p.257 Fig.10.7参照)。 1つの節の分割においては、m/2個のデータを新しい節にコピー しなくてはならないので、その計算量はO(m) となります。

ある節を分割した結果、その上の節も保持するデータ(子)がm個を 越えて分割しなければいけなくなる場合が起こりえます。 根まで木を遡っていくと、O(log n) 個の節を 分割することになります。

したがって、挿入の計算量は O(log n) ×O(m)ですが、 mは定数であると見なせるので、結局 O(log n) であることがわかります。

B木からの削除

教科書p.258〜p.261

あるデータ(子) L を節 α から削除するには、基本的には αの中身を詰めなおすだけで済みます(P.259,Fig.10.8(a)(b))。

しかし、その結果αの子の個数が [(m+1)/2]を下まわってしまうと、 隣りの節から要素を分けてもらう必要がでてきます。 このときαとβで子を半分ずつにします。(p.260, Fig.10.8(c))

その結果βの子の個数が[(m+1)/2]未満になる場合は、αとβを 併合します。(p.260 Fig.10.8(d))

併合の結果、上の節のデータ(子)の個数が足りなくなることがありえます。 上でも節の併合がおきると影響はさらに上へと伝播していきます。

1個の節から子を削除するときの計算量はO( m )ですが、 それが O(log n) 回起きる可能性があるので、 mは定数とみて結局削除にはO(log n)の計算量が必要で あることがわかります。



アルゴリズムA 演習


課題提出〆切は、来週金曜日の13:00です。

課題11

提出先 http://nw.tsuda.ac.jp/class/algoA/local/handin/list.php?id=kadai11
提出ファイルBinarySearchArray.java
コメント欄:RunBinarySearchArray.javaにbsearch03.txtを入力として与えた時の出力

配列で「二分探索木」を表現することができます。 配列のインデックスを1から数えるとして、 「親ノード」のインデックスをkとすると、「左部分木の子ノード」は 2*k, 「右部分木の子ノード」は 2*k+1にすればよいのです。

BinarySearchArray.java の欠けている部分を自分でコードを書きなさい。

BinarySearchArray.java

// ノードに
//     根からの距離が小さい順に、
//     根からの距離が同じ場合は左から
// 番号をつけると、左端のノードの番号は 2のn乗。
// 親ノードの番号をnとすると子ノードは  2n(左)と2n+1(右)。
// ノード番号mの親ノードの番号は m/2
//      1
//     2 3 
//   4 5 6 7
//  .. .. .. .. 
public class BinarySearchArray {
    private Integer[] a;
    public BinarySearchArray() { this(128); }
    public BinarySearchArray(int n) { // 配列[0]は使わない(分かりやすさのため)
	a = new Integer[n+1];
	for (int i=0; i<a.length; i++) a[i] = null;
    }
    private int leftIndex(int n) { return 2*n; }
    private int rightIndex(int n) { return 2*n+1; }
    private int parentIndex(int n) { return n/2; }
    public Integer getData(int idx) { return a[idx]; }
    public int search(Integer key) {
	int idx=1;
	while (a[idx] != null) {
	    int result = key.compareTo(a[idx]);
	    if (result == 0) {	// 発見した場合
		return idx;
	    } else if (result < 0) { // 左の子へ
		idx = leftIndex(idx);
	    } else {		// 右の子へ
		idx = rightIndex(idx);
	    }
	}
	return -1;		// 発見できず
    }
    public int insert(Integer key) {
	int idx=1;

	// 自分で考えてコードを書きなさい。

	return idx;		// 登録したノード番号を返す
    }
    void move(int src,int dst) {
	if (a[src]==null) return;
	a[dst] = a[src];
	a[src] = null;
	move(leftIndex(src),leftIndex(dst));
	move(rightIndex(src),rightIndex(dst));
    }
    Integer deleteMin(int idx) {
	while (a[idx] != null) idx = leftIndex(idx);
	Integer ans = a[parentIndex(idx)];
	int pidx = parentIndex(idx);
	a[pidx] = null;
	move(rightIndex(pidx),pidx);
	return ans;
    }
    public int delete(Integer key) {
	int idx=1;
	while (a[idx] != null) {
	    int result = key.compareTo(a[idx]);
	    if (result == 0) {	// 発見した場合
		if (a[leftIndex(idx)]==null && a[rightIndex(idx)]==null) {
		    a[idx]=null;
		} else if (a[leftIndex(idx)]==null) {
		    move(rightIndex(idx),idx);
		} else if (a[rightIndex(idx)]==null) {
		    move(leftIndex(idx),idx);
		} else {
		    a[idx] = deleteMin(rightIndex(idx));
		}
		return idx;
	    } else if (result < 0) { // 左の子へ
		idx = leftIndex(idx);
	    } else {		// 右の子へ
		idx = rightIndex(idx);
	    }
	}
	return -1;		// 発見できず
    }
    private static String getSpaces(int n) {
	String s="";
	for (int i=0; i<n; i++) s += " ";
	return s;
    }
    public String prettyPrint() { return prettyPrint(0,1); }
    public String prettyPrint(int n,int idx) {
	if (a[idx]==null) return getSpaces(n) + "null\n";
	String s = "";
	s += prettyPrint(n+2,rightIndex(idx));
	s += getSpaces(n) + a[idx] + "\n";
	s += prettyPrint(n+2,leftIndex(idx));
	return s;
    }
}
RunBinarySearchArray.java

授業で配布するプリントを参照して下さい。
RunBinarySearchArray.javaの実行例

% javac RunBinarySearchArray.java BinarySearchArray.java
% java RunBinarySearchArray < bsearch01.txt
      null
    15
        null
      13
        null
  11
      null
    9
      null
7
        null
      6
        null
    5
      null
  3
      null
    2
        null
      1
        null

---------
...(略)
bsearch03.txt

insert 7
insert 3
insert 11
insert 5
insert 2
insert 9
insert 20
insert 13
insert 1
insert 6
insert 14
insert 16
show
delete 2
show 
delete 5
show
delete 11
show