1 /*
2 # This file is part of the Astrometry.net suite.
3 # Licensed under a 3-clause BSD style license - see LICENSE
4
5 The AVL tree portion of this code was adapted from GNU libavl,
6 licensed under the GPL v2 or later.
7 */
8
9 #include <stdio.h>
10 #include <errno.h>
11 #include <string.h>
12 #include <assert.h>
13 #include <stdlib.h>
14
15 #include "bt.h"
16
17 /*
18 The AVL tree portion of this code was adapted from GNU libavl.
19 */
20 #define AVL_MAX_HEIGHT 32
21
22 // adapt compare_func to compare_func_2
compare_helper(const void * v1,const void * v2,void * token)23 static int compare_helper(const void* v1, const void* v2, void* token) {
24 compare_func f = token;
25 return f(v1, v2);
26 }
27
28 // data follows the bt_datablock*.
NODE_DATA(bt_leaf * leaf)29 static Const void* NODE_DATA(bt_leaf* leaf) {
30 return leaf+1;
31 }
NODE_CHARDATA(bt_leaf * leaf)32 static Const char* NODE_CHARDATA(bt_leaf* leaf) {
33 return (char*)(leaf+1);
34 }
35
isleaf(bt_node * node)36 static Pure anbool isleaf(bt_node* node) {
37 return node->leaf.isleaf;
38 }
39
node_N(bt_node * node)40 static Pure int node_N(bt_node* node) {
41 if (isleaf(node))
42 return node->leaf.N;
43 return node->branch.N;
44 }
45
sum_childN(bt_branch * branch)46 static Pure int sum_childN(bt_branch* branch) {
47 return node_N(branch->children[0]) + node_N(branch->children[1]);
48 }
49
getchild(bt_node * node,int i)50 static Pure bt_node* getchild(bt_node* node, int i) {
51 if (isleaf(node)) return NULL;
52 return node->branch.children[i];
53 }
54
getleftchild(bt_node * node)55 static Pure bt_node* getleftchild(bt_node* node) {
56 if (isleaf(node)) return NULL;
57 return node->branch.children[0];
58 }
59
getrightchild(bt_node * node)60 static Pure bt_node* getrightchild(bt_node* node) {
61 if (isleaf(node)) return NULL;
62 return node->branch.children[1];
63 }
64
firstleaf(bt_node * node)65 static Pure bt_leaf* firstleaf(bt_node* node) {
66 if (isleaf(node)) return &node->leaf;
67 return node->branch.firstleaf;
68 }
69
height_slow(bt_node * node)70 static int height_slow(bt_node* node) {
71 int hl, hr;
72 if (isleaf(node)) return 1;
73 hl = height_slow(node->branch.children[0]);
74 hr = height_slow(node->branch.children[1]);
75 return 1 + (hl > hr ? hl : hr);
76 }
77
78 #define CHECK(expr) { \
79 int truthval = (expr); \
80 assert(truthval); \
81 if (!truthval) return -1; \
82 }
83
bt_check_node(bt * tree,bt_node * node)84 static int bt_check_node(bt* tree, bt_node* node) {
85 int hl, hr;
86 bt_node* leftmost;
87 if (isleaf(node)) {
88 CHECK(node->leaf.N <= tree->blocksize);
89 return 0;
90 }
91
92 CHECK(sum_childN(&node->branch) == node->branch.N);
93
94 leftmost = node;
95 while (!isleaf(leftmost))
96 leftmost = leftmost->branch.children[0];
97 CHECK(&leftmost->leaf == node->branch.firstleaf);
98
99 hl = height_slow(node->branch.children[0]);
100 hr = height_slow(node->branch.children[1]);
101 CHECK(node->branch.balance == (hr - hl));
102 CHECK((node->branch.balance == 0) ||
103 (node->branch.balance == 1) ||
104 (node->branch.balance == -1));
105
106 if (bt_check_node(tree, node->branch.children[0]) ||
107 bt_check_node(tree, node->branch.children[1]))
108 return -1;
109 return 0;
110 }
111
bt_check(bt * tree)112 int bt_check(bt* tree) {
113 if (tree->root) {
114 CHECK(node_N(tree->root) == tree->N);
115 return bt_check_node(tree, tree->root);
116 }
117 return 0;
118 }
119
bt_new(int datasize,int blocksize)120 bt* bt_new(int datasize, int blocksize) {
121 bt* tree = calloc(1, sizeof(bt));
122 if (!tree) {
123 fprintf(stderr, "Failed to allocate a new bt struct: %s\n", strerror(errno));
124 return NULL;
125 }
126 tree->datasize = datasize;
127 tree->blocksize = blocksize;
128 return tree;
129 }
130
bt_size(bt * tree)131 int bt_size(bt* tree) {
132 return tree->N;
133 }
134
bt_height(bt * tree)135 int bt_height(bt* tree) {
136 bt_node* n;
137 int h;
138 n = tree->root;
139 if (!n) return 0;
140 if (isleaf(n)) return 1;
141 for (h=1; !isleaf(n); h++) {
142 if (n->branch.balance > 0)
143 n = getrightchild(n);
144 else
145 n = getleftchild(n);
146 }
147 return h;
148 }
149
bt_count_leaves_rec(bt_node * node)150 static int bt_count_leaves_rec(bt_node* node) {
151 if (isleaf(node)) return 1;
152 else return
153 bt_count_leaves_rec(node->branch.children[0]) +
154 bt_count_leaves_rec(node->branch.children[1]);
155 }
156
bt_count_leaves(bt * tree)157 int bt_count_leaves(bt* tree) {
158 return bt_count_leaves_rec(tree->root);
159 }
160
bt_free_node(bt_node * node)161 static void bt_free_node(bt_node* node) {
162 if (!isleaf(node)) {
163 bt_free_node(getleftchild(node));
164 bt_free_node(getrightchild(node));
165 }
166 free(node);
167 }
168
bt_free(bt * tree)169 void bt_free(bt* tree) {
170 if (tree->root)
171 bt_free_node(tree->root);
172 free(tree);
173 }
174
get_element(bt * tree,bt_leaf * leaf,int index)175 static Pure void* get_element(bt* tree, bt_leaf* leaf, int index) {
176 return NODE_CHARDATA(leaf) + index * tree->datasize;
177 }
178
first_element(bt_node * n)179 static Pure void* first_element(bt_node* n) {
180 if (isleaf(n)) return NODE_DATA(&n->leaf);
181 else return NODE_DATA(n->branch.firstleaf);
182 }
183
bt_new_branch(bt * tree)184 static Malloc bt_node* bt_new_branch(bt* tree) {
185 bt_node* n = calloc(1, sizeof(bt_node));
186 if (!n) {
187 fprintf(stderr, "Failed to allocate a new bt_node: %s\n", strerror(errno));
188 return NULL;
189 }
190 return n;
191 }
192
bt_new_leaf(bt * tree)193 static Malloc bt_node* bt_new_leaf(bt* tree) {
194 bt_node* n = malloc(sizeof(bt_leaf) + tree->datasize * tree->blocksize);
195 if (!n) {
196 fprintf(stderr, "Failed to allocate a new bt_node: %s\n", strerror(errno));
197 return NULL;
198 }
199 n->leaf.isleaf = 1;
200 n->leaf.N = 0;
201 return n;
202 }
203
bt_leaf_insert(bt * tree,bt_leaf * leaf,void * data,anbool unique,compare_func_2 compare,void * token,void * overflow)204 static anbool bt_leaf_insert(bt* tree, bt_leaf* leaf, void* data, anbool unique,
205 compare_func_2 compare, void* token, void* overflow) {
206 int lower, upper;
207 int nshift;
208 int index;
209
210 // binary search...
211 lower = -1;
212 upper = leaf->N;
213 while (lower < (upper-1)) {
214 int mid;
215 int cmp;
216 mid = (upper + lower) / 2;
217 cmp = compare(data, get_element(tree, leaf, mid), token);
218 if (!cmp && unique) return FALSE;
219 if (cmp >= 0)
220 lower = mid;
221 else
222 upper = mid;
223 }
224 // index to insert at:
225 index = lower + 1;
226
227 // duplicate value?
228 if (unique && (index > 0))
229 if (compare(data, get_element(tree, leaf, index-1), token) == 0)
230 return FALSE;
231
232 // shift...
233 nshift = leaf->N - index;
234 if (leaf->N == tree->blocksize) {
235 // this node is full. insert the element and put the overflowing
236 // element in "overflow".
237 if (nshift) {
238 memcpy(overflow, get_element(tree, leaf, leaf->N-1), tree->datasize);
239 nshift--;
240 } else {
241 memcpy(overflow, data, tree->datasize);
242 return TRUE;
243 }
244 } else {
245 leaf->N++;
246 tree->N++;
247 }
248 memmove(get_element(tree, leaf, index+1),
249 get_element(tree, leaf, index),
250 nshift * tree->datasize);
251 // insert...
252 memcpy(get_element(tree, leaf, index), data, tree->datasize);
253 return TRUE;
254 }
255
next_node(bt_node ** ancestors,int nancestors,bt_node * child,bt_node ** nextancestors,int * nnextancestors)256 static bt_node* next_node(bt_node** ancestors, int nancestors,
257 bt_node* child,
258 bt_node** nextancestors, int* nnextancestors) {
259 // -first, find the first ancestor of whom we are a left
260 // (grand^n)-child.
261 bt_node* parent = NULL;
262 int i, j;
263 for (i=nancestors-1; i>=0; i--) {
264 parent = ancestors[i];
265 if (parent->branch.children[0] == child)
266 break;
267 child = parent;
268 }
269 if (i < 0) {
270 // no next node.
271 return NULL;
272 }
273
274 // we share ancestors from the root to "parent".
275 for (j=i; j>=0; j--)
276 nextancestors[j] = ancestors[j];
277 *nnextancestors = i+1;
278
279 // -next, find the leftmost leaf of the parent's right branch.
280 child = parent->branch.children[1];
281 while (!isleaf(child)) {
282 nextancestors[(*nnextancestors)++] = child;
283 child = child->branch.children[0];
284 }
285 return child;
286 }
287
288 // Pure?
bt_leaf_contains(bt * tree,bt_leaf * leaf,void * data,compare_func_2 compare,void * token)289 static anbool bt_leaf_contains(bt* tree, bt_leaf* leaf, void* data,
290 compare_func_2 compare, void* token) {
291 int lower, upper;
292 lower = -1;
293 upper = leaf->N;
294 while (lower < (upper-1)) {
295 int mid;
296 int cmp;
297 mid = (upper + lower) / 2;
298 cmp = compare(data, get_element(tree, leaf, mid), token);
299 if (cmp == 0) return TRUE;
300 if (cmp > 0)
301 lower = mid;
302 else
303 upper = mid;
304 }
305 // duplicate value?
306 if (lower >= 0)
307 if (compare(data, get_element(tree, leaf, lower), token) == 0)
308 return TRUE;
309 return FALSE;
310 }
311
312 // Pure?
bt_contains(bt * tree,void * data,compare_func compare)313 anbool bt_contains(bt* tree, void* data, compare_func compare) {
314 return bt_contains2(tree, data, compare_helper, compare);
315 }
316
bt_contains2(bt * tree,void * data,compare_func_2 compare,void * token)317 anbool bt_contains2(bt* tree, void* data, compare_func_2 compare, void* token) {
318 bt_node *n;
319 int cmp;
320 int dir;
321
322 if (!tree->root)
323 return FALSE;
324
325 dir = 0;
326 for (n = tree->root; !isleaf(n); n = getchild(n, dir)) {
327 cmp = compare(data, first_element(n->branch.children[1]), token);
328 if (cmp == 0)
329 return TRUE;
330 dir = (cmp > 0);
331 }
332 return bt_leaf_contains(tree, &n->leaf, data, compare, token);
333 }
334
update_firstleaf(bt_node ** ancestors,int nancestors,bt_node * child,bt_leaf * leaf)335 static void update_firstleaf(bt_node** ancestors, int nancestors,
336 bt_node* child, bt_leaf* leaf) {
337 int i;
338 for (i=nancestors-1; i>=0; i--) {
339 if (ancestors[i]->branch.children[0] != child)
340 break;
341 ancestors[i]->branch.firstleaf = leaf;
342 child = ancestors[i];
343 }
344 }
345
bt_insert(bt * tree,void * data,anbool unique,compare_func compare)346 anbool bt_insert(bt* tree, void* data, anbool unique, compare_func compare) {
347 return bt_insert2(tree, data, unique, compare_helper, compare);
348 }
349
bt_insert2(bt * tree,void * data,anbool unique,compare_func_2 compare,void * token)350 anbool bt_insert2(bt* tree, void* data, anbool unique, compare_func_2 compare, void* token) {
351 bt_node *y, *z; /* Top node to update balance factor, and parent. */
352 bt_node *p, *q; /* Iterator, and parent. */
353 bt_node *n; /* Newly inserted node. */
354 bt_node *w; /* New root of rebalanced subtree. */
355 int dir; /* Direction to descend. */
356 bt_node* np;
357
358 bt_node* ancestors[AVL_MAX_HEIGHT];
359 int nancestors = 0;
360 unsigned char da[AVL_MAX_HEIGHT]; /* Cached comparison results. */
361 int k = 0; /* Number of cached results. */
362 unsigned char overflow[tree->datasize];
363 anbool rtn;
364 anbool willfit;
365 int cmp;
366 int i;
367
368 if (!tree->root) {
369 // inserting the first element...
370 n = bt_new_leaf(tree);
371 tree->root = n;
372 bt_leaf_insert(tree, &n->leaf, data, unique, compare, token, NULL);
373 return TRUE;
374 }
375
376 z = y = tree->root;
377 dir = 0;
378
379 for (q = z, p = y;
380 !isleaf(p);
381 q = p, p = p->branch.children[dir]) {
382 cmp = compare(data, first_element(p->branch.children[1]), token);
383 if (unique && (cmp == 0))
384 return FALSE;
385 if (p->branch.balance != 0) {
386 z = q;
387 y = p;
388 k = 0;
389 }
390 ancestors[nancestors++] = p;
391 da[k++] = dir = (cmp > 0);
392 }
393 cmp = compare(data, first_element(p), token);
394
395 // will this element fit in the current node?
396 willfit = (p->leaf.N < tree->blocksize);
397 if (willfit) {
398 rtn = bt_leaf_insert(tree, &p->leaf, data, unique, compare, token, overflow);
399 // duplicate value?
400 if (!rtn)
401 return rtn;
402 for (i=0; i<nancestors; i++)
403 ancestors[i]->branch.N++;
404 return TRUE;
405 }
406
407 da[k++] = (cmp > 0);
408
409 if (cmp > 0) {
410 // insert the new element into this node and shuffle the
411 // overflowing element (which may be the new element)
412 // into the next node, if it exists, or a new node.
413 bt_node* nextnode;
414 bt_node* nextancestors[AVL_MAX_HEIGHT];
415 int nnextancestors;
416
417 /*
418 HACK - should we traverse the tree looking for the next node,
419 or just take the right sibling if we're the left child of a
420 balanced parent?
421 */
422
423 rtn = bt_leaf_insert(tree, &p->leaf, data, unique, compare, token, overflow);
424 if (!rtn)
425 // duplicate value.
426 return rtn;
427 nextnode = next_node(ancestors, nancestors, p, nextancestors, &nnextancestors);
428 assert(!nextnode || isleaf(nextnode));
429 if (nextnode && (nextnode->leaf.N < tree->blocksize)) {
430 // there's room; insert the element!
431 rtn = bt_leaf_insert(tree, &nextnode->leaf, overflow, unique, compare, token, NULL);
432 for (i=0; i<nnextancestors; i++)
433 nextancestors[i]->branch.N++;
434 return rtn;
435 }
436
437 // no room (or no next node); add a new node to the right to hold
438 // the overflowed data.
439 dir = 1;
440 data = overflow;
441 } else {
442 // add a new node to the left.
443 dir = 0;
444 }
445
446 // we have "q", the parent node, and "p", the existing leaf node which is
447 // full. we create a new branch node, "np", to take "p"'s place.
448 // we move "p" down to be the child (1-dir) of "np", and create a new
449 // leaf node, "n", to be child (dir) of "np".
450
451 // create "n", a new leaf node to hold this element.
452 n = bt_new_leaf(tree);
453 if (!n)
454 return FALSE;
455 rtn = bt_leaf_insert(tree, &n->leaf, data, unique, compare, token, NULL);
456 if (!rtn) {
457 free(n);
458 return FALSE;
459 }
460
461 // create "np", a new branch node to take p's place.
462 np = bt_new_branch(tree);
463 if (!np)
464 return FALSE;
465 np->branch.children[dir] = n;
466 np->branch.children[1-dir] = p;
467 np->branch.N = p->leaf.N + 1;
468 np->branch.firstleaf = &(np->branch.children[0]->leaf);
469 if (!isleaf(q)) {
470 if (q->branch.children[0] == p) {
471 q->branch.children[0] = np;
472 if (!dir)
473 update_firstleaf(ancestors, nancestors, np, np->branch.firstleaf);
474 } else if (q->branch.children[1] == p) // need this because it could be that p = q = root.
475 q->branch.children[1] = np;
476 }
477
478 if (p == tree->root)
479 tree->root = np;
480
481 for (i=0; i<nancestors; i++)
482 ancestors[i]->branch.N++;
483
484 if (!y || isleaf(y))
485 return TRUE;
486
487 for (p = y, k = 0;
488 p != np;
489 p = p->branch.children[da[k]], k++)
490 if (da[k] == 0)
491 p->branch.balance--;
492 else
493 p->branch.balance++;
494
495 if (y->branch.balance == -2) {
496 bt_node *x = y->branch.children[0];
497 if (x->branch.balance == -1) {
498 /*
499 y
500 |- x
501 | |- x0
502 | |- x1
503 |- y1
504
505 becomes
506
507 x
508 |- x0
509 |- y
510 . |- x1
511 . |- y1
512 */
513 w = x;
514 y->branch.children[0] = x->branch.children[1];
515 x->branch.children[1] = y;
516 x->branch.balance = y->branch.balance = 0;
517
518 y->branch.firstleaf = firstleaf(y->branch.children[0]);
519 y->branch.N = sum_childN(&y->branch);
520 x->branch.N = sum_childN(&x->branch);
521
522 } else {
523 /*
524 y
525 |- x
526 | |- x0
527 | |- x1 (= w)
528 | |- x10
529 | |- x11
530 |- y1
531
532 becomes
533
534 x1
535 |- x
536 | |- x0
537 | |- x10
538 |- y
539 . |- x11
540 . |- y1
541 */
542
543 assert (x->branch.balance == 1);
544 w = x->branch.children[1];
545 x->branch.children[1] = w->branch.children[0];
546 w->branch.children[0] = x;
547 y->branch.children[0] = w->branch.children[1];
548 w->branch.children[1] = y;
549
550 y->branch.firstleaf = firstleaf(y->branch.children[0]);
551 w->branch.firstleaf = x->branch.firstleaf;
552
553 y->branch.N = sum_childN(&y->branch);
554 x->branch.N = sum_childN(&x->branch);
555 w->branch.N = sum_childN(&w->branch);
556
557 if (w->branch.balance == -1) {
558 x->branch.balance = 0;
559 y->branch.balance = 1;
560 } else if (w->branch.balance == 0)
561 x->branch.balance = y->branch.balance = 0;
562 else {
563 x->branch.balance = -1;
564 y->branch.balance = 0;
565 }
566 w->branch.balance = 0;
567
568 }
569 } else if (y->branch.balance == 2) {
570 bt_node *x = y->branch.children[1];
571 if (x->branch.balance == 1) {
572 /*
573 y
574 |- y0
575 |- x
576 . |- x0
577 . |- x1
578
579 becomes
580
581 x
582 |- y
583 | |- y0
584 | |- x0
585 |- x1
586 */
587 w = x;
588 y->branch.children[1] = x->branch.children[0];
589 x->branch.children[0] = y;
590 x->branch.balance = y->branch.balance = 0;
591
592 x->branch.firstleaf = y->branch.firstleaf;
593
594 y->branch.N = sum_childN(&y->branch);
595 x->branch.N = sum_childN(&x->branch);
596
597
598 } else {
599 /*
600 y
601 |- y0
602 |- x
603 . |- x0
604 . | |- x00
605 . | |- x01
606 . |- x1
607
608 becomes
609
610 x0
611 |- y
612 | |- y0
613 | |- x00
614 |- x
615 . |- x01
616 . |- x1
617 */
618 assert (x->branch.balance == -1);
619 w = x->branch.children[0];
620 x->branch.children[0] = w->branch.children[1];
621 w->branch.children[1] = x;
622 y->branch.children[1] = w->branch.children[0];
623 w->branch.children[0] = y;
624
625 y->branch.N = sum_childN(&y->branch);
626 x->branch.N = sum_childN(&x->branch);
627 w->branch.N = sum_childN(&w->branch);
628
629 x->branch.firstleaf = firstleaf(x->branch.children[0]);
630 w->branch.firstleaf = y->branch.firstleaf;
631
632 if (w->branch.balance == 1) {
633 x->branch.balance = 0;
634 y->branch.balance = -1;
635 } else if (w->branch.balance == 0)
636 x->branch.balance = y->branch.balance = 0;
637 else {
638 x->branch.balance = 1;
639 y->branch.balance = 0;
640 }
641 w->branch.balance = 0;
642
643 }
644 } else
645 goto finished;
646
647 if (y == tree->root)
648 tree->root = w;
649 else {
650 if (y == z->branch.children[0]) {
651 z->branch.children[0] = w;
652 z->branch.firstleaf = w->branch.firstleaf;
653 } else
654 z->branch.children[1] = w;
655 }
656
657 finished:
658 return TRUE;
659 }
660
661 // Pure?
bt_access(bt * tree,int index)662 void* bt_access(bt* tree, int index) {
663 bt_node* n = tree->root;
664 int offset = index;
665 while (!isleaf(n)) {
666 int Nleft = node_N(n->branch.children[0]);
667 if (offset >= Nleft) {
668 n = n->branch.children[1];
669 offset -= Nleft;
670 } else
671 n = n->branch.children[0];
672 }
673 return get_element(tree, &n->leaf, offset);
674 }
675
bt_print_node(bt * tree,bt_node * node,char * indent,void (* print_element)(void * val))676 static void bt_print_node(bt* tree, bt_node* node, char* indent,
677 void (*print_element)(void* val)) {
678 printf("%s", indent);
679 printf("(%p) ", node);
680 printf("N=%i", node_N(node));
681
682 if (!isleaf(node)) {
683 char* subind;
684 char* addind = " ";
685 printf(", leftmost (%p)", node->branch.firstleaf);
686 printf(", Nleft=%i, Nright=%i, balance %i.\n",
687 node_N(node->branch.children[0]),
688 node_N(node->branch.children[1]),
689 node->branch.balance);
690 subind = malloc(strlen(indent) + strlen(addind) + 1);
691 sprintf(subind, "%s%s", indent, addind);
692 printf("%sLeft child:\n", indent);
693 bt_print_node(tree, node->branch.children[0], subind, print_element);
694 printf("%sRight child:\n", indent);
695 bt_print_node(tree, node->branch.children[1], subind, print_element);
696 free(subind);
697 } else {
698 int i;
699 printf(". Leaf.");
700 if (print_element) {
701 printf(" [ ");
702 for (i=0; i<node_N(node); i++)
703 print_element(get_element(tree, &node->leaf, i));
704 }
705 printf("]\n");
706 }
707 }
708
bt_print(bt * tree,void (* print_element)(void * val))709 void bt_print(bt* tree, void (*print_element)(void* val)) {
710 printf(" bt: N=%i, datasize=%i, blocksize=%i.\n", tree->N,
711 tree->datasize, tree->blocksize);
712 printf(" root=(%p)\n", tree->root);
713 if (!tree->root) {
714 printf(" Empty tree.\n");
715 return;
716 }
717 bt_print_node(tree, tree->root, " ", print_element);
718 }
719
bt_print_struct_node(bt * tree,bt_node * node,char * indent,void (* print_element)(void * val))720 static void bt_print_struct_node(bt* tree, bt_node* node, char* indent,
721 void (*print_element)(void* val)) {
722
723 printf("%s", indent);
724 if (!isleaf(node)) {
725 char* subind;
726 char* addind = "|--";
727 printf("(bal %i)\n", node->branch.balance);
728 subind = malloc(strlen(indent) + strlen(addind) + 1);
729 sprintf(subind, "%s%s", indent, addind);
730 bt_print_struct_node(tree, node->branch.children[0], subind, print_element);
731 bt_print_struct_node(tree, node->branch.children[1], subind, print_element);
732 } else {
733 int i;
734 printf("(leaf)");
735 if (print_element) {
736 printf(" [ ");
737 for (i=0; i<node_N(node); i++)
738 print_element(get_element(tree, &node->leaf, i));
739 printf("]");
740 }
741 printf("\n");
742 }
743 }
744
bt_print_structure(bt * tree,void (* print_element)(void * val))745 void bt_print_structure(bt* tree, void (*print_element)(void* val)) {
746 bt_print_struct_node(tree, tree->root, " ", print_element);
747 }
748
749