taskrambler  v0.1.8
Web server and task management solution.
Functions
tree/delete.c File Reference
#include "tree.h"
+ Include dependency graph for tree/delete.c:

Go to the source code of this file.

Functions

Tree inOrderSuccessor (Tree)
 
void treeRotateLeft (Tree *, Tree)
 
void treeRotateRight (Tree *, Tree)
 
void * treeDelete (Tree *this, const void *search, TreeComp comp)
 

Detailed Description

Author
Georg Hopp
Copyright
Copyright © 2012 Georg Hopp

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.

Definition in file tree/delete.c.

Function Documentation

Tree inOrderSuccessor ( Tree  )

Definition at line 26 of file inOrderSuccessor.c.

References TREE_LEFT, and TREE_RIGHT.

Referenced by treeDelete().

27 {
28  this = TREE_RIGHT(this);
29 
30  while (NULL != TREE_LEFT(this)) {
31  this = TREE_LEFT(this);
32  }
33 
34  return this;
35 }
TREE_RIGHT
#define TREE_RIGHT(node)
Definition: tree.h:28
TREE_LEFT
#define TREE_LEFT(node)
Definition: tree.h:29

+ Here is the caller graph for this function:

void* treeDelete ( Tree *  this,
const void *  search,
TreeComp  comp 
)

Definition at line 31 of file tree/delete.c.

References comp(), inOrderSuccessor(), rbBlack, rbRed, TREE_CHILD, TREE_LEFT, TREE_PARENT, TREE_REPLACE_NODE, TREE_RIGHT, TREE_SIBLING, treeRotateLeft(), and treeRotateRight().

Referenced by hashDelete(), hashDeleteByVal(), and main().

