changeset 81:dc6f665bb753

implement delete(tail call). do not work
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Fri, 11 Dec 2015 15:06:20 +0900
parents 099d85f9d371
children 69d0637e52fd
files src/llrb/CMakeLists.txt src/llrb/compare.c src/llrb/llrb.c src/llrb/llrbContext.c src/llrb/llrbContext.h src/llrb/main.c src/llrb/stack.c
diffstat 7 files changed, 467 insertions(+), 477 deletions(-) [+]
line wrap: on
line diff
--- a/src/llrb/CMakeLists.txt	Mon Nov 30 21:40:50 2015 +0900
+++ b/src/llrb/CMakeLists.txt	Fri Dec 11 15:06:20 2015 +0900
@@ -1,5 +1,7 @@
 cmake_minimum_required(VERSION 2.8)
 
+add_definitions("-Wall -g -O0")
+
 set(CMAKE_C_COMPILER $ENV{CbC_Clang}/clang)
 
 add_executable(llrb
--- a/src/llrb/compare.c	Mon Nov 30 21:40:50 2015 +0900
+++ b/src/llrb/compare.c	Fri Dec 11 15:06:20 2015 +0900
@@ -2,10 +2,10 @@
 
 void compare(struct Context* context, struct Tree* tree, int key1, int key2) {
     if (key1 == key2) {
-        tree->result = 0;
+        tree->result = EQ;
     } else if (key1 < key2) {
-        tree->result = 1;
+        tree->result = GT;
     } else {
-        tree->result = -1;
+        tree->result = LT;
     }
 }
--- a/src/llrb/llrb.c	Mon Nov 30 21:40:50 2015 +0900
+++ b/src/llrb/llrb.c	Fri Dec 11 15:06:20 2015 +0900
@@ -8,15 +8,16 @@
 
 extern int num;
 
-__code put(struct Context* context, struct Tree* tree, struct Allocate* allocate) {
+__code put(struct Context* context, struct Tree* tree, struct Node* root, struct Allocate* allocate) {
     allocate->size = sizeof(struct Node);
     allocator(context);
-
+    
     stack_push(context->code_stack, &context->next);
 
-    if (tree->root) {
-        tree->current = tree->root;
-        tree->root = &context->data[context->dataNum]->node;
+    tree->root = &context->data[context->dataNum]->node;
+    
+    if (root) {
+        tree->current = root;
         compare(context, tree, tree->current->key, context->data[Node]->node.key);
 
         goto meta(context, Replace);
@@ -26,18 +27,18 @@
 }
 
 __code put_stub(struct Context* context) {
-    goto put(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate);
+    goto put(context, &context->data[Tree]->tree, context->data[Tree]->tree.root, &context->data[Allocate]->allocate);
 }
 
 __code replaceNode(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) {
     *newNode = *oldNode;
 
-    if (result == 0) {
+    if (result == EQ) {
         newNode->value = context->data[Node]->node.value;
 
         stack_pop(context->code_stack, &context->next);
         goto meta(context, context->next);
-    } else if (result == 1) {
+    } else if (result == GT) {
         tree->current = oldNode->right;
         newNode->right = context->heap;
     } else {
@@ -68,140 +69,153 @@
     
     tree->current = newNode;
 
-    goto meta(context, Balance1);
+    goto meta(context, InsertCase1);
 }
 
 __code insertNode_stub(struct Context* context) {
     goto insertNode(context, &context->data[Tree]->tree, &context->data[Node]->node, &context->data[context->dataNum]->node);
 }
 
-__code balance1(struct Context* context, struct Node* current) {
-    if (current->parent == 0) {
-        current->color = Black;
-        
-        stack_pop(context->code_stack, &context->next);
-        goto meta(context, context->next);
-    } else {
-        goto meta(context, Balance2);
-    }
+__code insertCase1(struct Context* context, struct Tree* tree, struct Node* current) {
+    if (current->parent)
+        goto meta(context, InsertCase2);
+
+    tree->root->color = Black;
+    tree->current = 0;
+
+    stack_pop(context->code_stack, &context->next);
+    goto meta(context, context->next);
+}
+
+__code insert1_stub(struct Context* context) {
+    goto insertCase1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
 }
 
-__code balance1_stub(struct Context* context) {
-    goto balance1(context, context->data[Tree]->tree.current);
+__code insertCase2(struct Context* context, struct Node* current) {
+    if (current->parent->color == Black) {
+        stack_pop(context->code_stack, &context->next);
+        goto meta(context, context->next);
+    }
+    
+    goto meta(context, InsertCase3);
 }
 
-__code balance2(struct Context* context, struct Node* current) {
-    if (current->parent->color == Black)
-        goto meta(context, SetRoot);
-    else
-        goto meta(context, Balance3);
+__code insert2_stub(struct Context* context) {
+    goto insertCase2(context, context->data[Tree]->tree.current);
 }
 
-__code balance2_stub(struct Context* context) {
-    goto balance2(context, context->data[Tree]->tree.current);
-}
-
-__code balance3(struct Context* context, struct Tree* tree, struct Node* current) {
+__code insertCase3(struct Context* context, struct Tree* tree, struct Node* current) {
     struct Node* uncle;
     struct Node* grandparent = current->parent->parent;
 
-    if (grandparent == 0)
-        uncle = 0;
-    
     if (grandparent->left == current->parent)
         uncle = grandparent->right;
     else
         uncle = grandparent->left;
-    
-    if ((uncle != 0) && (uncle->color == Red)) {
+
+    if (uncle && (uncle->color == Red)) {
         current->parent->color = Black;
         uncle->color = Black;
         grandparent->color = Red;
         tree->current = grandparent;
-        goto meta(context, Balance1);
-    } else {
-        goto meta(context, Balance4);
+        goto meta(context, InsertCase1);
     }
+
+    goto meta(context, InsertCase4);
 }
 
-__code balance3_stub(struct Context* context) {
-    goto balance3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
+__code insert3_stub(struct Context* context) {
+    goto insertCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
 }
 
-__code balance4(struct Context* context, struct Node* current) {
+__code insertCase4(struct Context* context, struct Node* current) {
     struct Node* grandparent = current->parent->parent;
 
     if ((current == current->parent->right) && (current->parent == grandparent->left)) {
-        context->next = Balance4_1;
+        context->next = InsertCase4_1;
 
         stack_push(context->code_stack, &context->next);
         goto meta(context, RotateL);
     } else if ((current == current->parent->left) && (current->parent == grandparent->right)) {
-        context->next = Balance4_2;
+        context->next = InsertCase4_2;
         
         stack_push(context->code_stack, &context->next);
         goto meta(context, RotateR);
     }
 
-    goto meta(context, Balance5);
+    goto meta(context, InsertCase5);
 }
 
-__code balance4_stub(struct Context* context) {
-    goto balance4(context, context->data[Tree]->tree.current);
+__code insert4_stub(struct Context* context) {
+    goto insertCase4(context, context->data[Tree]->tree.current);
 }
 
-__code balance4_1(struct Context* context, struct Tree* tree) {
+__code insertCase4_1(struct Context* context, struct Tree* tree) {
     tree->current = tree->current->left;
-    goto meta(context, Balance5);
+    goto meta(context, InsertCase5);
 }
 
-__code balance4_1_stub(struct Context* context) {
-    goto balance4_1(context, &context->data[Tree]->tree);
+__code insert4_1_stub(struct Context* context) {
+    goto insertCase4_1(context, &context->data[Tree]->tree);
 }   
 
-__code balance4_2(struct Context* context, struct Tree* tree) {
+__code insertCase4_2(struct Context* context, struct Tree* tree) {
     tree->current = tree->current->right;
-    goto meta(context, Balance5);
+    goto meta(context, InsertCase5);
 }
 
-__code balance4_2_stub(struct Context* context) {
-    goto balance4_2(context, &context->data[Tree]->tree);
+__code insert4_2_stub(struct Context* context) {
+    goto insertCase4_2(context, &context->data[Tree]->tree);
 }   
 
-__code balance5(struct Context* context, struct Tree* tree, struct Node* current) {
+__code insertCase5(struct Context* context, struct Tree* tree, struct Node* current) {
     current->parent->color = Black;
     current->parent->parent->color = Red;
 
     tree->current = current->parent->parent;
 
+    context->next = InsertCase5_1;
+    stack_push(context->code_stack, &context->next);
+    
     if ((current == current->parent->left) && (current->parent == current->parent->parent->left))
         goto meta(context, RotateR);
     else
         goto meta(context, RotateL);
 }
 
-__code balance5_stub(struct Context* context) {
-    goto balance5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
+__code insert5_stub(struct Context* context) {
+    goto insertCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
+}
+
+__code insertCase5_1(struct Context* context, struct Tree* tree) {
+    tree->current = NULL;
+
+    stack_pop(context->code_stack, &context->next);
+    goto meta(context, context->next);
+}
+
+__code insert5_1_stub(struct Context* context) {
+    goto insertCase5_1(context, &context->data[context->dataNum]->tree);
 }
 
 __code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree) {
     struct Node* tmp = node->right;
 
-    if (node->parent == 0) {
-        tree->root = tmp;
-    } else {
+    if (node->parent) {
         if (node == node->parent->left)
             node->parent->left = tmp;
         else
             node->parent->right = tmp;
+    } else {
+        tree->root = tmp;
     }
 
-    if (tmp != 0)
+    if (tmp)
         tmp->parent = node->parent;
     
     node->right = tmp->left;
 
-    if (tmp->left != 0)
+    if (tmp->left)
         tmp->left->parent = node;
 
     tmp->left = node;
@@ -219,21 +233,21 @@
 __code rotateRight(struct Context* context, struct Node* node, struct Tree* tree) {
     struct Node* tmp = node->left;
 
-    if (node->parent == 0) {
-        tree->root = tmp;
-    } else {
+    if (node->parent) {
         if (node == node->parent->left)
             node->parent->left = tmp;
         else
             node->parent->right = tmp;
+    } else {
+        tree->root = tmp;
     }
 
-    if (tmp != 0)
+    if (tmp)
         tmp->parent = node->parent;
 
     node->left = tmp->right;
 
-    if (tmp->right != 0)
+    if (tmp->right)
         tmp->right->parent = node;
     
     tmp->right = node;
@@ -248,415 +262,383 @@
     goto rotateRight(context, context->data[Tree]->tree.current, &context->data[Tree]->tree);
 }
 
-__code colorFlip(struct Context* context, struct Node* node) {
-    node->color ^= 1;
+__code get(struct Context* context, struct Tree* tree) {
+    if (tree->root) {
+        tree->current = tree->root;
 
-    if (node->left)
-        node->left->color ^= 1;
-
-    if (node->right)
-        node->right->color ^= 1;
+        goto meta(context, Search);
+    }
 
     stack_pop(context->code_stack, &context->next);
     goto meta(context, context->next);
 }
 
-__code colorFlip_stub(struct Context* context) {
-    goto colorFlip(context, context->data[Tree]->tree.current);
-}
-
-__code fixUp(struct Context* context, struct Tree* tree, struct Node* node, struct Node* newNode) {
-    node->key = newNode->key;
-    tree->prev = newNode;
-    
-    if (stack_pop(context->node_stack, &tree->current) == 0) {
-        compare(context, tree, tree->current->key, node->key);
-        goto meta(context, ChangeRef);
-    }
-
-    goto meta(context, SetRoot);
-}
-
-__code fixUp_stub(struct Context* context) {
-    goto fixUp(context, &context->data[Tree]->tree, &context->data[Node]->node, context->data[Tree]->tree.current);
+__code get_stub(struct Context* context) {
+    goto get(context, &context->data[Tree]->tree);
 }
 
-__code setRoot(struct Context* context, struct Tree* tree, struct Node* node) {
-    if(node->parent) {
-        tree->current = tree->current->parent;
-        goto meta(context, SetRoot);
-    }
-
-    tree->root = node;
-    tree->root->color = Black;
-    tree->current = 0;
-    
-    stack_pop(context->code_stack, &context->next);
-    goto meta(context, context->next);
-}    
-
-__code setRoot_stub(struct Context* context) {
-    goto setRoot(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
-}
-
-__code changeReference(struct Context* context, struct Tree* tree, struct Node* node, int result) {
-    if (result == 1) {
-        node->right = tree->prev;
-    } else if (result == -1) {
-        node->left = tree->prev;
-    } else {
-        perror("bad status");
-    }
-    
-    goto meta(context, Balance1);
-}
-
-__code changeReference_stub(struct Context* context) {
-    goto changeReference(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, context->data[Tree]->tree.result);
-}
-
-__code get(struct Context* context, struct Tree* tree, struct Node* node) {
-    tree->current = (tree->current == 0)? tree->root : tree->current;
-
+__code search(struct Context* context, struct Tree* tree, struct Node* node) {
     compare(context, tree, tree->current->key, node->key);
     
-    if (tree->result == 0) {
+    if (tree->result == EQ) {
+        *node = *tree->current;
+        
         goto meta(context, context->next);
-    } else if (tree->result == 1) {
+    } else if (tree->result == GT) {
         tree->current = tree->current->right;
     } else {
         tree->current = tree->current->left;
     }
         
     if (tree->current)
+        goto meta(context, Search);
+
+    stack_pop(context->code_stack, &context->next);
+    goto meta(context, context->next);
+}
+
+__code search_stub(struct Context* context) {
+    goto search(context, &context->data[Tree]->tree, &context->data[Node]->node);
+}
+
+__code delete(struct Context* context, struct Tree* tree) {
+    if (tree->root) {
+        stack_push(context->code_stack, &context->next);
+        context->next = Delete1;
         goto meta(context, Get);
+    }
 
     goto meta(context, context->next);
 }
 
-__code get_stub(struct Context* context) {
-    goto get(context, &context->data[Tree]->tree, &context->data[Node]->node);
-}
-
-__code delete(struct Context* context, struct Tree* tree, struct Allocate* allocate) {
-    allocate->size = sizeof(struct Node);
-    allocator(context);
-
-    stack_push(context->code_stack, &context->next);
-
-    tree->current = tree->root;
-    compare(context, tree, tree->current->key, context->data[Node]->node.key);
-    goto meta(context, Replace_d1);
-}
-
 __code delete_stub(struct Context* context) {
-    goto delete(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate);
-}
-
-__code replaceNode_d1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, struct Node* node) {
-    *newNode = *oldNode;
-    tree->current = newNode;
-    
-    if (tree->result == -1) {
-        if (tree->current->left) {
-            
-            if (tree->current->left->left)
-                if (tree->current->left->color != Red && tree->current->left->left->color != Red) {
-                    context->next = MoveRedL1;
-                    
-                    stack_push(context->code_stack, &context->next);
-                    goto meta(context, ColorFlip);
-                }
-            
-            stack_push(context->node_stack, &tree->current);
-
-            tree->current->left = context->heap;
-            tree->current = oldNode->left;
-
-            allocator(context);
-            compare(context, tree, tree->current->key, context->data[Node]->node.key);
-
-            goto meta(context, Replace_d1);
-        }
-    } else {
-        if (tree->current->left)
-            if (tree->current->left->color == Red) {
-                allocator(context);
-                context->data[context->dataNum]->node = *tree->current->left;
-                tree->current->left = &context->data[context->dataNum]->node;
-
-                context->next = Replace_d2;
-                stack_push(context->code_stack, &context->next);
-
-                goto meta(context, RotateR);
-            }
-
-        goto meta(context, Replace_d2);
-    }
-}
-
-__code replaceNode_d1_stub(struct Context* context) {
-    goto replaceNode_d1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, &context->data[Node]->node);
+    goto delete(context, &context->data[Tree]->tree);
 }
 
-__code replaceNode_d2(struct Context* context, struct Tree* tree) {
-    compare(context, tree, tree->current->key, context->data[Node]->node.key);
+__code delete1(struct Context* context, struct Tree* tree, struct Allocate* allocate) {
+    allocate->size = sizeof(struct Node);
+    allocator(context);
     
-    if (tree->result == 0 && tree->current->right == 0) {
-        stack_pop(context->node_stack, &tree->current);
-
-        compare(context, tree, tree->current->key, context->data[Node]->node.key);
-        
-        if (tree->result == 1) {
-            tree->current->right = 0;
-        } else {
-            tree->current->left = 0;
-        }
-
-        goto meta(context, Balance1);
-    }
-
-    goto meta(context, Replace_d3);
-}
-
-__code replaceNode_d2_stub(struct Context* context) {
-    goto replaceNode_d2(context, &context->data[Tree]->tree);
-}
-
-__code replaceNode_d3(struct Context* context, struct Tree* tree) {
-    if (tree->current->right) {
-        if (tree->current->right->left)
-            if (tree->current->right->color != Red && tree->current->right->left->color != Red) {
-                context->next = MoveRedR1;
-                stack_push(context->code_stack, &context->next);
-
-                goto meta(context, ColorFlip);
-            }
-
-        goto meta(context, Replace_d4);
-    }
-}
-
-__code replaceNode_d3_stub(struct Context* context) {
-    goto replaceNode_d3(context, &context->data[Tree]->tree);
-}
-
-__code replaceNode_d4(struct Context* context, struct Tree* tree, struct Node* node) {
-    stack_push(context->node_stack, &tree->current);
+    struct Node* root = tree->root;
 
-    if (tree->result == 0) {
-        tree->current = node->right;
-        goto meta(context, FindMin);
-    } else {
-        struct Node* next = node->right;
-        tree->current->right = context->heap;
-        tree->current = next;
-        
-        allocator(context);
-
-        compare(context, tree, tree->current->key, context->data[Node]->node.key);
-
-        goto meta(context, Replace_d1);
-    }
-}
-
-__code replaceNode_d4_stub(struct Context* context) {
-    goto replaceNode_d4(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
-}
+    tree->root = &context->data[context->dataNum]->node;
+    tree->current = root;
 
-__code moveRedLeft1(struct Context* context, struct Tree* tree, struct Node* node) {
-    if (tree->current->right)
-        if (tree->current->right->left)
-            if (tree->current->right->left->color == Red) {
-                allocator(context);
-                context->data[context->dataNum]->node = *node->right;
-                node->right = &context->data[context->dataNum]->node;
-                
-                allocator(context);
-                context->data[context->dataNum]->node = *node->right->left;
-                node->right->left = &context->data[context->dataNum]->node;
-                
-                stack_push(context->node_stack, &tree->current);
-                tree->current = node->right;
-                
-                context->next = MoveRedL2;
-                stack_push(context->code_stack, &context->next);
-                
-                goto meta(context, RotateR);
-            }
-
-    stack_pop(context->code_stack, &context->next);
-    if (context->next == DeleteMin2)
-        goto meta(context, context->next);
-
-    stack_push(context->code_stack, &context->next);
-    stack_push(context->node_stack, &tree->current);
-    
-    struct Node* next = node->left;
-    tree->current->left = context->heap;
-    tree->current = next;
-    
-    allocator(context);
     compare(context, tree, tree->current->key, context->data[Node]->node.key);
     
     goto meta(context, Replace_d1);
 }
 
-__code moveRedLeft1_stub(struct Context* context) {
-    goto moveRedLeft1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
+__code delete1_stub(struct Context* context) {
+    goto delete1(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate);
 }
- 
-__code moveRedLeft2(struct Context* context, struct Tree* tree) {
-    stack_pop(context->node_stack, &tree->current);
+
+__code delete2(struct Context* context, struct Node* current) {
+    if (current->color == Black) {
+        struct Node* child = current->right == NULL ? current->left : current->right;
+        current->color = child == NULL ? Black : child->color;
 
-    context->next = MoveRedL3;
-    stack_push(context->code_stack, &context->next);
+        goto meta(context, DeleteCase1);
+    }
 
-    context->next = ColorFlip;
-    stack_push(context->code_stack, &context->next);
+    goto meta(context, Delete3);
+}
 
-    goto meta(context, RotateL);
+__code delete2_stub(struct Context* context) {
+    goto delete2(context, context->data[Tree]->tree.current);
 }
 
-__code moveRedLeft2_stub(struct Context* context) {
-    goto moveRedLeft2(context, &context->data[Tree]->tree);
+__code delete3(struct Context* context, struct Tree* tree, struct Node* current) {
+    struct Node* tmp = current->right == NULL ? current->left : current->right;
+
+    if (current->parent) {
+        if (current == current->parent->left)
+            current->parent->left = tmp;
+        else
+            current->parent->right = tmp;
+    } else {
+        tree->root = tmp;
+    }
+
+    if (tmp)
+        tmp->parent = current->parent;
+
+    if (current->parent == NULL && tmp)
+        tmp->color = Black;
+
+    current == current->parent->left ? (current->parent->left = NULL) : (current->parent->right = NULL);
+
+    stack_pop(context->code_stack, &context->next);
+    goto meta(context, context->next);
 }
 
-__code moveRedLeft3(struct Context* context, struct Tree* tree) {
-    stack_pop(context->code_stack, &context->next);
-    if (context->next == DeleteMin2)
-        goto meta(context, context->next);
+__code delete3_stub(struct Context* context) {
+    goto delete3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
+}
+
+__code replaceNodeForDelete1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) {
+    *newNode = *oldNode;
 
-    stack_push(context->code_stack, &context->next);
-    stack_push(context->node_stack, &tree->current);
+    if (result == EQ)
+        goto meta(context, Replace_d2);
+    else if (result == GT)
+        tree->current = newNode->right;
+    else
+        tree->current = newNode->left;
 
-    tree->current = tree->current->left;
+    tree->current->parent = newNode;
+    
+    if (tree->current->left == NULL && tree->current->right == NULL)
+        goto meta(context, Delete2);
+    
+    if (result == GT)
+        newNode->right = context->heap;
+    else if (result == LT)
+        newNode->left = context->heap;
+    
+    allocator(context);
     
     compare(context, tree, tree->current->key, context->data[Node]->node.key);
     
     goto meta(context, Replace_d1);
 }
 
-__code moveRedLeft3_stub(struct Context* context) {
-    goto moveRedLeft3(context, &context->data[Tree]->tree);
+__code replaceNodeForDelete1_stub(struct Context* context) {
+    goto replaceNodeForDelete1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result);
+}
+
+__code replaceNodeForDelete2(struct Context* context, struct Tree* tree, struct Node* newNode) {
+    if (tree->current->left && tree->current->right) {
+        newNode->left->parent = newNode;
+        tree->current = newNode->left;
+        newNode->left = context->heap;
+        tree->deleted = newNode;
+
+        allocator(context);
+        tree->current->parent = newNode;
+        
+        goto meta(context, FindMax1);
+    }
+
+    goto meta(context, Delete2);
+}
+
+__code replaceNodeForDelete2_stub(struct Context* context) {
+    goto replaceNodeForDelete2(context, &context->data[Tree]->tree, &context->data[context->dataNum]->node);
+}
+
+__code findMax1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) {
+    *newNode = *oldNode;
+
+    if (newNode->right)
+        goto meta(context, FindMax2);
+    
+    tree->deleted->key = newNode->key;
+    tree->deleted->value = newNode->value;
+
+    tree->current = newNode;
+
+    goto meta(context, Delete2);
 }
 
-__code moveRedRight1(struct Context* context, struct Tree* tree, struct Node* node) {
-    if (tree->current->left)
-        if (tree->current->left->left)
-            if (tree->current->left->left->color == Red) {
-                allocator(context);
-                context->data[context->dataNum]->node = *node->left;
-                node->left = &context->data[context->dataNum]->node;
-                
-                context->next = MoveRedR2;
-                stack_push(context->code_stack, &context->next);
+__code findMax1_stub(struct Context* context) {
+    goto findMax1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node);
+}
+    
+
+__code findMax2(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) {
+    *newNode = *oldNode;
+
+    if (newNode->right->right) {
+        tree->current = newNode->right;
+        newNode->right = context->heap;
 
-                context->next = ColorFlip;
-                stack_push(context->code_stack, &context->next);
-                
-                goto meta(context, RotateR);
-            }
+        allocator(context);
+        tree->current->parent = newNode;
+        
+        goto meta(context, FindMax2);
+    }
 
-    goto meta(context, Replace_d4);
+    tree->deleted->key = newNode->right->key;
+    tree->deleted->value = newNode->right->value;
+
+    tree->current = newNode;
+    
+    goto meta(context, Delete2);
+}
+    
+__code findMax2_stub(struct Context* context) {
+    goto findMax2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node);
 }
 
-__code moveRedRight1_stub(struct Context* context) {
-    goto moveRedRight1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
+__code deleteCase1(struct Context* context, struct Node* current) {
+    if (current->parent)
+        goto meta(context, DeleteCase2);
+
+    goto meta(context, Delete3);
+}
+
+__code deleteCase1_stub(struct Context* context) {
+    goto deleteCase1(context, context->data[Tree]->tree.current);
 }
 
-__code moveRedRight2(struct Context* context, struct Tree* tree) {
-    stack_push(context->node_stack, &tree->current);
-    tree->current = tree->current->right;
+__code deleteCase2(struct Context* context, struct Tree* tree, struct Node* current) {
+    struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left;
     
-    compare(context, tree, tree->current->key, context->data[Node]->node.key);
-    
-    goto meta(context, Replace_d1);
+    if ((sibling == NULL ? Black : sibling->color) == Red) {
+        current->parent->color = Red;
+        sibling->color = Black;
+
+        current == current->parent->left ? (current->parent->left = context->heap) : (current->parent->right = context->heap);
+        allocator(context);
+        context->data[context->dataNum]->node = *sibling;
+        
+        tree->current = current->parent;
+        
+        context->next = DeleteCase3;
+        stack_push(context->code_stack, &context->next);
+
+        if (current == current->parent->left)
+            goto meta(context, RotateL);
+        else
+            goto meta(context, RotateR);
+    }
+
+    goto meta(context, DeleteCase3);
 }
 
-__code moveRedRight2_stub(struct Context* context) {
-    goto moveRedRight2(context, &context->data[Tree]->tree);
+__code deleteCase2_stub(struct Context* context) {
+    goto deleteCase2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
 }
 
-__code findMin(struct Context* context, struct Tree* tree, struct Node* tmp) {
-    if (tree->current->left) {
-        tree->current = tree->current->left;
-
-        goto meta(context, FindMin);
-    }
-    
-    tmp->key = tree->current->key;
-    tmp->value = tree->current->value;
-    
-    stack_pop(context->node_stack, &tree->current);
+__code deleteCase3(struct Context* context, struct Tree* tree, struct Node* current) {
+    struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left;
     
-    tree->current->key = tmp->key;
-    tree->current->value = tmp->value;
-    
-    stack_push(context->node_stack, &tree->current);
-    
-    struct Node* next = tree->current->right;
-    
-    tree->current->right = context->heap;
-    tree->current = next;
-    
-    allocator(context);
-    
-    goto meta(context, DeleteMin1);
+    if (current->parent->color == Black &&
+        (sibling == NULL ? Black : sibling->color) == Black &&
+        (sibling->left == NULL ? Black : sibling->left->color) == Black &&
+        (sibling->right == NULL ? Black : sibling->right->color) == Black) {
+        sibling->color = Red;
+
+        tree->current = current->parent;
+        goto meta(context, DeleteCase1);
+    }
+
+    goto meta(context, DeleteCase4);
 }
 
-__code findMin_stub(struct Context* context) {
-    goto findMin(context, &context->data[Tree]->tree, &context->data[Node]->node);
+__code deleteCase3_stub(struct Context* context) {
+    goto deleteCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
+}
+
+__code deleteCase4(struct Context* context, struct Node* current) {
+    struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left;
+    
+    if (current->parent->color == Red &&
+        (sibling == NULL ? Black : sibling->color) == Black &&
+        (sibling->left == NULL ? Black : sibling->left->color) == Black &&
+        (sibling->right == NULL ? Black : sibling->right->color) == Black) {
+        sibling->color = Red;
+        current->parent->color = Black;
+
+        goto meta(context, Delete3);
+    }
+
+    goto meta(context, DeleteCase5);
+}
+
+__code deleteCase4_stub(struct Context* context) {
+    goto deleteCase4(context, context->data[Tree]->tree.current);
 }
 
-__code deleteMin1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) {
-    *newNode = *oldNode;
-    tree->current = newNode;
+__code deleteCase5(struct Context* context, struct Tree* tree, struct Node* current) {
+    struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left;
+    sibling->parent = current->parent;
+    
+    if (current == current->parent->left &&
+        (sibling == NULL ? Black : sibling->color) == Black &&
+        (sibling->left == NULL ? Black : sibling->left->color) == Red &&
+        (sibling->right == NULL ? Black : sibling->right->color) == Black) {
+        sibling->color = Red;
+        sibling->left->color = Black;
+        
+        sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap);
+        allocator(context);
+        struct Node* tmp = &context->data[context->dataNum]->node;
+        *tmp = *sibling;
+        tmp->parent = current;
+        
+        tmp->left = context->heap;
+        allocator(context);
+        context->data[context->dataNum]->node = *sibling->left;
+        context->data[context->dataNum]->node.parent = tmp;
 
-    if (tree->current->left == 0) {
-        struct Node* node = tree->current;
-
-        stack_pop(context->node_stack, &tree->current);
+        tree->current = tmp;
         
-        compare(context, tree, tree->current->key, node->key);
+        context->next = DeleteCase6;
+        stack_push(context->code_stack, &context->next);
+
+        goto meta(context, RotateR);
+    } else if (current == current->parent->right &&
+               (sibling == NULL ? Black : sibling->color) == Black &&
+               (sibling->left == NULL ? Black : sibling->left->color) == Black &&
+               (sibling->right == NULL ? Black : sibling->right->color) == Red) {
+        sibling->color = Red;
+        sibling->right->color = Black;
 
-        if (tree->result == -1) {
-            tree->current->left = 0;
-        } else {
-            tree->current->right = 0;
-        }
-        
-        goto meta(context, Balance1);
+        sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap);
+        allocator(context);
+        struct Node* tmp = &context->data[context->dataNum]->node;
+        *tmp = *sibling;
+        tmp->parent = current;
+
+        tmp->right = context->heap;
+        allocator(context);
+        context->data[context->dataNum]->node = *sibling->right;
+        context->data[context->dataNum]->node.parent = tmp;
+
+        tree->current = tmp;
+
+        context->next = DeleteCase6;
+        stack_push(context->code_stack, &context->next);
+        goto meta(context, RotateL);
     }
 
-    if (tree->current->left)
-        if (tree->current->left->left)
-            if (tree->current->left->color != Red && tree->current->left->left->color != Red) {
-                context->next = DeleteMin2;
-                stack_push(context->code_stack, &context->next);
+    goto meta(context, DeleteCase6);
+}
 
-                context->next = MoveRedL1;
-                stack_push(context->code_stack, &context->next);
-                
-                goto meta(context, ColorFlip);
-            }
-
-    goto meta(context, DeleteMin2);
+__code deleteCase5_stub(struct Context* context) {
+    goto deleteCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
 }
 
-__code deleteMin1_stub(struct Context* context) {
-    goto deleteMin1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node);
+__code deleteCase6(struct Context* context, struct Tree* tree, struct Node* current) {
+    struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left;
+
+    sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap);
+    allocator(context);
+    struct Node* tmp = &context->data[context->dataNum]->node;
+    *tmp = *sibling;
+    tmp->parent = current;
+
+    tmp->color = current->parent->color;
+    current->parent->color = Black;
+    
+    context->next = Delete3;
+    stack_push(context->code_stack, &context->next);
+    
+    if (current == current->parent->left) {
+        tmp->right->color = Black;
+        tree->current = current->parent;
+
+        goto meta(context, RotateL);
+    } else {
+        tmp->left->color = Black;
+        tree->current = current->parent;
+
+        goto meta(context, RotateR);
+    }
 }
 
-__code deleteMin2(struct Context* context, struct Tree* tree, struct Node* node) {
-    stack_push(context->node_stack, &tree->current);
-    tree->current->left = context->heap;
-    tree->current = node->left;
-
-    allocator(context);
-    goto meta(context, DeleteMin1);
+__code deleteCase6_stub(struct Context* context) {
+    goto deleteCase6(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
 }
-
-__code deleteMin2_stub(struct Context* context) {
-    goto deleteMin2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
-}
--- a/src/llrb/llrbContext.c	Mon Nov 30 21:40:50 2015 +0900
+++ b/src/llrb/llrbContext.c	Fri Dec 11 15:06:20 2015 +0900
@@ -19,28 +19,30 @@
 extern __code colorFlip_stub(struct Context*);
 extern __code fixUp_stub(struct Context*);
 extern __code changeReference_stub(struct Context*);
-extern __code balance1_stub(struct Context*);
-extern __code balance2_stub(struct Context*);
-extern __code balance3_stub(struct Context*);
-extern __code balance4_stub(struct Context*);
-extern __code balance4_1_stub(struct Context*);
-extern __code balance4_2_stub(struct Context*);
-extern __code balance5_stub(struct Context*);
-extern __code setRoot_stub(struct Context*);
+extern __code insert1_stub(struct Context*);
+extern __code insert2_stub(struct Context*);
+extern __code insert3_stub(struct Context*);
+extern __code insert4_stub(struct Context*);
+extern __code insert4_1_stub(struct Context*);
+extern __code insert4_2_stub(struct Context*);
+extern __code insert5_stub(struct Context*);
+extern __code insert5_1_stub(struct Context*);
 extern __code get_stub(struct Context*);
-extern __code findMin_stub(struct Context*);
+extern __code search_stub(struct Context*);
 extern __code delete_stub(struct Context*);
-extern __code replaceNode_d1_stub(struct Context*);
-extern __code replaceNode_d2_stub(struct Context*);
-extern __code replaceNode_d3_stub(struct Context*);
-extern __code replaceNode_d4_stub(struct Context*);
-extern __code moveRedLeft1_stub(struct Context*);
-extern __code moveRedLeft2_stub(struct Context*);
-extern __code moveRedLeft3_stub(struct Context*);
-extern __code moveRedRight1_stub(struct Context*);
-extern __code moveRedRight2_stub(struct Context*);
-extern __code deleteMin1_stub(struct Context*);
-extern __code deleteMin2_stub(struct Context*);
+extern __code delete1_stub(struct Context*);
+extern __code delete2_stub(struct Context*);
+extern __code delete3_stub(struct Context*);
+extern __code replaceNodeForDelete1_stub(struct Context*);
+extern __code replaceNodeForDelete2_stub(struct Context*);
+extern __code findMax1_stub(struct Context*);
+extern __code findMax2_stub(struct Context*);
+extern __code deleteCase1_stub(struct Context*);
+extern __code deleteCase2_stub(struct Context*);
+extern __code deleteCase3_stub(struct Context*);
+extern __code deleteCase4_stub(struct Context*);
+extern __code deleteCase5_stub(struct Context*);
+extern __code deleteCase6_stub(struct Context*);
 extern __code exit_code(struct Context*);
 
 __code initLLRBContext(struct Context* context, int num) {
@@ -64,31 +66,30 @@
     context->code[Insert]     = insertNode_stub;
     context->code[RotateL]    = rotateLeft_stub;
     context->code[RotateR]    = rotateRight_stub;
-    context->code[ColorFlip]  = colorFlip_stub;
-    context->code[FixUp]      = fixUp_stub;
-    context->code[ChangeRef]  = changeReference_stub;
-    context->code[Balance1]   = balance1_stub;
-    context->code[Balance2]   = balance2_stub;
-    context->code[Balance3]   = balance3_stub;
-    context->code[Balance4]   = balance4_stub;
-    context->code[Balance4_1] = balance4_1_stub;
-    context->code[Balance4_2] = balance4_2_stub;
-    context->code[Balance5]   = balance5_stub;
-    context->code[SetRoot]    = setRoot_stub;
+    context->code[InsertCase1]   = insert1_stub;
+    context->code[InsertCase2]   = insert2_stub;
+    context->code[InsertCase3]   = insert3_stub;
+    context->code[InsertCase4]   = insert4_stub;
+    context->code[InsertCase4_1] = insert4_1_stub;
+    context->code[InsertCase4_2] = insert4_2_stub;
+    context->code[InsertCase5]   = insert5_stub;
+    context->code[InsertCase5_1] = insert5_1_stub;
     context->code[Get]        = get_stub;
-    context->code[Delete]     = delete_stub;
-    context->code[FindMin]    = findMin_stub;
-    context->code[Replace_d1] = replaceNode_d1_stub;
-    context->code[Replace_d2] = replaceNode_d2_stub;
-    context->code[Replace_d3] = replaceNode_d3_stub;
-    context->code[Replace_d4] = replaceNode_d4_stub;
-    context->code[MoveRedL1]  = moveRedLeft1_stub;
-    context->code[MoveRedL2]  = moveRedLeft2_stub;
-    context->code[MoveRedL3]  = moveRedLeft3_stub;
-    context->code[MoveRedR1]  = moveRedRight1_stub;
-    context->code[MoveRedR2]  = moveRedRight2_stub;
-    context->code[DeleteMin1] = deleteMin1_stub;
-    context->code[DeleteMin2] = deleteMin2_stub;
+    context->code[Search]        = search_stub;
+    context->code[Delete]        = delete_stub;
+    context->code[Delete1]       = delete1_stub;
+    context->code[Delete2]       = delete2_stub;
+    context->code[Delete3]       = delete3_stub;
+    context->code[Replace_d1] = replaceNodeForDelete1_stub;
+    context->code[Replace_d2] = replaceNodeForDelete2_stub;
+    context->code[FindMax1]    = findMax1_stub;
+    context->code[FindMax2]    = findMax2_stub;
+    context->code[DeleteCase1]   = deleteCase1_stub;
+    context->code[DeleteCase2]   = deleteCase2_stub;
+    context->code[DeleteCase3]   = deleteCase3_stub;
+    context->code[DeleteCase4]   = deleteCase4_stub;
+    context->code[DeleteCase5]   = deleteCase5_stub;
+    context->code[DeleteCase6]   = deleteCase6_stub;
     context->code[Exit]       = exit_code;
     
     context->heap = context->heapStart;
@@ -107,7 +108,7 @@
     struct Tree* tree = &context->data[Tree]->tree;
     tree->root = 0;
     tree->current = 0;
-    tree->prev = 0;
+    tree->deleted = 0;
     
     context->node_stack = stack_init(sizeof(union Data*), num);
     context->code_stack = stack_init(sizeof(enum Code), 100);
--- a/src/llrb/llrbContext.h	Mon Nov 30 21:40:50 2015 +0900
+++ b/src/llrb/llrbContext.h	Fri Dec 11 15:06:20 2015 +0900
@@ -1,7 +1,7 @@
 /* Context definition for llrb example */
 #include "stack.h"
 
-#define ALLOCATE_SIZE 100
+#define ALLOCATE_SIZE 1000
 
 enum Code {
     Code1,
@@ -17,37 +17,42 @@
     Replace,
     Insert,
     Compare,
-    Create,
     RotateL,
     RotateR,
-    ColorFlip,
-    FixUp,
-    SetRoot,
-    ChangeRef,
-    Balance1,
-    Balance2,
-    Balance3,
-    Balance4,
-    Balance4_1,
-    Balance4_2,
-    Balance5,
+    SetTree,
+    InsertCase1,
+    InsertCase2,
+    InsertCase3,
+    InsertCase4,
+    InsertCase4_1,
+    InsertCase4_2,
+    InsertCase5,
+    InsertCase5_1,
     Get,
-    FindMin,
+    Search,
     Delete,
+    Delete1,
+    Delete2,
+    Delete3,
     Replace_d1,
     Replace_d2,
-    Replace_d3,
-    Replace_d4,
-    MoveRedL1,
-    MoveRedL2,
-    MoveRedL3,
-    MoveRedR1,
-    MoveRedR2,
-    DeleteMin1,
-    DeleteMin2,
+    FindMax1,
+    FindMax2,
+    DeleteCase1,
+    DeleteCase2,
+    DeleteCase3,
+    DeleteCase4,
+    DeleteCase5,
+    DeleteCase6,
     Exit,
 };
 
+enum Relational {
+    EQ,
+    GT,
+    LT,
+};
+
 enum UniqueData {
     Allocate,
     Tree,
@@ -80,7 +85,7 @@
         enum Code next;
         struct Node* root;
         struct Node* current;
-        struct Node* prev;
+        struct Node* deleted;;
         int result;
     } tree;
     struct Node {
--- a/src/llrb/main.c	Mon Nov 30 21:40:50 2015 +0900
+++ b/src/llrb/main.c	Fri Dec 11 15:06:20 2015 +0900
@@ -88,11 +88,11 @@
     print_tree(context->data[Tree]->tree.root, 0);
     
     struct Node* node = &context->data[Node]->node;
-    node->key = 5;
+    node->key = 4;
     
     context->next = Code5;
 
-    goto meta(context, Exit);
+    goto meta(context, Delete);
 }
 
 __code code5(struct Context* context) {
@@ -101,7 +101,7 @@
     puts("--Number of Data--");
     printf("%d\n", context->dataNum);
 
-    goto meta(context, Find);
+    goto meta(context, Exit);
 }
 
 __code find(struct Context* context) {
--- a/src/llrb/stack.c	Mon Nov 30 21:40:50 2015 +0900
+++ b/src/llrb/stack.c	Fri Dec 11 15:06:20 2015 +0900
@@ -55,7 +55,7 @@
     stack_ptr->num--;
 
     memcpy(data, (char*)stack_ptr->data+stack_ptr->num*stack_ptr->size, stack_ptr->size);
-
+    
     return 0;
 }