Diff: stack/pico_tree.c

Revision:

131:4758606c9316

Parent:

68:0847e35d08a6

Child:

149:5f4cb161cec3

--- a/stack/pico_tree.c	Wed Dec 11 07:20:17 2013 +0000
+++ b/stack/pico_tree.c	Mon Dec 16 11:25:54 2013 +0100
@@ -1,22 +1,22 @@
 /*********************************************************************
-PicoTCP. Copyright (c) 2012 TASS Belgium NV. Some rights reserved.
-See LICENSE and COPYING for usage.
+   PicoTCP. Copyright (c) 2012 TASS Belgium NV. Some rights reserved.
+   See LICENSE and COPYING for usage.
 
-Author: Andrei Carp <andrei.carp@tass.be>
-*********************************************************************/
+   Author: Andrei Carp <andrei.carp@tass.be>
+ *********************************************************************/
 
 #include "pico_tree.h"
 #include "pico_config.h"
 #include "pico_protocol.h"
 
-#define RED 	0
+#define RED     0
 #define BLACK 1
 
-// By default the null leafs are black
+/* By default the null leafs are black */
 struct pico_tree_node LEAF = {
-  NULL, // key
-  &LEAF, &LEAF, &LEAF, // parent, left,right
-  BLACK, // color
+    NULL, /* key */
+    &LEAF, &LEAF, &LEAF, /* parent, left,right */
+    BLACK, /* color */
 };
 
 #define IS_LEAF(x) (x == &LEAF)
@@ -32,390 +32,390 @@
 /*
  * Local Functions
  */
-static struct pico_tree_node * create_node(struct pico_tree * tree,void *key);
-static void rotateToLeft(struct pico_tree* tree, struct pico_tree_node* node);
-static void rotateToRight(struct pico_tree* root, struct pico_tree_node* node);
-static void fix_insert_collisions(struct pico_tree* tree, struct pico_tree_node* node);
-static void fix_delete_collisions(struct pico_tree* tree, struct pico_tree_node * node);
-static void switchNodes(struct pico_tree* tree, struct pico_tree_node* nodeA, struct pico_tree_node* nodeB);
+static struct pico_tree_node *create_node(struct pico_tree *tree, void *key);
+static void rotateToLeft(struct pico_tree*tree, struct pico_tree_node*node);
+static void rotateToRight(struct pico_tree*root, struct pico_tree_node*node);
+static void fix_insert_collisions(struct pico_tree*tree, struct pico_tree_node*node);
+static void fix_delete_collisions(struct pico_tree*tree, struct pico_tree_node *node);
+static void switchNodes(struct pico_tree*tree, struct pico_tree_node*nodeA, struct pico_tree_node*nodeB);
 
 /*
  * Exported functions
  */
 
-struct pico_tree_node *pico_tree_firstNode(struct pico_tree_node * node)
+struct pico_tree_node *pico_tree_firstNode(struct pico_tree_node *node)
 {
-	while(IS_NOT_LEAF(node->leftChild))
-		node = node->leftChild;
-	return node;
+    while(IS_NOT_LEAF(node->leftChild))
+        node = node->leftChild;
+    return node;
 }
 
-struct pico_tree_node * pico_tree_lastNode(struct pico_tree_node * node)
+struct pico_tree_node *pico_tree_lastNode(struct pico_tree_node *node)
 {
-	while(IS_NOT_LEAF(node->rightChild))
-		node = node->rightChild;
-	return node;
+    while(IS_NOT_LEAF(node->rightChild))
+        node = node->rightChild;
+    return node;
 }
 