32 {
33  Tree node = *this;
34  Tree del_node;
35 
36  void * data;
37 
38  /*
39  * first search for it and if its found return the data
40  * and we are done...
41  */
42  while (NULL != node) {
43  int comparison = comp(node->data, search);
44 
45  if (0 < comparison) {
46  node = TREE_LEFT(node);
47  continue;
48  }
49 
50  if (0 > comparison) {
51  node = TREE_RIGHT(node);
52  continue;
53  }
54 
55  if (0 == comparison) {
56  break;
57  }
58  }
59 
60  /*
61  * nothing was found...return NULL to indicate this.
62  */
63  if (NULL == node) {
64  return NULL;
65  }
66 
67  /*
68  * we found an element, store its data pointer as we are
69  * up to delete it.
70  */
71  data = node->data;
72 
73  /*
74  * now remove the element.
75  */
76 
77  /*
78  * if we have two children replace data with the one from
79  * out inOrderSuccessor and remove the inOrderSuccessor.
80  */
81  if (NULL != TREE_LEFT(node) && NULL != TREE_RIGHT(node)) {
82  Tree successor = inOrderSuccessor(node);
83 
84  node->data = successor->data;
85  node = successor;
86  }
87 
88  {
89  Tree child = TREE_CHILD(node);
90 
91  /*
92  * if we still have one child replace ourself with it.
93  */
94  TREE_REPLACE_NODE(this, node, child);
95 
96  /*
97  * and finally delete the node...and prepare ourselfs
98  * for rebalancing.
99  */
100  if (rbBlack == node->color) {
101  if (NULL != child && rbRed == child->color) {
102  child->color = rbBlack;
103  delete(node);
104  return data;
105  } else {
106  del_node = node;
107  if (NULL != child) {
108  node = child;
109  } else {
110  node->color = rbBlack;
111  node->left = NULL;
112  node->right = NULL;
113  }
114  }
115  } else {
116  delete(node);
117  return data;
118  }
119  }
120 
121  /*
122  * now comes rebalancing...note that if we came to this point
123  * the node is still not deleted.
124  * This is because I am not sure if it is needed during the
125  * rebalancing process...(this does not make much sense, but
126  * to be honest I don't know now.)
127  */
128  while(1) {
129  // case 1
130  if (NULL == TREE_PARENT(node)) {
131  break;
132  }
133 
134  // case 2
135  if (NULL != TREE_SIBLING(node)
136  && rbRed == TREE_SIBLING(node)->color) {
137 
138  TREE_PARENT(node)->color = rbRed;
139  TREE_SIBLING(node)->color = rbBlack;
140 
141  if (NULL != TREE_PARENT(node)->right &&
142  node != TREE_PARENT(node)->right) {
143 
144  //TREE_ROTATE_LEFT(this, TREE_PARENT(node));
145  treeRotateLeft(this, TREE_PARENT(node));
146 
147  } else {
148 
149  //TREE_ROTATE_RIGHT(this, TREE_PARENT(node));
150  treeRotateRight(this, TREE_PARENT(node));
151 
152  }
153  }
154 
155  // case 3 / 4
156  if (NULL == TREE_SIBLING(node)
157  || (rbBlack == TREE_SIBLING(node)->color
158  && (NULL == TREE_SIBLING(node)->left
159  || rbBlack == TREE_SIBLING(node)->left->color)
160  && (NULL == TREE_SIBLING(node)->right
161  || rbBlack == TREE_SIBLING(node)->right->color))) {
162 
163  if (NULL != TREE_SIBLING(node)) {
164  TREE_SIBLING(node)->color = rbRed;
165  }
166 
167 
168  /*
169  * this is the point where during the balancing our tree
170  * node can be finally deleted.
171  */
172  if (rbBlack == TREE_PARENT(node)->color) {
173  // case 3
174  Tree parent = node->parent;
175  node = parent;
176  continue;
177  } else {
178  // case 4
179  TREE_PARENT(node)->color = rbBlack;
180  break;
181  }
182  }
183 
184  // case 5
185  if (NULL != TREE_SIBLING(node)
186  && rbBlack == TREE_SIBLING(node)->color) {
187 
188  if (node == TREE_PARENT(node)->left
189  && (NULL == TREE_SIBLING(node)->right
190  || rbBlack == TREE_SIBLING(node)->right->color)
191  && (NULL != TREE_SIBLING(node)->left
192  && rbRed == TREE_SIBLING(node)->left->color)) {
193 
194  TREE_SIBLING(node)->color = rbRed;
195  TREE_SIBLING(node)->left->color = rbBlack;
196 
197  //TREE_ROTATE_RIGHT(this, TREE_SIBLING(node));
198  treeRotateRight(this, TREE_SIBLING(node));
199 
200  } else if (node == TREE_PARENT(node)->right
201  && (NULL == TREE_SIBLING(node)->left
202  || rbBlack == TREE_SIBLING(node)->left->color)
203  && (NULL != TREE_SIBLING(node)->right
204  && rbRed == TREE_SIBLING(node)->right->color)) {
205 
206  TREE_SIBLING(node)->color = rbRed;
207  TREE_SIBLING(node)->right->color = rbBlack;
208 
209  //TREE_ROTATE_LEFT(this, TREE_SIBLING(node));
210  treeRotateLeft(this, TREE_SIBLING(node));
211  }
212  }
213 
214  // case 6
215  if (NULL != TREE_SIBLING(node)) {
216  TREE_SIBLING(node)->color = TREE_PARENT(node)->color;
217  }
218 
219  if (NULL != node && NULL != TREE_PARENT(node)) {
220  TREE_PARENT(node)->color = rbBlack;
221 
222  if (NULL != TREE_PARENT(node)->right
223  && node != TREE_PARENT(node)->right) {
224 
225  if (NULL != TREE_SIBLING(node)->right) {
226  TREE_SIBLING(node)->right->color = rbBlack;
227  }
228  //TREE_ROTATE_LEFT(this, TREE_PARENT(node));
229  treeRotateLeft(this, TREE_PARENT(node));
230  } else {
231  if (NULL != TREE_SIBLING(node)->left) {
232  TREE_SIBLING(node)->left->color = rbBlack;
233  }
234  //TREE_ROTATE_RIGHT(this, TREE_PARENT(node));
235  treeRotateRight(this, TREE_PARENT(node));
236  }
237  }
238 
239  break;
240  }
241 
242  delete(del_node);
243  /*
244  * not sure if deleting here is correct.
245  */
246  return data;
247 }
TREE_RIGHT
#define TREE_RIGHT(node)
Definition: tree.h:28
TREE_CHILD
#define TREE_CHILD(node)
Definition: tree.h:32
TREE_PARENT
#define TREE_PARENT(node)
Definition: tree.h:30
comp
static int comp(const void *_a, const void *_b)
Definition: interface.c:32
inOrderSuccessor
Tree inOrderSuccessor(Tree)
Definition: inOrderSuccessor.c:26
treeRotateRight
void treeRotateRight(Tree *, Tree)
Definition: rotateRight.c:26
rbBlack
Definition: tree.h:115
TREE_LEFT
#define TREE_LEFT(node)
Definition: tree.h:29
treeRotateLeft
void treeRotateLeft(Tree *, Tree)
Definition: rotateLeft.c:26
TREE_REPLACE_NODE
#define TREE_REPLACE_NODE(root, node1, node2)
Definition: tree.h:98
rbRed
Definition: tree.h:115
TREE_SIBLING
#define TREE_SIBLING(node)
Definition: tree.h:41

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void treeRotateLeft ( Tree *  ,
Tree   
)

