avl.c (3267B)
1 #include <ctype.h> 2 #include <limits.h> 3 #include <stdio.h> 4 #include <stdint.h> 5 #include <stdlib.h> 6 #include <time.h> 7 8 #include "tree.h" 9 10 #include "config.h" 11 12 typedef struct Node Node; 13 14 15 inline Node * 16 init(int val) 17 { 18 Node *n = emalloc(sizeof(Node)); 19 if (n == NULL) 20 return NULL; 21 22 n->val = val; 23 n->left = NULL; 24 n->right = NULL; 25 26 return n; 27 } 28 29 30 Node * 31 add(Node *root, int val) 32 { 33 if (!root) 34 return init(val); 35 36 if (val < root->val) 37 root->left = add(root->left, val); 38 else if (val > root->val) 39 root->right = add(root->right, val); 40 else 41 return root; 42 43 return balance(root); 44 } 45 46 int 47 get_height(Node *root) 48 { 49 int r, l; 50 51 if (!root) 52 return 0; 53 54 l = get_height(root->left) + 1; 55 r = get_height(root->right) + 1; 56 57 if (l > r) { 58 return l; 59 } 60 61 return r; 62 } 63 64 65 static inline int 66 get_balance_factor(Node *root) 67 { 68 if (!root) 69 return 0; 70 71 return get_height(root->left) - get_height(root->right); 72 } 73 74 75 Node * 76 right_turn(Node *root) 77 { 78 if (!root || !root->left) 79 return root; 80 81 Node *buf = root->left; 82 root->left = buf->right; 83 buf->right = root; 84 return buf; 85 } 86 87 88 Node * 89 left_turn(Node *root) 90 { 91 if (!root || !root->right) 92 return root; 93 94 Node *buf = root->right; 95 root->right = buf->left; 96 buf->left = root; 97 return buf; 98 } 99 100 101 Node * 102 balance(Node *root) 103 { 104 if (!root) 105 return NULL; 106 107 int bf = get_balance_factor(root); 108 109 110 if (bf > 1) { 111 if (get_balance_factor(root->left) < 0) 112 root->left = left_turn(root->left); 113 return right_turn(root); 114 } 115 116 if (bf < -1) { 117 if (get_balance_factor(root->right) > 0) 118 root->right = right_turn(root->right); 119 return left_turn(root); 120 } 121 122 return root; 123 } 124 125 126 Node * 127 search(Node *root, int val) 128 { 129 if (root->val == val) return root; 130 131 if (root->val > val) return search(root->left, val); 132 133 return search(root->right, val); 134 } 135 136 static inline void 137 usage(void) 138 { 139 eprintf("usage: %s [-c] [-s] [-d] [filename]\n", argv0); 140 } 141 142 int 143 main(int argc, char *argv[]) 144 { 145 int cflag = 0, sflag = 0, dflag = 0; 146 ARGBEGIN { 147 case 'c': 148 cflag = 1; 149 break; 150 case 's': 151 sflag = 1; 152 break; 153 case 'd': 154 eprintf("Not implemented\n"); 155 dflag = 1; 156 break; 157 } ARGEND 158 if (argc > 1 || (cflag + sflag + dflag) < 1) 159 usage(); 160 const char *filename; 161 if (argc == 1) 162 filename = argv[0]; 163 else 164 filename = FILENAME; 165 166 FILE *file; 167 if (!(file = fopen(filename, "r"))) 168 eprintf("fopen %s:", filename); 169 170 int arr[TESTNUMBER+1], ch; 171 char w[64]; 172 int len = 0, wi = 0; 173 do { 174 ch = fgetc(file); 175 if (!isspace(ch) && ch != EOF) { 176 w[wi++] = ch; 177 } else if (wi > 0) { 178 w[wi] = '\0'; 179 arr[len++] = estrtonum(w, 0, INT_MAX); 180 wi = 0; 181 } 182 } while (ch != EOF && len <= TESTNUMBER); 183 efshut(file, filename); 184 if (len < TESTNUMBER) 185 eprintf("Array too small\n"); 186 if (len > TESTNUMBER) 187 weprintf("Array too big - using only the first %d elements\n", TESTNUMBER); 188 189 Node *root = NULL; 190 clock_t start_time, elapsed = 0; 191 192 if (cflag) 193 start_time = clock(); 194 for (int i = 0; i < TESTNUMBER; ++i) 195 root = add(root, arr[i]); 196 if (cflag) 197 elapsed += clock() - start_time; 198 199 volatile uintptr_t checksum = 0; /* to avoid optimization */ 200 if (sflag) { 201 start_time = clock(); 202 for (int i = 0; i < TESTNUMBER; ++i) 203 checksum = (uintptr_t)search(root, arr[i]); 204 elapsed += clock() - start_time; 205 } 206 207 printf("%f\n", (double)elapsed/CLOCKS_PER_SEC); 208 }