-struct pico_tree_node * pico_tree_next(struct pico_tree_node * node)
+struct pico_tree_node *pico_tree_next(struct pico_tree_node *node)
 {
-	if(IS_NOT_LEAF(node->rightChild))
-	{
-		node = node->rightChild;
-		while(IS_NOT_LEAF(node->leftChild))
-			node = node->leftChild;
-	}
-	else
-	{
-		if (IS_NOT_LEAF(node->parent) &&  AM_I_LEFT_CHILD(node))
-		  		node = node->parent;
-		else {
-			while (IS_NOT_LEAF(node->parent) &&	AM_I_RIGHT_CHILD(node))
-				node = node->parent;
+    if(IS_NOT_LEAF(node->rightChild))
+    {
+        node = node->rightChild;
+        while(IS_NOT_LEAF(node->leftChild))
+            node = node->leftChild;
+    }
+    else
+    {
+        if (IS_NOT_LEAF(node->parent) &&  AM_I_LEFT_CHILD(node))
+            node = node->parent;
+        else {
+            while (IS_NOT_LEAF(node->parent) && AM_I_RIGHT_CHILD(node))
+                node = node->parent;
+            node = node->parent;
+        }
+    }
 
-			node = node->parent;
-		}
-	}
-	return node;
+    return node;
 }
 
-struct pico_tree_node * pico_tree_prev(struct pico_tree_node * node)
+struct pico_tree_node *pico_tree_prev(struct pico_tree_node *node)
 {
-	if (IS_NOT_LEAF(node->leftChild)) {
-  	node = node->leftChild;
-  	while (IS_NOT_LEAF(node->rightChild))
-  		node = node->rightChild;
-  } else {
-  	if (IS_NOT_LEAF(node->parent) && AM_I_RIGHT_CHILD(node))
-  		node = node->parent;
-  	else {
-  		while (IS_NOT_LEAF(node) &&	AM_I_LEFT_CHILD(node))
-  			node = node->parent;
+    if (IS_NOT_LEAF(node->leftChild)) {
+        node = node->leftChild;
+        while (IS_NOT_LEAF(node->rightChild))
+            node = node->rightChild;
+    } else {
+        if (IS_NOT_LEAF(node->parent) && AM_I_RIGHT_CHILD(node))
+            node = node->parent;
+        else {
+            while (IS_NOT_LEAF(node) && AM_I_LEFT_CHILD(node))
+                node = node->parent;
+            node = node->parent;
+        }
+    }
 
-  		node = node->parent;
-  	}
-  }
-	return node;
+    return node;
 }
 