Definition at line 26 of file rotateLeft.c.

Referenced by treeDelete().

27 {
28  Tree rightChild = TREE_RIGHT(node);
29  Tree rcLeftSub = TREE_RIGHT_LEFT(node);
30 
31  rightChild->left = node;
32  rightChild->parent = TREE_PARENT(node);
33  node->right = rcLeftSub;
34  if (NULL != rcLeftSub) {
35  rcLeftSub->parent = node;
36  }
37 
38  if (NULL != TREE_PARENT(node)) {
39  if (TREE_PARENT(node)->left == node) {
40  TREE_PARENT(node)->left = rightChild;
41  } else {
42  TREE_PARENT(node)->right = rightChild;
43  }
44  } else {
45  *this = rightChild;
46  }
47 
48  node->parent = rightChild;
49 }
TREE_RIGHT
#define TREE_RIGHT(node)
Definition: tree.h:28
TREE_PARENT
#define TREE_PARENT(node)
Definition: tree.h:30
TREE_RIGHT_LEFT
#define TREE_RIGHT_LEFT(node)
Definition: tree.h:35

+ Here is the caller graph for this function:

void treeRotateRight ( Tree *  ,
Tree   
)

Definition at line 26 of file rotateRight.c.

Referenced by treeDelete().

27 {
28  Tree leftChild = TREE_LEFT(node);
29  Tree lcRightSub = TREE_LEFT_RIGHT(node);
30 
31  leftChild->right = node;
32  leftChild->parent = TREE_PARENT(node);
33  node->left = lcRightSub;
34  if (NULL != lcRightSub) {
35  lcRightSub->parent = node;
36  }
37 
38  if (NULL != TREE_PARENT(node)) {
39  if (TREE_PARENT(node)->left == node) {
40  TREE_PARENT(node)->left = leftChild;
41  } else {
42  TREE_PARENT(node)->right = leftChild;
43  }
44  } else {
45  *this = leftChild;
46  }
47 
48  node->parent = leftChild;
49 }
TREE_PARENT
#define TREE_PARENT(node)
Definition: tree.h:30
TREE_LEFT_RIGHT
#define TREE_LEFT_RIGHT(node)
Definition: tree.h:38
TREE_LEFT
#define TREE_LEFT(node)
Definition: tree.h:29

+ Here is the caller graph for this function: