rbtree.java

红黑树的java实现

红黑树是二叉搜索树中的一种，每个节点或黑或白，并满足一定的规则~Java中的TreeMap就是基于它实现的，这里只写一个简单的红黑树实现~

/*
* from CLR
* 用泛型表示红黑树的key值类型，Entry代表一个树节点的数据结构
* 左旋和右旋都是能保持二叉搜索树性质(左子树节点值小于父节点值，右子树节点值大于父节点值)的一个操作，很有用
* 在删除后对树的调整(为满足红黑树性质)需要防止空指针异常，所以后面定义了一组基本操作
*/
class RBTree<T>
{
private Entry<T> root = null;
private static final boolean RED = false;
private static final boolean BLACK = true;
//定义节点
static final class Entry<T>
{
   T keyValue;
   Entry<T> left = null;
   Entry<T> right = null;
   Entry<T> parent;
   boolean color = BLACK;

   Entry(T t, Entry<T> parent)
   {
    this.keyValue = t;
    this.parent = parent;
   }
}
//左旋
private void rotateLeft(Entry<T> p)
{
   if (p != null)
   {
    Entry<T> y = p.right;
    p.right = y.left;
    if (y.left != null)
     y.left.parent = p;
    y.parent = p.parent;
    if (p.parent == null)
     root = y;
    else if (p == p.parent.left)
     p.parent.left = y;
    else
     p.parent.right = y;
    y.left = p;
    p.parent = y;
   }
}
//右旋
private void rotateRight(Entry<T> p)
{
   if (p != null)
   {
    Entry<T> y = p.left;
    p.left = y.right;
    if (y.right != null)
     y.right.parent = p;
    y.parent = p.parent;
    if (p.parent == null)
     root = y;
    else if (p == p.parent.left)
     p.parent.left = y;
    else
     p.parent.right = y;
    y.right = p;
    p.parent = y;
   }
}
//找整棵树比自身key值大且最接近的节点，在删除节点中需要作替换
static <T> Entry<T> successor(Entry<T> p)
{
   if (p == null)
    return null;
   else if (p.right != null)
   {
    Entry<T> r = p.right;
    while (r.left != null)
     r = r.left;
    return r;
   }
   else
   {
    Entry<T> p0 = p.parent;
    while (p != null && p == p0.right)
    {
     p = p.parent;
     p0 = p0.parent;
    }
    return p0;
   }
}
//插入节点
public void rbInsert(T keyValue)
{
   if (keyValue == null)
    throw new NullPointerException();
   Entry<T> t = root;
   if (t == null)
   {
    root = new Entry(keyValue, null);
    return;
   }
   Entry<T> parent;
   Comparable<? super T> k = (Comparable<? super T>) keyValue;
   do
   {
    parent = t;
    if (k.compareTo(t.keyValue) < 0)
     t = t.left;
    else if (k.compareTo(t.keyValue) > 0)
     t = t.right;
    else
    {
     t.keyValue = keyValue;
     return;
    }
   }
   while (t != null);
   Entry<T> e = new Entry(keyValue, parent);
   if (k.compareTo(parent.keyValue) < 0)
    parent.left = e;
   else
    parent.right = e;
   e.color = RED;
   rbInsertFixup(e);
}
//插入节点后的修正红黑树性质操作
private void rbInsertFixup(Entry<T> p)
{
   while (colorOf(p.parent) == RED)
   {
    Entry<T> y;
    if (p.parent == p.parent.parent.left)
    {
     y = p.parent.parent.right;
     if (colorOf(y) == RED)
     {
      y.color = BLACK;
      p.parent.color = BLACK;
      p.parent.parent.color = RED;
      p = p.parent.parent;
     }
     else
     {
      if (p == p.parent.right)
      {
       p = p.parent;
       rotateLeft(p);
      }
      p.parent.color = BLACK;
      p.parent.parent.color = RED;
      rotateRight(p.parent.parent);
     }
    }
    else
    {
     y = p.parent.parent.left;
     if (colorOf(y) == RED)
     {
      y.color = BLACK;
      p.parent.color = BLACK;
      p.parent.parent.color = RED;
      p = p.parent.parent;
     }
     else
     {
      if (p == p.parent.left)
      {
       p = p.parent;
       rotateRight(p);
      }
      p.parent.color = BLACK;
      p.parent.parent.color = RED;
      rotateLeft(p.parent.parent);
     }
    }
   }
   root.color = BLACK;
}
//删除节点
public void rbDelete(T keyValue)
{
   Entry<T> p = getEntry(keyValue);
   if (p == null)
    return;
   Entry<T> y;
   Entry<T> x;
   if (p.left != null && p.right != null)
   {
    y = successor(p);
    p.keyValue = y.keyValue;
    p = y;
   }
   x = (p.left != null ? p.left : p.right);
   if (x != null)
   {
    x.parent = p.parent;
    if (p.parent == null)
     root = x;
    else if (p == p.parent.left)
     p.parent.left = x;
    else
     p.parent.right = x;
    p.parent = p.left = p.right = null;
    if (p.color == BLACK)
     rbDeleteFixup(x);
   }
   else
   {
    if (p.parent == null)
     root = null;
    else
    {
     if (p.color == BLACK)
      rbDeleteFixup(p);
     if (p == p.parent.left)
      p.parent.left = null;
     else
      p.parent.right = null;
     p.parent = null;
    }
   }
}
//根据key值查找节点
final Entry<T> getEntry(Object keyValue)
{
   if (keyValue == null)
    throw new NullPointerException();
   Comparable<? super T> k = (Comparable<? super T>) keyValue;
   Entry<T> r = root;
   while (r != null)
   {
    if (k.compareTo(r.keyValue) < 0)
     r = r.left;
    else if (k.compareTo(r.keyValue) > 0)
     r = r.right;
    else
     return r;
   }
   return null;
}
//删除节点后修正红黑树性质操作
private void rbDeleteFixup(Entry<T> p)
{
   while (p != root && colorOf(p) == BLACK)
   {
    Entry w;
    if (p == leftOf(parentOf(p)))
    {
     w = rightOf(parentOf(p));
     if (colorOf(w) == RED)
     {
      setColor(parentOf(p),RED);
      setColor(w,BLACK);
      rotateLeft(parentOf(p));
      w = rightOf(parentOf(p));
     }
     if (colorOf(leftOf(w)) == BLACK && colorOf(rightOf(w)) == BLACK)
     {
      setColor(w,RED);
      p = parentOf(p);
     }
     else
     {
      if (colorOf(rightOf(w)) == BLACK)
      {
       setColor(leftOf(w),RED);
       setColor(w,RED);
       rotateRight(w);
       w = rightOf(parentOf(p));
      }
      setColor(w,colorOf(parentOf(p))); 
      setColor(parentOf(p),BLACK);
      setColor(rightOf(w),BLACK);
      rotateLeft(parentOf(p));
      p = root;
     }
    }
    else
    {
     w = leftOf(parentOf(p));
     if (colorOf(w) == RED)
     {
      setColor(w,BLACK);
      setColor(parentOf(p),RED);
      rotateRight(parentOf(p));
      w = leftOf(parentOf(p));
     }
     if (colorOf(leftOf(w)) == BLACK && colorOf(rightOf(w)) == BLACK)
     {
      setColor(w, RED);
      p = parentOf(p);
     }
     else
     {
      if (colorOf(leftOf(w)) == BLACK)
      {
       setColor(rightOf(w),BLACK);
       setColor(w,RED);
       rotateLeft(w);
       w = leftOf(parentOf(p));
      }
      setColor(w,colorOf(parentOf(p)));
      setColor(parentOf(p), BLACK);
      setColor(leftOf(w), BLACK);
      rotateRight(parentOf(p));
      p = root;
     }
    }
   }
   setColor(p,BLACK);
}
//定义一些基本操作
private static <T> boolean colorOf(Entry<T> p)
{
   return (p == null ? BLACK : p.color);
}

private static <T> Entry<T> leftOf(Entry<T> p)
{
   return (p == null ? null : p.left);
}

private static <T> Entry<T> rightOf(Entry<T> p)
{
   return (p == null ? null : p.right);
}

private static <T> Entry<T> parentOf(Entry<T> p)
{
   return (p == null ? null : p.parent);
}

private static <T> void setColor(Entry<T> p, boolean c)
{
   if (p != null)
    p.color = c;
}
}