memory pool and rb-tree

[BLS]

BLS schrieb:

> 
> Hi Steve
> In 2008, Sedgewick introduced a simpler version of red-black trees.
> So called Left-Leaning Red-Black Trees. Remarkable enough : This algo. 
> requires just a few lines of code (compared to traditional 
> implementations), is dammned fast, and looks pretty smart. Probabely 
> interesting for you / DCollections. So here two links.

Can't resist :)
*traditional code insert() :

private Node insert(Node x, Key key, Value val, boolean sw)
{
if (x == null)
return new Node(key, value, RED);
int cmp = key.compareTo(x.key);
if (isRed(x.left) && isRed(x.right))
{
x.color = RED;
x.left.color = BLACK;
x.right.color = BLACK;
}
if (cmp == 0) x.val = val;
else if (cmp < 0))
{
x.left = insert(x.left, key, val, false);
if (isRed(x) && isRed(x.left) && sw)
x = rotR(x);
if (isRed(x.left) && isRed(x.left.left))
{
x = rotR(x);
x.color = BLACK; x.right.color = RED;
}
}
else // if (cmp > 0)
{
x.right = insert(x.right, key, val, true);
if (isRed(h) && isRed(x.right) && !sw)
x = rotL(x);
if (isRed(h.right) && isRed(h.right.right))
{
x = rotL(x);
x.color = BLACK; x.left.color = RED;
}
}
return x;
}

*LL RB TREE INSERT
private Node insert(Node h, Key key, Value val)
{
if (h == null)
return new Node(key, val, RED);
int cmp = key.compareTo(h.key);
if (cmp == 0) h.val = val;
else if (cmp < 0)
h.left = insert(h.left, key, val);
else
h.right = insert(h.right, key, val);
if (isRed(h.right))
h = rotateLeft(h);
if (isRed(h.left) && isRed(h.left.left))
h = rotateRight(h);
if (isRed(h.left) && isRed(h.right))
colorFlip(h);
return h;
}
YEP