根への挿入,BSTの選択、分割、削除

根への挿入

BSTの標準的な実現では新しい節点は木の底だが、次のプログラムはトップに配置する。これを実現する為に、木に対して回転を行う。
右回転は根を右側におく。根の左リンクは回転前は根から左の個へ向いているが回転後は、左の子（新しい根）から古い根（新しい根の右の子）へ向いている。また、左の子（新しい根）の右リンクを古い根の左リンクへコピーする。そして、親から古い根へのリンクは新しい根へのリンクを変更される。
左回転は右回転の動作を逆にしたもの。
回転操作を使うと、根への挿入を砂青に再帰的に実現できる。新しい項目を適当な部分木に再帰的に挿入し、回転によってその根を全体の根にする。

BSTにおける回転のプログラム

link rotR(link h)
{
    link x = h->l;
    h->l = x->r;
    x->r = h;
    return x;
}

link rotL(link h)
{
    link x = h->r;
    h->r = x->l;
    x->l = h;
    return x;
}

BSTの根への挿入のプログラム

link insertT(link h, Item item)
{
    Key v = key(item);
    if (h == z)
        return NEW(item, z, z, 1);
    if (less(v, key(h->item))) {
        h->l = insertT(h->l, item);
        h = rotR(h);
    } else {
        h->r = insertT(h->r, item);
        h = rotL(h);
    }
    return h;
}
    
void STinsert(Item item)
{
    head = insertT(head, item);
}

選択

BST中のk番目のキーを見つけるには左部分木中の節点の個数を調べれば良い。個数がk-1個なら、根にある項目を返せば良い。k個より多ければ、左部分木でk番目のキーを返せばよい。そのどちらでも無い場合は左部分木中のキーはt(

Item selectR(link h, int k)
{
    int t;
    if (h == z)
        return NULLitem;
    t = (h->l == z) ? 0 : h->l->N;
    if (t > k)
        return selectR(h->l, k);
    if (t < k)
        return selectR(h->r, k-t-1);

    return h->item;
}

Item STselect(int k)
{
    return selectR(head, k);
}

上のselectの操作をpartition操作に変更することができる。再帰呼び出しの後に回転を付け加えることでBSTを選択された項目を根に置いて分割するようになる。

link partR(link h, int k)
{
    int t = h->l->N;
    if (t > k) {
        h->l = partR(h->l, k);
        h = rotR(h);
    }
    if (t < k) {
        h->r = partR(h->r, k-t-1);
        h = rotL(h);
    }
    return h;
}

削除

削除対象のキーvを持つ節点で最初に出会う節点を削除する。下に向かって行きながら削除される節点が根になるまで適当な部分木に対して再帰的に呼び出される。それから、その節点をその節点の二つの部分木を結合した木と置き換える。結合した木は、右部分木中で最小のキーが根となり、その左リンクは左部分木を指す。

link joinLR(link a, link b)
{
    if (b == z)
        return a;
    b = partR(b, 0); // 右部分木で最小の要素を根に引き上げる
    b->l = a;
    return b;
}

link deleteR(link h, Key v)
{
    link x;
    Key t = key(h->item);
    if (h == z)
        return z;
    if (less(v, t))
        h->l = deleteR(h->l, v);
    if (less(t, v))
        h->r = deleteR(h->r, v);
    if (eq(v, t)) {
        x = h;
        h = joinLR(h->l, h->r);
        free(x);
    }
    return h;
}

void STdelete(Key v)
{
    head = deleteR(head, v);
}