54,7 → 54,7 |
|
|
static int test_tree_balance(avltree_node_t *node); |
static avltree_node_t *tree_test_parents(avltree_node_t *node); |
static avltree_node_t *test_tree_parents(avltree_node_t *node); |
static void print_tree_structure_flat (avltree_node_t *node, int level); |
static avltree_node_t *alloc_avltree_node(void); |
|
98,7 → 98,7 |
/** |
* Prints the structure of node, which is level levels from the top of the tree. |
*/ |
static void print_tree_structure_flat (const avltree_node_t *node, int level) |
static void print_tree_structure_flat (avltree_node_t *node, int level) |
{ |
/* You can set the maximum level as high as you like. |
Most of the time, you'll want to debug code using small trees, |
115,16 → 115,16 |
printf ("%d[%d]", node->key,node->balance); |
if (node->lft != NULL || node->rgt != NULL) |
{ |
putchar ('('); |
printf("("); |
|
print_tree_structure_flat (node->lft, level + 1); |
if (node->rgt != NULL) |
{ |
putchar (','); |
printf(","); |
print_tree_structure_flat (node->rgt, level + 1); |
} |
|
putchar (')'); |
printf(")"); |
} |
} |
|
135,7 → 135,7 |
int i; |
|
for (i = 0; i < NODE_COUNT - 1; i++) { |
avltree_nodes[i].n = &(avltree_nodes[i+1]); |
avltree_nodes[i].par = &(avltree_nodes[i+1]); |
} |
/* |
* Node keys which will be used for insertion. Up to NODE_COUNT size of array. |
172,7 → 172,7 |
for (i = 21; i < NODE_COUNT; i++) |
avltree_nodes[i].key = i * 3; |
|
avltree_nodes[i].n = NULL; |
avltree_nodes[i].par = NULL; |
first_free_node = &(avltree_nodes[0]); |
} |
|
181,7 → 181,7 |
avltree_node_t *node; |
|
node = first_free_node; |
first_free_node = first_free_node->n; |
first_free_node = first_free_node->par; |
|
return node; |
} |
197,7 → 197,7 |
*/ |
avltree_create(tree); |
|
if (!quiet) printf("\n\nInserting %d nodes ...\n", node_count); |
if (!quiet) printf("\nInserting %d nodes ...\n", node_count); |
|
for (i = 0; i < node_count; i++) { |
newnode = alloc_avltree_node(); |
213,26 → 213,7 |
if (!quiet) printf("Inserting was finished\n"); |
} |
|
/* |
static avltree_node_t *tree_random_delete_node(avltree_t *tree, int node_count, int r, bool quiet) |
{ |
avltree_node_t *delnode; |
int i; |
|
for (i = 0,delnode = tree->head.n; i < (r-1); i++) |
delnode = delnode->n; |
|
if (delnode == &tree->head) { |
if (!quiet) printf("Try to delete head! Node count: %d, number of deleted node: %d\n",node_count,r); |
return NULL; |
} |
|
avltree_delete(tree, delnode); |
|
return delnode; |
} |
*/ |
|
static void test_tree_delete(avltree_t *tree, int node_count, int node_position, bool quiet) |
{ |
avltree_node_t *delnode; |
243,7 → 224,7 |
|
switch(node_position) { |
case 0: //mazani vzdy korene |
if (!quiet) printf("\n\nDelete root nodes\n"); |
if (!quiet) printf("\nDelete root nodes\n"); |
while(tree->root != NULL) { |
delnode = tree->root; |
avltree_delete(tree,delnode); |
255,7 → 236,7 |
|
break; |
case 1: |
if (!quiet) printf("\n\nDelete nodes according to their time of origin\n"); |
if (!quiet) printf("\nDelete nodes according to their time of origin\n"); |
for (i = 0; i < node_count; i++) { |
avltree_delete(tree,&(avltree_nodes[i])); |
if (!quiet) { |
274,9 → 255,9 |
{ |
int i = 0; |
|
if (!quiet) printf("Timeout tree ...\n"); |
if (!quiet) printf("\nTimeout tree ...\n"); |
|
while(tree->head.n != &(tree->head)) { |
while(tree->root != NULL) { |
i++; |
avltree_delete_min(tree); |
if (!quiet) { |
285,62 → 266,24 |
} |
} |
|
if (!quiet && (i != node_count)) printf("Bad node count. Some nodes have been lost!"); |
if (!quiet && (i != node_count)) printf("Bad node count. Some nodes have been lost!\n"); |
|
if (!quiet) printf("Timeout tree finished\n"); |
} |
|
/* |
void timeout_tree_run(avltree_t *tree, int operation_count, int verbal) |
{ |
int i; |
avltree_node_t *node; |
int r; |
int count; |
|
//inicializace stromu: |
avltree_create(tree); |
|
for(i = 0, count = 0; i < operation_count; i++) { |
if (tree->count && ((rand() % NODE_COUNT) <= tree->count)) { |
if ((r = rand()) % DELETE_PROB == 1) { //mazu nahodne |
node = tree_random_delete_node(tree,(r % tree->count)); |
//printf("DELETE key: %d, number: %d,address: %p\n",node->key,r % (tree->count+1),node); |
node->n = first_free_node; |
first_free_node = node; |
} else { |
node = tree->head.n; |
avltree_delete_min(tree); |
//printf("TIMEOUT key: %d, address: %p\n",node->key,node); |
node->n = first_free_node; |
first_free_node = node; |
} |
} else { |
node = alloc_avltree_node_random(); |
//printf("INSERT key: %d, address: %p\n",node->key + tree->basetime,node); |
avltree_insert(tree, node); |
} |
//test_tree_height(tree->root,1); |
//tree_test_parents(tree->root); |
//print_tree_link(tree->count); |
//print_tree_structure_flat(tree->root,0); putchar('\n'); putchar('\n'); |
} |
} |
*/ |
|
char * test_avltree1(bool quiet) |
{ |
alloc_avltree_node_prepare(); |
test_tree_insert(&tree, NODE_COUNT, quiet); |
test_tree_delete(&tree, NODE_COUNT, 0, quiet); |
test_tree_insert(&avltree, NODE_COUNT, quiet); |
test_tree_delete(&avltree, NODE_COUNT, 0, quiet); |
|
alloc_avltree_node_prepare(); |
test_tree_insert(&tree, NODE_COUNT, quiet); |
test_tree_delete(&tree, NODE_COUNT, 1, quiet); |
test_tree_insert(&avltree, NODE_COUNT, quiet); |
test_tree_delete(&avltree, NODE_COUNT, 1, quiet); |
|
alloc_avltree_node_prepare(); |
test_tree_insert(&tree, NODE_COUNT, quiet); |
timeout_tree(&tree, NODE_COUNT, quiet); |
test_tree_insert(&avltree, NODE_COUNT, quiet); |
timeout_tree(&avltree, NODE_COUNT, quiet); |
|
return NULL; |
} |