rbtree.cc

#include <stdio.h>
#include <vector>
#include <iostream>
#include <cassert>


template <typename T>
struct rbtree
{
  enum Color {
    RED,
    BLACK
    };
  struct node 
  {
    int key;
    Color color;
    node *right, *left, *p;
  };
  node* root;
  
  node* search(int key)
  {
    node *x = root;
    assert(x!=NULL);
    while(x!=NULL) {
      if (x->key < key) {
	x = x->left;
      }
      if (x->key > key) {
	x = x->right;
      }
      else {
	assert(x.key==key);
	return x;
      }
    }
    assert(x==NULL);
  }


  /* RightRotate
x <- y.left
y.left <- x.right

if x.right != nil then
  x.right.p <- y
x.p = y.p

if y.p == nil then
  root = x
else if y == y.p.left then
  y.p.left <- x
else 
  y.p.right <- x

x.right <- y
y.p <- x
   */
  void right_rotate(int key) 
  {
    node* y = search(key);
    node* x = y->left;
    assert(x->key < y->key < y->right->key);
    if (x->right != NULL) {
      x->right->p = y;
    }
    x->p = y->p;
    
    if (y->p == NULL) {
      y->p->left = x;
    }
    else if (y==y->p->left) {
      y->p->left = x;
    }
    else {
      y->p->ritght = x;
    }
    x->right = y;
    y->p = x;
    assert(x->left->key < x-key < y->key);
  }



  /*
    LeftRotate

y <- x.right
x.right <- y.left

if y.left != nil then
  y.left.p <- x
y.p <- x.p

if x.p == nil then
  root <- y
else if x == x.p.left then
  x.p.left <- y
else
  x.p.right <- y

y.left <- x
x.p <- y

   */

  void left_rotate(int key) 
  {
    node* x = search(key);
    node* y = x.right;
    assert(x->left->key < x-key < y->key);

    if (y->left != NULL) {
      y->left->p = x;
    }
    y->p = x->p;
    if (x->p==NULL) {
      root = y;
    }
    else if (x==x->p->left) {
      x->p->left = y;
    }
    else  {
      x->p->right = y;
    }
     
    y->left = x;
    x->p = y;
    assert(x->key < y->key < y->right->key);
  }

  /*
    insert
    
    y <- nil
    x <- root

    while  x!= nil do
      y <- x
       if z.key < x.key then
         x <- x.left
       else
         x <- x.right

    x.p <- y
    if y == nil then
    else if
      z.key < y.key then
        y.left = z
      else
        y.right = z
    z.left = nil
    z.right = nil
    z.color = RED
    insrt(z)
         
    

   */
  void insert(int key)
  {
    node* z = new node;
    node->key = key;
    // find poind
    while (x!=NULL) {
      node* y = x;
      if (z->key < x->key) {
	x = x->left;
      }
      else {
	x = x->right;
      }
      
      // root?  left or right?
      x->p = y;
      if (y==NULL) {
	root = y;
      }
      else if (z->key < y->key) {
	y->left = z;
      }
      else {
	y->right = z;
      }
    }
    z->left = NULL;
    z->left = NULL;
    z->Color = RED;

    fixup(z);
    
    
    assert(z->left->key < z->key < z->right->key);
  }
  /*
    fixup
    while z.p.color = RED do
      if z->p <- z->p->p->left then
        y = z.p.p.right
	  if y.color == RED then
	    z.p.color = BLACK
	    y.color = BLACK
	    z.p.p.color = RED
	    z = z.p.p
	  else if z == z.p.right then
	    z = z.p
	    leftrotate(z)
	  z.p.color = black
	  z.p.p.color = red
	  rightrotate(z.p.p)
       else 
    root.color = black
      
   */
  void fixup(node* z)
  {
    
  }
 
};