taskrambler  v0.1.8
Web server and task management solution.
binarytree.c
Go to the documentation of this file.
1 #include <stdio.h>
2 #include <stdlib.h>
3 
4 
5 struct element
6 {
7  int data;
8 
9  struct element * parent;
10  struct element * left;
11  struct element * right;
12 };
13 
14 struct element *
16 {
17  struct element * el = malloc(sizeof(struct element));
18  el->data = data;
19  el->parent = NULL;
20  el->left = NULL;
21  el->right = NULL;
22 
23  return el;
24 }
25 
26 /**
27  * find element in tree
28  */
29 struct element *
30 findElement(struct element * tree, int data)
31 {
32  while (NULL != tree) {
33  if (tree->data == data) {
34  break;
35  }
36 
37  if (data < tree->data) {
38  tree = tree->left;
39  } else {
40  tree = tree->right;
41  }
42  }
43 
44  return tree;
45 }
46 
47 /**
48  * insert element in tree
49  */
50 void
51 insertElement(struct element ** tree, int data)
52 {
53  struct element * node = *tree;
54 
55  if (NULL == node) {
56  *tree = newElement(data);
57  return;
58  }
59 
60  while (data != node->data) {
61  if (data < node->data) {
62  if (NULL == node->left) {
63  node->left = newElement(data);
64  node->left->parent = node;
65  return;
66  } else {
67  node = node->left;
68  }
69  } else {
70  if (NULL == node->right) {
71  node->right = newElement(data);
72  node->right->parent = node;
73  return;
74  } else {
75  node = node->right;
76  }
77  }
78  }
79 }
80 
81 /**
82  * delete element from tree
83  * here multiple functions are involved....
84  * =======================================================================
85  */
86 /**
87  * find minimum of the right subtree aka leftmost leaf of right subtree
88  * aka left in-order successor.
89  * We return the parent of the element in the out argument parent.
90  * This can be NULL wenn calling.
91  */
92 struct element *
94 {
95  struct element * node = tree->right;
96 
97  while (NULL != node->left) {
98  node = node->left;
99  }
100 
101  return node;
102 }
103 
104 void
105 deleteElement(struct element ** tree, int data)
106 {
107  struct element * node = *tree;
108 
109  // find the relevant node and it's parent
110  while (NULL != node && node->data != data) {
111  if (data < node->data) {
112  node = node->left;
113  } else {
114  node = node->right;
115  }
116  }
117 
118  // element not found
119  if (NULL == node) {
120  return;
121  }
122 
123  // distinuish 3 cases, where the resolving of each case leads to the
124  // precondition of the other.
125 
126  // case 1: two children
127  if (NULL != node->left && NULL != node->right) {
128  struct element * successor = findInOrderSuccessor(node);
129 
130  node->data = successor->data;
131  node = successor;
132  }
133 
134  // case 2: one child wither left or right
135  if (NULL != node->left) {
136  //node->data = node->left->data;
137  //node = node->left;
138  if (NULL != node->parent) {
139  if (node == node->parent->left) {
140  node->parent->left = node->left;
141  } else {
142  node->parent->right = node->left;
143  }
144  }
145  node->left->parent = node->parent;
146  }
147 
148  if (NULL != node->right) {
149  //node->data = node->right->data;
150  //node = node->right;
151  if (NULL != node->parent) {
152  if (node == node->parent->left) {
153  node->parent->left = node->right;
154  } else {
155  node->parent->right = node->right;
156  }
157  }
158  node->right->parent = node->parent;
159  }
160 
161  // case 3: we are a leaf
162  if (NULL != node->parent) {
163  if (node == node->parent->left) {
164  node->parent->left = NULL;
165  } else {
166  node->parent->right = NULL;
167  }
168  }
169 
170  if (node == *tree) {
171  if (NULL != node->left) {
172  *tree = node->left;
173  } else if (NULL != node->right) {
174  *tree = node->right;
175  } else {
176  *tree = NULL;
177  }
178  }
179 
180  free(node);
181 }
182 
183 
184 void
185 traverse(struct element * tree, void (*cb)(int, int))
186 {
187  struct element * previous = tree;
188  struct element * node = tree;
189  int depth = 1;
190 
191  /*
192  * I think this has something like O(n+log(n)) on a ballanced
193  * tree because I have to traverse back the rightmost leaf to
194  * the root to get a break condition.
195  */
196  while (node) {
197  /*
198  * If we come from the right so nothing and go to our
199  * next parent.
200  */
201  if (previous == node->right) {
202  previous = node;
203  node = node->parent;
204  depth--;
205  continue;
206  }
207 
208  if ((NULL == node->left || previous == node->left)) {
209  /*
210  * If there are no more elements to the left or we
211  * came from the left, process data.
212  */
213  cb(node->data, depth);
214  previous = node;
215 
216  if (NULL != node->right) {
217  node = node->right;
218  depth++;
219  } else {
220  node = node->parent;
221  depth--;
222  }
223  } else {
224  /*
225  * if there are more elements to the left go there.
226  */
227  previous = node;
228  node = node->left;
229  depth++;
230  }
231  }
232 }
233 
234 void printElement(int data, int depth)
235 {
236  int i;
237 
238  printf("%02d(%02d)", data, depth);
239  for (i=0; i<depth; i++) printf("-");
240  puts("");
241 }
242 
243 /**
244  * =======================================================================
245  */
246 int
247 main(int argc, char * argv[])
248 {
249  struct element * root = NULL;
250 
251  insertElement(&root, 13);
252  insertElement(&root, 8);
253  insertElement(&root, 16);
254  insertElement(&root, 11);
255  insertElement(&root, 3);
256  insertElement(&root, 9);
257  insertElement(&root, 12);
258  insertElement(&root, 10);
259 
260  /*
261  * delete does not work correctly here..
262  * luckily I do not need the simple binary trees anymore
263  * as I have rbtrees.
264  */
265  puts("traverse");
266  traverse(root, printElement);
267 
268  deleteElement(&root, 8);
269  puts("traverse");
270  traverse(root, printElement);
271 
272  deleteElement(&root, 11);
273  puts("traverse");
274  traverse(root, printElement);
275 
276  deleteElement(&root, 13);
277  puts("traverse");
278  traverse(root, printElement);
279 
280  deleteElement(&root, 3);
281  puts("traverse");
282  traverse(root, printElement);
283 
284  deleteElement(&root, 16);
285  puts("traverse");
286  traverse(root, printElement);
287 
288  deleteElement(&root, 10);
289  puts("traverse");
290  traverse(root, printElement);
291 
292  deleteElement(&root, 9);
293  puts("traverse");
294  traverse(root, printElement);
295 
296  deleteElement(&root, 12);
297  puts("traverse");
298  traverse(root, printElement);
299 
300  return 0;
301 }
302 
303 // vim: set et ts=4 sw=4:
struct element * right
Definition: binarytree.c:11
struct element * findInOrderSuccessor(struct element *tree)
Definition: binarytree.c:93
static void(* cb)(const void *)
Definition: each.c:27
struct element * left
Definition: binarytree.c:10
void insertElement(struct element **tree, int data)
Definition: binarytree.c:51
struct element * parent
Definition: binarytree.c:9
int main(int argc, char *argv[])
Definition: binarytree.c:247
int data
Definition: binarytree.c:7
struct element * newElement(int data)
Definition: binarytree.c:15
void deleteElement(struct element **tree, int data)
Definition: binarytree.c:105
struct element * findElement(struct element *tree, int data)
Definition: binarytree.c:30
void printElement(int data, int depth)
Definition: binarytree.c:234
void traverse(struct element *tree, void(*cb)(int, int))
Definition: binarytree.c:185