-void * pico_tree_insert(struct pico_tree* tree, void * key){
+void *pico_tree_insert(struct pico_tree*tree, void *key)
+{
 
-	struct pico_tree_node * last_node = INIT_LEAF;
-  struct pico_tree_node * temp = tree->root;
-  struct pico_tree_node * insert;
-  void * LocalKey;
-  int result = 0;
+    struct pico_tree_node *last_node = INIT_LEAF;
+    struct pico_tree_node *temp = tree->root;
+    struct pico_tree_node *insert;
+    void *LocalKey;
+    int result = 0;
 
-	LocalKey = (IS_NOT_LEAF(tree->root) ? pico_tree_findKey(tree,key) : NULL);
-	// if node already in, bail out
-  if(LocalKey)
-  	return LocalKey;
-  else
-  {
-  	insert = create_node(tree,key);
-  	if(!insert)
-  	{
-  		pico_err = PICO_ERR_ENOMEM;
-  		// to let the user know that it couldn't insert
-  		return (void *)&LEAF;
-  	}
-  }
+    LocalKey = (IS_NOT_LEAF(tree->root) ? pico_tree_findKey(tree, key) : NULL);
+    /* if node already in, bail out */
+    if(LocalKey)
+        return LocalKey;
+    else
+    {
+        insert = create_node(tree, key);
+        if(!insert)
+        {
+            pico_err = PICO_ERR_ENOMEM;
+            /* to let the user know that it couldn't insert */
+            return (void *)&LEAF;
+        }
+    }
 
-  // search for the place to insert the new node
-  while(IS_NOT_LEAF(temp))
-  {
-		last_node = temp;
-		result = tree->compare(insert->keyValue,temp->keyValue);
+    /* search for the place to insert the new node */
+    while(IS_NOT_LEAF(temp))
+    {
+        last_node = temp;
+        result = tree->compare(insert->keyValue, temp->keyValue);
 
-		temp = (result < 0 ? temp->leftChild : temp->rightChild);
-  }
-
-  // make the needed connections
-  insert->parent = last_node;
+        temp = (result < 0 ? temp->leftChild : temp->rightChild);
+    }
+    /* make the needed connections */
+    insert->parent = last_node;
 
-  if(IS_LEAF(last_node))
-    tree->root = insert;
-  else{
-  	result = tree->compare(insert->keyValue,last_node->keyValue);
-    if(result < 0)
-      last_node->leftChild = insert;
-    else
-      last_node->rightChild = insert;
-  }
+    if(IS_LEAF(last_node))
+        tree->root = insert;
+    else{
+        result = tree->compare(insert->keyValue, last_node->keyValue);
+        if(result < 0)
+            last_node->leftChild = insert;
+        else
+            last_node->rightChild = insert;
+    }
 
-  // fix colour issues
-  fix_insert_collisions(tree, insert);
+    /* fix colour issues */
+    fix_insert_collisions(tree, insert);
 
-	return NULL;
+    return NULL;
 }
 
-struct pico_tree_node * pico_tree_findNode(struct pico_tree * tree, void * key)
+struct pico_tree_node *pico_tree_findNode(struct pico_tree *tree, void *key)
 {
-		struct pico_tree_node *found;
+    struct pico_tree_node *found;
 
-		found = tree->root;
+    found = tree->root;
 
-	  while(IS_NOT_LEAF(found))
-	  {
-	  	int result;
-	  	result = tree->compare(found->keyValue, key);
-	  	if(result == 0)
-	  	{
-	  	   return found;
-	  	}
-	  	else if(result < 0)
-	       found = found->rightChild;
-	     else
-	       found = found->leftChild;
-	   }
-
-
-
-	  return NULL;
+    while(IS_NOT_LEAF(found))
+    {
+        int result;
+        result = tree->compare(found->keyValue, key);
+        if(result == 0)
+        {
+            return found;
+        }
+        else if(result < 0)
+            found = found->rightChild;
+        else
+            found = found->leftChild;
+    }
+    return NULL;
 }
 
-void * pico_tree_findKey(struct pico_tree * tree, void * key)
+void *pico_tree_findKey(struct pico_tree *tree, void *key)
 {
-  struct pico_tree_node *found;
+    struct pico_tree_node *found;
 
 
-  found = tree->root;
+    found = tree->root;
 
-  while(IS_NOT_LEAF(found))
-  {
-  	int result;
+    while(IS_NOT_LEAF(found))
+    {
+        int result;
 
-  	result = tree->compare(found->keyValue, key);
-  	if(result == 0)
-  	   return found->keyValue;
-  	else if(result < 0)
-       found = found->rightChild;
-     else
-       found = found->leftChild;
+        result = tree->compare(found->keyValue, key);
+        if(result == 0)
+            return found->keyValue;
+        else if(result < 0)
+            found = found->rightChild;
+        else
+            found = found->leftChild;
 
-   }
-
-  return NULL;
+    }
+    return NULL;
 }
 
-void * pico_tree_first(struct pico_tree * tree)
+void *pico_tree_first(struct pico_tree *tree)
 {
-	return pico_tree_firstNode(tree->root)->keyValue;
+    return pico_tree_firstNode(tree->root)->keyValue;
 }
 
-void * pico_tree_last(struct pico_tree * tree)
+void *pico_tree_last(struct pico_tree *tree)
 {
-	return pico_tree_lastNode(tree->root)->keyValue;
+    return pico_tree_lastNode(tree->root)->keyValue;
 }
 
-void * pico_tree_delete(struct pico_tree * tree, void * key){
+void *pico_tree_delete(struct pico_tree *tree, void *key)
+{
 
-	uint8_t nodeColor; // keeps the color of the node to be deleted
-  void * lkey; // keeps a copy of the key which will be removed
-	struct pico_tree_node * delete; // keeps a copy of the node to be extracted
-	struct pico_tree_node * temp; // temporary
-	struct pico_tree_node * ltemp; // used for switching nodes, as a copy
+    uint8_t nodeColor; /* keeps the color of the node to be deleted */
+    void *lkey; /* keeps a copy of the key which will be removed */
+    struct pico_tree_node *delete;  /* keeps a copy of the node to be extracted */
+    struct pico_tree_node *temp;  /* temporary */
+    struct pico_tree_node *ltemp;  /* used for switching nodes, as a copy */
 
-	delete = pico_tree_findNode(tree, key);
-	ltemp = delete;
+    delete = pico_tree_findNode(tree, key);
+    ltemp = delete;
 
-  // this key isn't in the tree, bail out
-  if(!delete)
-    return NULL;
+    /* this key isn't in the tree, bail out */
+    if(!delete)
+        return NULL;
 
-  lkey = delete->keyValue;
-  nodeColor = delete->color;
+    lkey = delete->keyValue;
+    nodeColor = delete->color;
 
-  if(IS_LEAF(delete->leftChild))
-  {
-    temp = ltemp->rightChild;
-    switchNodes(tree, ltemp, ltemp->rightChild);
-  }
-  else
+    if(IS_LEAF(delete->leftChild))
+    {
+        temp = ltemp->rightChild;
+        switchNodes(tree, ltemp, ltemp->rightChild);
+    }
+    else
     if(IS_LEAF(delete->rightChild))
     {
-    	struct pico_tree_node * _ltemp = delete;
-      temp = _ltemp->leftChild;
-      switchNodes(tree, _ltemp, _ltemp->leftChild);
+        struct pico_tree_node *_ltemp = delete;
+        temp = _ltemp->leftChild;
+        switchNodes(tree, _ltemp, _ltemp->leftChild);
     }
     else{
-    	struct pico_tree_node * min;
-    	min = pico_tree_firstNode(delete->rightChild);
-      nodeColor = min->color;
+        struct pico_tree_node *min;
+        min = pico_tree_firstNode(delete->rightChild);
+        nodeColor = min->color;
 
-       temp = min->rightChild;
-       if(min->parent == ltemp && IS_NOT_LEAF(temp))
- 	 temp->parent = min;
-       else{
-      	 switchNodes(tree, min, min->rightChild);
-      	 min->rightChild = ltemp->rightChild;
-      	 if(IS_NOT_LEAF(min->rightChild)) min->rightChild->parent = min;
-       }
-       switchNodes(tree, ltemp, min);
-       min->leftChild = ltemp->leftChild;
-       if(IS_NOT_LEAF(min->leftChild)) min->leftChild->parent = min;
-       min->color = ltemp->color;
+        temp = min->rightChild;
+        if(min->parent == ltemp && IS_NOT_LEAF(temp))
+            temp->parent = min;
+        else{
+            switchNodes(tree, min, min->rightChild);
+            min->rightChild = ltemp->rightChild;
+            if(IS_NOT_LEAF(min->rightChild)) min->rightChild->parent = min;
+        }
+
+        switchNodes(tree, ltemp, min);
+        min->leftChild = ltemp->leftChild;
+        if(IS_NOT_LEAF(min->leftChild)) min->leftChild->parent = min;
+
+        min->color = ltemp->color;
     }
 
-  // deleted node is black, this will mess up the black path property
-  if(nodeColor == BLACK)
-    fix_delete_collisions(tree, temp);
+    /* deleted node is black, this will mess up the black path property */
+    if(nodeColor == BLACK)
+        fix_delete_collisions(tree, temp);
 
-  pico_free(delete);
+    pico_free(delete);
 
-  return lkey;
+    return lkey;
 }
 
-int pico_tree_empty(struct pico_tree * tree)
+int pico_tree_empty(struct pico_tree *tree)
 {
-	return (!tree->root || IS_LEAF(tree->root));
+    return (!tree->root || IS_LEAF(tree->root));
 }
 
 /*
  * Private functions
  */
-static void rotateToLeft(struct pico_tree* tree, struct pico_tree_node* node)
+static void rotateToLeft(struct pico_tree*tree, struct pico_tree_node*node)
 {
-  struct pico_tree_node* temp;
+    struct pico_tree_node*temp;
 
-  temp = node->rightChild;
+    temp = node->rightChild;
 
-  if(temp == &LEAF) return;
+    if(temp == &LEAF) return;
 
-  node->rightChild = temp->leftChild;
+    node->rightChild = temp->leftChild;
 
-  if(IS_NOT_LEAF(temp->leftChild))
-    temp->leftChild->parent = node;
+    if(IS_NOT_LEAF(temp->leftChild))
+        temp->leftChild->parent = node;
 
-  temp->parent = node->parent;
+    temp->parent = node->parent;
 
-  if(IS_LEAF(node->parent))
-    tree->root = temp;
-  else
+    if(IS_LEAF(node->parent))
+        tree->root = temp;
+    else
     if(node == node->parent->leftChild)
-    	node->parent->leftChild = temp;
+        node->parent->leftChild = temp;
     else
-    	node->parent->rightChild = temp;
+        node->parent->rightChild = temp;
 
-  temp->leftChild = node;
-  node->parent = temp;
+    temp->leftChild = node;
+    node->parent = temp;
 }
 
 
-static void rotateToRight(struct pico_tree * tree, struct pico_tree_node * node)
+static void rotateToRight(struct pico_tree *tree, struct pico_tree_node *node)
 {
-  struct pico_tree_node* temp;
+    struct pico_tree_node*temp;
 
-  temp = node->leftChild;
-  node->leftChild = temp->rightChild;
+    temp = node->leftChild;
+    node->leftChild = temp->rightChild;
 
-  if(temp == &LEAF) return;
+    if(temp == &LEAF) return;
 
-  if(IS_NOT_LEAF(temp->rightChild))
-    temp->rightChild->parent = node;
+    if(IS_NOT_LEAF(temp->rightChild))
+        temp->rightChild->parent = node;
 
-  temp->parent = node->parent;
+    temp->parent = node->parent;
 
-  if(IS_LEAF(node->parent))
-    tree->root = temp;
-  else
+    if(IS_LEAF(node->parent))
+        tree->root = temp;
+    else
     if(node == node->parent->rightChild)
-      node->parent->rightChild = temp;
+        node->parent->rightChild = temp;
     else
-      node->parent->leftChild = temp;
+        node->parent->leftChild = temp;
 
-  temp->rightChild = node;
-  node->parent = temp;
-  return;
+    temp->rightChild = node;
+    node->parent = temp;
+    return;
 }
 
-static struct pico_tree_node * create_node(struct pico_tree * tree, void* key)
+static struct pico_tree_node *create_node(struct pico_tree *tree, void*key)
 {
-  struct pico_tree_node *temp;
-  IGNORE_PARAMETER(tree);
-  temp = (struct pico_tree_node *)pico_zalloc(sizeof(struct pico_tree_node));
+    struct pico_tree_node *temp;
+    IGNORE_PARAMETER(tree);
+    temp = (struct pico_tree_node *)pico_zalloc(sizeof(struct pico_tree_node));
 
-  if(!temp)
-  	return NULL;
+    if(!temp)
+        return NULL;
 
-  temp->keyValue = key;
-  temp->parent = &LEAF;
-  temp->leftChild = &LEAF;
-  temp->rightChild = &LEAF;
-  // by default every new node is red
-  temp->color = RED;
-  return temp;
+    temp->keyValue = key;
+    temp->parent = &LEAF;
+    temp->leftChild = &LEAF;
+    temp->rightChild = &LEAF;
+    /* by default every new node is red */
+    temp->color = RED;
+    return temp;
 }
 
 /*
  * This function fixes the possible collisions in the tree.
  * Eg. if a node is red his children must be black !
  */
-static void fix_insert_collisions(struct pico_tree* tree, struct pico_tree_node* node)
+static void fix_insert_collisions(struct pico_tree*tree, struct pico_tree_node*node)
 {
-  struct pico_tree_node* temp;
+    struct pico_tree_node*temp;
+
+    while(node->parent->color == RED && IS_NOT_LEAF(GRANPA(node)))
+    {
+        if(AM_I_RIGHT_CHILD(node->parent))
+        {
+            temp = GRANPA(node)->leftChild;
+            if(temp->color == RED) {
+                node->parent->color = BLACK;
+                temp->color = BLACK;
+                GRANPA(node)->color = RED;
+                node = GRANPA(node);
+            }
+            else if(temp->color == BLACK) {
+                if(node == node->parent->leftChild) {
+                    node = node->parent;
+                    rotateToRight(tree, node);
+                }
 
-  while(node->parent->color == RED && IS_NOT_LEAF(GRANPA(node)) )
-  {
-  	if(AM_I_RIGHT_CHILD(node->parent))
-	 {
-			temp = GRANPA(node)->leftChild;
-			if(temp->color == RED){
-				node->parent->color = BLACK;
-				temp->color = BLACK;
-				GRANPA(node)->color = RED;
-				node = GRANPA(node);
-			}
-			else if(temp->color == BLACK){
-				if(node == node->parent->leftChild){
-				node = node->parent;
-				rotateToRight(tree, node);
-			}
-			node->parent->color = BLACK;
-			GRANPA(node)->color = RED;
-			rotateToLeft(tree, GRANPA(node));
-			}
-		}
-  	else if(AM_I_LEFT_CHILD(node->parent))
-    {
-      temp = GRANPA(node)->rightChild;
-      if(temp->color == RED){
-				node->parent->color = BLACK;
-				temp->color = BLACK;
-				GRANPA(node)->color = RED;
-				node = GRANPA(node);
-      }
-      else if(temp->color == BLACK){
-				if(AM_I_RIGHT_CHILD(node)){
-					node = node->parent;
-					rotateToLeft(tree, node);
-				}
-				node->parent->color = BLACK;
-				GRANPA(node)->color = RED;
-				rotateToRight(tree, GRANPA(node));
-  		}
+                node->parent->color = BLACK;
+                GRANPA(node)->color = RED;
+                rotateToLeft(tree, GRANPA(node));
+            }
+        }
+        else if(AM_I_LEFT_CHILD(node->parent))
+        {
+            temp = GRANPA(node)->rightChild;
+            if(temp->color == RED) {
+                node->parent->color = BLACK;
+                temp->color = BLACK;
+                GRANPA(node)->color = RED;
+                node = GRANPA(node);
+            }
+            else if(temp->color == BLACK) {
+                if(AM_I_RIGHT_CHILD(node)) {
+                    node = node->parent;
+                    rotateToLeft(tree, node);
+                }
+
+                node->parent->color = BLACK;
+                GRANPA(node)->color = RED;
+                rotateToRight(tree, GRANPA(node));
+            }
+        }
     }
-  }
-
-  // make sure that the root of the tree stays black
-  tree->root->color = BLACK;
+    /* make sure that the root of the tree stays black */
+    tree->root->color = BLACK;
 }
 
-static void switchNodes(struct pico_tree* tree, struct pico_tree_node* nodeA, struct pico_tree_node* nodeB)
+static void switchNodes(struct pico_tree*tree, struct pico_tree_node*nodeA, struct pico_tree_node*nodeB)
 {
 
-	if(IS_LEAF(nodeA->parent))
-    tree->root = nodeB;
-  else
-  if(IS_NOT_LEAF(nodeA))
-  {	
-    if(AM_I_LEFT_CHILD(nodeA))
-      nodeA->parent->leftChild = nodeB;
+    if(IS_LEAF(nodeA->parent))
+        tree->root = nodeB;
     else
-      nodeA->parent->rightChild = nodeB;
-   }
+    if(IS_NOT_LEAF(nodeA))
+    {
+        if(AM_I_LEFT_CHILD(nodeA))
+            nodeA->parent->leftChild = nodeB;
+        else
+            nodeA->parent->rightChild = nodeB;
+    }
 
-  if(IS_NOT_LEAF(nodeB))  nodeB->parent = nodeA->parent;
+    if(IS_NOT_LEAF(nodeB)) nodeB->parent = nodeA->parent;
 
 }
 
@@ -424,73 +424,76 @@
  * Eg. if a node is red his children must be black !
  * In this case the function fixes the constant black path property.
  */
-static void fix_delete_collisions(struct pico_tree* tree, struct pico_tree_node * node)
+static void fix_delete_collisions(struct pico_tree*tree, struct pico_tree_node *node)
 {
-  struct pico_tree_node* temp;
+    struct pico_tree_node*temp;
+
+    while( node != tree->root && node->color == BLACK && IS_NOT_LEAF(node))
+    {
+        if(AM_I_LEFT_CHILD(node)) {
 
-  while( node != tree->root && node->color == BLACK && IS_NOT_LEAF(node))
-  {
-  	if(AM_I_LEFT_CHILD(node)){
+            temp = node->parent->rightChild;
+            if(temp->color == RED)
+            {
+                temp->color = BLACK;
+                node->parent->color = RED;
+                rotateToLeft(tree, node->parent);
+                temp = node->parent->rightChild;
+            }
+
+            if(temp->leftChild->color == BLACK && temp->rightChild->color == BLACK)
+            {
+                temp->color = RED;
+                node = node->parent;
+            }
+            else
+            {
+                if(temp->rightChild->color == BLACK)
+                {
+                    temp->leftChild->color = BLACK;
+                    temp->color = RED;
+                    rotateToRight(tree, temp);
+                    temp = temp->parent->rightChild;
+                }
 
-      temp = node->parent->rightChild;
-      if(temp->color == RED)
-      {
-				temp->color = BLACK;
-				node->parent->color = RED;
-				rotateToLeft(tree, node->parent);
-				temp = node->parent->rightChild;
-      }
-      if(temp->leftChild->color == BLACK && temp->rightChild->color == BLACK)
-      {
-				temp->color = RED;
-				node = node->parent;
-      }
-      else
-      {
-				if(temp->rightChild->color == BLACK)
-				{
-					temp->leftChild->color = BLACK;
-					temp->color = RED;
-					rotateToRight(tree, temp);
-					temp = temp->parent->rightChild;
-				}
-				temp->color = node->parent->color;
-				node->parent->color = BLACK;
-				temp->rightChild->color = BLACK;
-				rotateToLeft(tree, node->parent);
-				node = tree->root;
-      }
+                temp->color = node->parent->color;
+                node->parent->color = BLACK;
+                temp->rightChild->color = BLACK;
+                rotateToLeft(tree, node->parent);
+                node = tree->root;
+            }
+        }
+        else{
+            temp = node->parent->leftChild;
+            if(temp->color == RED)
+            {
+                temp->color = BLACK;
+                node->parent->color = RED;
+                rotateToRight(tree, node->parent);
+                temp = node->parent->leftChild;
+            }
+
+            if(temp->rightChild->color == BLACK && temp->leftChild->color == BLACK)
+            {
+                temp->color = RED;
+                node = node->parent;
+            }
+            else{
+                if(temp->leftChild->color == BLACK)
+                {
+                    temp->rightChild->color = BLACK;
+                    temp->color = RED;
+                    rotateToLeft(tree, temp);
+                    temp = temp->parent->leftChild;
+                }
+
+                temp->color = node->parent->color;
+                node->parent->color = BLACK;
+                temp->leftChild->color = BLACK;
+                rotateToRight(tree, node->parent);
+                node = tree->root;
+            }
+        }
     }
-    else{
-      temp = node->parent->leftChild;
-      if(temp->color == RED)
-      {
-				temp->color = BLACK;
-				node->parent->color = RED;
-				rotateToRight(tree, node->parent);
-				temp = node->parent->leftChild;
-      }
-      if(temp->rightChild->color == BLACK && temp->leftChild->color == BLACK)
-      {
-				temp->color = RED;
-				node = node->parent;
-      }
-      else{
-				if(temp->leftChild->color == BLACK)
-				{
-					temp->rightChild->color = BLACK;
-					temp->color = RED;
-					rotateToLeft(tree, temp);
-					temp = temp->parent->leftChild;
-				}
-			temp->color = node->parent->color;
-			node->parent->color = BLACK;
-			temp->leftChild->color = BLACK;
-			rotateToRight(tree, node->parent);
-			node = tree->root;
-      }
-    }
-  }
-
-  node->color = BLACK;
+    node->color = BLACK;
 }