Mercurial > hg > Members > Moririn

comparison src/llrb/verifier/llrbContextWithVerifier.c @ 100:3d7ecced7e14

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Split functions which gets tree height
author Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
date Tue, 02 Feb 2016 16:12:34 +0900
parents
children 870453d5b096
comparison
equal deleted inserted replaced
99:ca55f4be5f0f 100:3d7ecced7e14
1 #include "llrbContextWithVerifier.h"
2
3 unsigned int min_height(struct Node* node, unsigned int height) {
4 if ((node->left == NULL) && (node->right == NULL)) return height;
5 if (node->left == NULL) return min_height(node->right, height+1);
6 if (node->right == NULL) return min_height(node->left, height+1);
7
8 unsigned int left_min = min_height(node->left, height+1);
9 unsigned int right_min = min_height(node->right, height+1);
10
11 if (left_min < right_min) {
12 return left_min;
13 } else {
14 return right_min;
15 }
16 }
17
18 unsigned int max_height(struct Node* node, unsigned int height) {
19 if ((node->left == NULL) && (node->right == NULL)) return height;
20 if (node->left == NULL) return max_height(node->right, height+1);
21 if (node->right == NULL) return max_height(node->left, height+1);
22
23 unsigned int left_max = max_height(node->left, height+1);
24 unsigned int right_max = max_height(node->right, height+1);
25
26 if (left_max > right_max) {
27 return left_max;
28 } else {
29 return right_max;
30 }
31 }
32
33 void verify_tree_height(struct Node* root) {
34 if (root == NULL) return;
35
36 unsigned int min_h = min_height(root, 1);
37 unsigned int max_h = max_height(root, 1);
38
39 if (max_h >= 2*min_h) {
40 printf("llrb-condition violated.\n");
41 printf("\tmin-height %u", min_h);
42 printf("\tmax-height %u", max_h);
43 exit(EXIT_FAILURE);
44 }
45 }