平衡木（赤黒木）

ランダム化BSTとスプレイ木はどちらも特殊な探索が線形時間となる可能性がある。そのため、根から外部節点への距離がすべて等しくなるような木構造を考える。

2分探索木のノードに赤か黒の色をつけ、以下の条件を満たすものを赤黒木と呼ぶ

ノードは赤か黒
根は黒
全ての葉は黒
赤いノードの子は黒
全ての葉から根までのパスには同じ個数の黒いノードがある

上記条件より、最短パスは黒ノードだけを含み、最長パスには赤黒が交互に含まれることになる。最短パスと最長パスが2倍を超えないようにバランスをとる。
全てのノードに赤を示す1bitを加える。

挿入するノードの親の親が黒でその子（親）が二つとも赤と赤の場合、親の親の色を赤に変更し、親二つのノードを黒にする。また親の親と親のノードが共に赤の場合、回転を使用し親の親を親の子ノードに移動、親を黒にすればよい。
詳細の説明は以下サイトが分かりやすい。

http://www.geocities.jp/h2fujimura/mutter/tree/red-black-tree.html

次のプログラムは赤黒木への挿入のプログラム。木を下るときに（再帰呼び出しの前）４節点の色替えを実行し、木をさかのぼるときに（再帰呼び出しの後）回転を実行できるようにする。
※再帰呼び出しの後、値として帰ってきたリンクを設定し、回転が必要かチェックする。探索路に同じ向きの赤いリンクが二つ並べば上から単回転を行い、色替えをする。二つの赤いリンクの向きが異なっていれば、下から単回転を行う。

#include <stdio.h>
#include <stdlib.h>
#include "Item.h"
#include "ST.h"

typedef struct STnode *link;
struct STnode {
    Item item;
    link l;
    link r;
    unsigned int red: 1;
    int N;
};

static link head, z;


static link NEW(Item item, link l, link r, int red, int N)
{
    link x = malloc(sizeof *x);
    x->item = item;
    x->l = l;
    x->r = r;
    x->red = red;
    x->N = N;
    return x;
}

void STinit(int maxN)
{
    head = (z = NEW(NULLitem, 0, 0, 0, 0));
}


link RBinsert(link h, Item item, int sw)
{
    Key v = key(item);
    if (h == z)
        return NEW(item, z, z, 1, 1);
    if ((h->l->red) && (h->r->red)) {
        h->red = 1;
        h->l->red = 0;
        h->r->red = 0;
    }
    if (less(v, key(h->item))) {
        h->l = RBinsert(h->l, item, 0);
        if (h->red && h->l->red && sw)
            h = rotR(h);
        if (h->l->red && h->l->l->red) {
            h = rotR(h);
            h->red = 0;
            h->r->red = 1;
        }
    } else {
        h->r = RBinsert(h->r, item, 1);
        if (h->red && h->r->red && !sw)
            h = rotL(h);
        if (h->r->red && h->r->r->red) {
            h = rotL(h);
            h->red = 0;
            h->l->red = 1;
        }
    }
    return h;
}

void STinsert(Item item)
{
    head = RBinsert(head, item, 0);
    head->red = 0;
    // debug
    STsort(ITEMshow);
}