1. #include <stddef.h>
2. #include <stdio.h>
3. #include <stdlib.h>
4. #include <string.h>
5.  
6. /* Minh họa ánh xạ char * => int dựa trên cây
7.    nhị phân tìm kiếm. */
8.  
9. struct bst_node {
10.   char key[100];
11.   int value;
12.   struct bst_node *left;
13.   struct bst_node *right;
14.   struct bst_node *top;
15. };
16.  
17. typedef int (*cmp_fnt)(const void *, const void *);
18.  
19. struct bst_tree {
20.   struct bst_node *root;
21.   int size;
22.   cmp_fnt cmp;
23. };
24.  
25. struct bst_node *bst_node(char *key, int value) {
26.   struct bst_node *nn = malloc(sizeof(struct bst_node));
27.   strcpy(nn->key, key);
28.   nn->value = value;
29.   nn->left = NULL;
30.   nn->right = NULL;
31.   nn->top = NULL;
32.   return nn;
33. }
34.  
35. struct bst_tree *bst_tree(cmp_fnt cmp) {
36.   struct bst_tree *t = malloc(sizeof(struct bst_tree));
37.   t->cmp = cmp;
38.   t->root = NULL;
39.   t->size = 0;
40. }
41.  
42. /**
43.  * Thêm cặp (key, value) vào cây t,
44.  * trong trường hợp key đã tồn tại thì trả về con trỏ
45.  * tới giá trị của nút tương ứng với key.
46.  * Nếu khóa chưa tồn tại thì trả về NULL.
47.  */
48. int *bst_put(struct bst_tree *t, char *key, int value) {
49.   if (t->root == NULL) {
50.     t->root = bst_node(key, value);
51.     ++t->size;
52.     return NULL;
53.   }
54.   struct bst_node *p = t->root, *c;
55.   int r;
56.   for(;;) {
57.     r = t->cmp(key, p->key);
58.     if (r == 0) {
59.       return &p->value;
60.     }
61.     c = r < 0? p->left: p->right;
62.     if (!c) {
63.       break;
64.     }
65.     p = c;
66.   }
67.   struct bst_node *nn = bst_node(key, value);
68.   if (r < 0) {
69.     p->left = nn;
70.   } else {
71.     p->right = nn;
72.   }
73.   nn->top = p;
74.   ++t->size;
75.   return NULL;
76. }
77.  
78. int *bst_search(struct bst_tree *t, char *key) {
79.   struct bst_node *u = t->root;
80.   while (u) {
81.     int r = t->cmp(key, u->key);
82.     if (r == 0) {
83.       return &u->value;
84.     }
85.     u = r < 0 ? u->left: u->right;
86.   }
87.   return NULL;
88. }
89.  
90. struct bst_node *bst_pvalnode(int *pval) {
91.   return pval? ((void*)pval) - offsetof(struct bst_node, value): NULL;
92. }
93.  
94. /* Xóa nút tương ứng với khóa khỏi cây
95.  * Trả về 1 nếu đã xóa, hoặc 0 nếu khóa không tồn tại
96.  */
97. int bst_remove(struct bst_tree *t, char *key) {
98.   struct bst_node *dn = bst_pvalnode(bst_search(t, key));
99.   if (!dn) {
100.     return 0;
101.   }
102.   struct bst_node *node = dn;
103.   struct bst_node *child = node->right, *tmp = node->left, *top;
104.   struct bst_node *p;
105.   if (!tmp) {
106.     top = node->top;
107.     if (top) {
108.       if (top->left == node) {
109.         top->left = child;
110.       } else {
111.         top->right = child;
112.       }
113.     } else {
114.       t->root = child;
115.     }
116.     if (child) {
117.       child->top = top;
118.     }
119.   } else if (!child) {
120.     top = node->top;
121.     if (top) {
122.       if (top->left == node) {
123.         top->left = tmp;
124.       } else {
125.         top->right = tmp;
126.       }
127.     } else {
128.       t->root = tmp;
129.     }
130.     tmp->top = top;
131.   } else {
132.     struct bst_node *successor = child, *child2;
133.     tmp = child->left;
134.     if (!tmp) {
135.       top = successor;
136.       child2 = successor->right;
137.     } else {
138.       do {
139.         top = successor;
140.         successor = tmp;
141.         tmp = tmp->left;
142.       } while (tmp);
143.       child2 = successor->right;
144.       top->left = child2;
145.       successor->right = child;
146.       child->top = successor;
147.     }
148.     tmp = node->left;
149.     successor->left = tmp;
150.     tmp->top = successor;
151.     p = node->top;
152.     tmp = p;
153.     if (tmp) {
154.       if (tmp->left == node) {
155.         tmp->left = successor;
156.       } else {
157.         tmp->right = successor;
158.       }
159.     } else {
160.       t->root = successor;
161.     }
162.     if (child2) {
163.       child2->top = top;
164.     }
165.     successor->top = p;
166.     tmp = successor;
167.   }
168.   free(dn);
169.   --t->size;
170.   return 1;
171. }
172.  
173. void bst_node_print_lnr(struct bst_node *n, int depth) {
174.   if (n->left) {
175.     bst_node_print_lnr(n->left, depth + 1);
176.   }
177.   for (int i = 0; i < depth * 2; ++i) {
178.     printf(" ");
179.   }
180.   printf("(%s: %d)\n", n->key, n->value);
181.   if (n->right) {
182.     bst_node_print_lnr(n->right, depth + 1);
183.   }
184. }
185.  
186. void bst_pprint(struct bst_tree *t) {
187.   printf("size: %d\n", t->size);
188.   if (t->root) {
189.     bst_node_print_lnr(t->root, 0);
190.   }
191. }
192.  
193. int cmps(const void *p1, const void *p2) {
194.   return strcmp(p1, p2);
195. }
196.  
197. int main() {
198.   struct bst_tree *t = bst_tree(cmps);
199.   char key[100];
200.   int value;
201.   while (scanf("%s", key) == 1) {
202.     if (strcmp(key, "***") == 0) {
203.       break;
204.     }
205.     scanf("%d", &value;);
206.     bst_put(t, key, value);
207.   }
208.   bst_pprint(t);
209.   while (scanf("%s", key) == 1) {
210.     if (strcmp(key, "***") == 0) {
211.       break;
212.     }
213.     int *pval = bst_search(t, key);
214.     if (pval) {
215.       printf("Found: (%s: %d)\n", bst_pvalnode(pval)->key, *pval);
216.     } else {
217.       printf("Key %s not exists\n", key);
218.     }
219.   }
220.   while (scanf("%s", key) == 1) {
221.     int ret = bst_remove(t, key);
222.     if (ret) {
223.       printf("Đã xóa %s\n", key);
224.       bst_pprint(t);
225.     } else {
226.       printf("Không tìm thấy %s\n", key);
227.     }
228.   }
229. }