二分探索木/Binary-Search-Tree 削除/Delete ｃ＋＋
ハトムギです。
前回に引き続き、二分探索木について書きます。
今回は、指定したkeyを持つnodeの削除について書きます。
二分探索木とは
探索木の中でももっとも基本的なものが、二分探索木です
簡単に説明するとその名の通り、根から枝が二つに分かれ、また各節点から二つに分かれを繰り返します。
今回は、あるnodeのkeyより値の小さいnodeは左側に、大きいnodeは右側にくるように実装しました。
各nodeは、key, 親、左の子、右の子をメンバにもつ構造体により実装できます。
struct Node {
int key;
Node* p, * l, * r;
};
二分探索木・削除
void del(node *u, int k)
まず、ｋをkeyにもつnodeを探索します。
while (u != NULL && u->key != k) {
if (u->key < k) u = u->r;
else u = u->l;
}
if (u == NULL)return;
また、消したいnodeが親の左の子か右の子かをrorl２保存しておきましょう。
int which = le;
if (u->p->l!=NULL&&u->p->l->key == k)which = le;
else if(u->p->r!=NULL&&u->p->r->key==k) which = ri;
つぎに、消したいnodeが持っている子の数で場合分けをします。
if (u->l == NULL && u->r == NULL) {
deln2(u, k,which);
}
else if (u->l != NULL && u->r != NULL) {
deln0(u, k, which);
}
else deln1(u, k, which);
}
子を持たない場合 del0( node *u, int k, int rorl)
方針は、親からのポインタをNULLにし、子から親を指すポインタもNULLにするだけです。
void deln0(node* u,int k, int which) {
if (which)u->p->r = NULL;
else u->p->l = NULL;
u->p = NULL;
}
子を一つ持つ場合 del1( node *u, int k, int rorl)
方針は、
消したいnodeの子が左であるか右であるかで場合分けをする。
次に、消したいnodeの子の親を指すポインタを消したいnodeの親を指すポインタにする。
また、消したいnodeが左の子か右の子か場合分けする。
次に、消したいnodeの親の子を指すポインタを消したいnodeの子を指すポインタにする。
最後に消したいnodeの親、子を指すポインタをNULLにする。
void deln1(node* u, int k, int which) {
if (u->l != NULL) {
u->l->p = u->p;
if (which)u->p->r = u->l;
else u->p->l = u->l;
u->p = NULL;
u->l = NULL;
}
else {
u->r->p = u->p;
if (which)u->p->r = u->r;
else u->p->l = u->r;
u->p = NULL;
u->r = NULL;
}
}
子を二つ持つ場合 del2 ( node*u, int k, int rorl)
子を二つ持つ場合が一番難しいです。
方針としは、消したいnodeの次節点nodeのkeyを消したいnodeにコピーして、次節点nodeを削除します。
ここで、次節点とは中間順巡回で消したいnodeの次に得られる節点のことです。
次節点を見つけられたら、次節点nodeがもつ子の数で場合分けをして、del0,del1,del2,を呼び出したらできます。
次節点を見つける。node * getsuc(node*u)
u の次節点を見つけて、その節点へのポインタを返す関数を考えます。
u が右の子を持っている場合、右の子から派生してくる部分木のなかで、最小のkeyを持つnodeが次節点になります。
最小のkeyは今回の木の構造が、左の子は親より小さいkeyを持ち、右の子は親より大きいkeyを持つので左の子をたどっていけば求められます。
node* getmin(node* u) {
while (u->l != NULL) {
u = u->l;
}
return u;
}
uが右の子を持たない場合、uの親を遡っていき、初めて左の子になっているnodeの親がuの次節点になります。
node * getsuc(node* u) {
if (u->r != NULL) return getmin(u->r);
else {
node* y = u->p;
while (y != NULL && u == y->r) {
u = y;
y = y->p;
}
return y;
}
}
ここで、新たに消したいnodeができたので、その子の数で場合分けしてそれぞれ関数を呼び出します。
void deln0(node* u, int k, int which) {
node* y = getsuc(u);
u->key = y->key;
if (y->p->l == y)which = le;
else if (y->p->r == y)which = ri;
if (y->l == NULL && y->r == NULL)deln0(y, y->key,which);
else if (y->l != NULL && y->r != NULL) deln2(y, y->key, which);
else deln1(y, y->key, which);
}
