コンピュータ基礎演習 ー二分探索木ー

コンピュータ基礎演習�
�ー二分探索木ー�
岩井�儀雄�
[email protected]�
2分探索木�
(binary search tree)�
 
 
任意の節xで，左部分木TL(x)に含ま
れる要素Nは節Xの要素N(x)より
小さい．�
右部分木TR(x)に含まれる要素Nは
節xの要素N(x)より大きい．�
例） a < b < c <d
c
右部分木�
左部分木�
a
d
b
∀x, l, r l ∈ T L(x), r ∈ T R(x) ⇒ N(l) < N(x) ∧ N(x) < N(r)
2分探索木の利点�
 
 
順序 < が定義された集合を表現可�
集合への追加，削除，探索などの操作が O
(log n) で可能�
Strict Partial Order < �
 
非反射律: irreflexivity�
∀x x < x must be false
 
推移律：transivity�
∀x,y,z x < y ∧ y < z ⇒ x < z
上の2つの条件を満たす2項関係を
strict partial order （狭義半順序）という�
同値 equivalence "~"�
 
反射律: reflexivity�
∀x x ~ x
 
 
対称律: symmetry�
∀x x ~ y ⇔ y ~ x
推移律： transitivity�
∀x x ~ y ∧ y ~ z ⇒ x ~ z
2分探索木の操作�
 
探索 (search)�
 
 
挿入 (insert)�
 
 
指定された要素と等価な要素の位置を返す�
指定された要素と等価な要素を2分探索木の
条件を満たすように挿入する�
削除 (erase)�
 
指定された要素と等価な要素を2分探索木の
条件を満たすように削除する�
2分探索木の実装（C言語）�
struct NODE {
DATATYPE data;
struct NODE *leftchild; /* 左の子へのポインタ */
struct NODE *rightchild; /* 右の子へのポインタ */
};
2分探索木で必要な演算
�データ要素を順序づける演算 ‘<’ (strict partial order)
�データが等価かどうかの演算 ‘~’ (equivalence)
int lessthan(DATATYPE a, DATATYPE b); /* 偽なら0，真なら!0 */
int equal(DATATYPE a, DATATYPE b);
/* 偽なら0，真なら!0 */
探索(search)の実装�
 
 
 
 
struct
if
if
if
現在の節の要素と等しい→探索終わり�
現在の節の要素より小さい→左部分木を探索�
現在の節の要素より大きい→右部分木を探索�
節がない→要素なし(NULLを返す)�
NODE *search(DATATYPE data,struct NODE *node) {
(node == NULL) return NULL; /* データなし */
(equal(data,node->data)) return node; /* データ発見 */
(lessthan(data,node->data))
return search(data,node->leftchild); /* 左部分木を探索 */
else return search(data,node->rightchild); /* 右部分木を探索 */
}
挿入(insert)の実装（C言語）�
struct NODE *create(DATATYPE data) { /* 新規ノード作成 */
struct NODE *p = (struct NODE *)malloc(sizeof(struct NODE));
node->data = data; node->leftchild = node->rightchild = NULL;
return p;
}
struct
if
if
if
NODE *insert(DATATYPE data,struct NODE *node) {
(node == NULL) return create(data);
/* 新規データ */
(equal(data,node->data)) return node; /* 既にデータあり */
(lessthan(data,node->data))
node->leftchild = insert( data, node->leftchild );
else node->rightchild = insert( data, node->rightchild );
return node;
}
削除(erase)の実装�
 
 
削除すべき要素が葉ならば削除�
削除すべき要素が内部節ならば問題�
 
 
右部分木の最小値をその削除すべき要素と置き換える．�
右部分木の最小値があった位置は1つ以下の子なので削除可�
d
この節を単純に削除
すると木が壊れる�
b
a
e
c
この節は葉であるから
単純に削除OK
削除(erase)の実装�
 
 
削除すべき要素が葉ならば削除�
削除すべき要素が内部節ならば問題�
 
 
右部分木の最小値をその削除すべき要素と置き換える．�
右部分木の最小値があった位置は1つ以下の子なので削除可�
d
右部分木の最小値と入替�
a
c
e
d
この節は葉であるから
単純に削除OK
右部分木の最小値をその削除すべき要
素と置き換える�
 
2分探索木の条件�
∀x, l, r l ∈ T L(x), r ∈ T R(x) ⇒ N(l) < N(x) ∧ N(x) < N(r)
削除対象の節を x，右部分木TRの最小値を m とすると，�
N(x) < m < N(r), ∀r ∈ T R(x)
∀l, r l ∈ T L(x), r ∈ T R(x) ⇒ N(l) < m ∧ m < N(r)
2分探索木の条件を壊さないことが分かる�
木の最小値を削除しその値を返
す�
 
 
右部分木の根を渡せば，右部分木の最小値を削除できる．�
返り値で削除対象節の値を書き換える�
data
min
最小値の左の子はいない�
data
木の最小値を削除しその値を返
す�
 
 
右部分木の根を渡せば，右部分木の最小値を削除できる．�
返り値で削除対象節の値を書き換える�
data
min
最小値の左の子はいない�
data
木の最小値を削除しその値を返
す(C言語)�
struct NODE *erasemin(struct NODE **node) {
if ((*node)->leftchild == NULL) {
struct NODE *ret = *node;
/* 返り値 */
*node = (*node)->rightchild; /* ポインタ変更 */
ret->rightchild = NULL;
return ret; /* 削除した節を返す */
} else
return erasemin( &((*node)->leftchild) );
}
要素の削除（C言語）�
struct NODE *erase( DATATYPE data, struct NODE **node ) {
struct NODE *x = *node;
if (x == NULL) return NULL;
if (equal(data,x->data)) { /* 等価なデータ発見，削除 */
/* 子の有無を調査，１つだけならそのままつなぐ */
if (x->leftchild == NULL) *node = x->rightchild;
else if (x->rightchild == NULL) *node = x->leftchild;
else { /* 両側に子がある場合は erasemin を呼ぶ */
x = erasemin( &x->rightchild );
(*node)->data = x->data;
}
x->leftchild = x->rightchild = NULL;
return x;
} else if (lessthan(data,x->data))
return erase( data, &x->leftchild) ); /* 左部分木を探索 */
else
return erase( data, &x->rightchild) ); /* 右部分木を探索 */
}