11_trie.c

Download
c 401 lines 11.6 KB 
  1/*
  2 * ํŠธ๋ผ์ด (Trie)
  3 * Prefix Tree, Autocomplete, XOR Trie
  4 *
  5 * ๋ฌธ์ž์—ด ๊ฒ€์ƒ‰์„ ์œ„ํ•œ ํŠธ๋ฆฌ ์ž๋ฃŒ๊ตฌ์กฐ์ž…๋‹ˆ๋‹ค.
  6 */
  7
  8#include <stdio.h>
  9#include <stdlib.h>
 10#include <string.h>
 11#include <stdbool.h>
 12
 13#define ALPHABET_SIZE 26
 14
 15/* =============================================================================
 16 * 1. ๊ธฐ๋ณธ ํŠธ๋ผ์ด
 17 * ============================================================================= */
 18
 19typedef struct TrieNode {
 20    struct TrieNode* children[ALPHABET_SIZE];
 21    bool is_end;
 22    int count;  /* ์ด ์ ‘๋‘์‚ฌ๋กœ ์‹œ์ž‘ํ•˜๋Š” ๋‹จ์–ด ์ˆ˜ */
 23} TrieNode;
 24
 25TrieNode* trie_create_node(void) {
 26    TrieNode* node = malloc(sizeof(TrieNode));
 27    node->is_end = false;
 28    node->count = 0;
 29    for (int i = 0; i < ALPHABET_SIZE; i++)
 30        node->children[i] = NULL;
 31    return node;
 32}
 33
 34void trie_free(TrieNode* node) {
 35    if (node == NULL) return;
 36    for (int i = 0; i < ALPHABET_SIZE; i++)
 37        trie_free(node->children[i]);
 38    free(node);
 39}
 40
 41void trie_insert(TrieNode* root, const char* word) {
 42    TrieNode* node = root;
 43    while (*word) {
 44        int idx = *word - 'a';
 45        if (node->children[idx] == NULL)
 46            node->children[idx] = trie_create_node();
 47        node = node->children[idx];
 48        node->count++;
 49        word++;
 50    }
 51    node->is_end = true;
 52}
 53
 54bool trie_search(TrieNode* root, const char* word) {
 55    TrieNode* node = root;
 56    while (*word) {
 57        int idx = *word - 'a';
 58        if (node->children[idx] == NULL)
 59            return false;
 60        node = node->children[idx];
 61        word++;
 62    }
 63    return node->is_end;
 64}
 65
 66bool trie_starts_with(TrieNode* root, const char* prefix) {
 67    TrieNode* node = root;
 68    while (*prefix) {
 69        int idx = *prefix - 'a';
 70        if (node->children[idx] == NULL)
 71            return false;
 72        node = node->children[idx];
 73        prefix++;
 74    }
 75    return true;
 76}
 77
 78int trie_count_prefix(TrieNode* root, const char* prefix) {
 79    TrieNode* node = root;
 80    while (*prefix) {
 81        int idx = *prefix - 'a';
 82        if (node->children[idx] == NULL)
 83            return 0;
 84        node = node->children[idx];
 85        prefix++;
 86    }
 87    return node->count;
 88}
 89
 90/* =============================================================================
 91 * 2. ๋‹จ์–ด ์‚ญ์ œ
 92 * ============================================================================= */
 93
 94bool trie_delete_helper(TrieNode* node, const char* word, int depth) {
 95    if (node == NULL) return false;
 96
 97    if (*word == '\0') {
 98        if (!node->is_end) return false;
 99        node->is_end = false;
100
101        /* ์ž์‹์ด ์—†์œผ๋ฉด ์‚ญ์ œ ๊ฐ€๋Šฅ */
102        for (int i = 0; i < ALPHABET_SIZE; i++) {
103            if (node->children[i]) return false;
104        }
105        return true;
106    }
107
108    int idx = *word - 'a';
109    if (trie_delete_helper(node->children[idx], word + 1, depth + 1)) {
110        free(node->children[idx]);
111        node->children[idx] = NULL;
112
113        /* ํ˜„์žฌ ๋…ธ๋“œ๋„ ์‚ญ์ œ ๊ฐ€๋Šฅํ•œ์ง€ ํ™•์ธ */
114        if (!node->is_end) {
115            for (int i = 0; i < ALPHABET_SIZE; i++) {
116                if (node->children[i]) return false;
117            }
118            return true;
119        }
120    }
121
122    return false;
123}
124
125void trie_delete(TrieNode* root, const char* word) {
126    trie_delete_helper(root, word, 0);
127}
128
129/* =============================================================================
130 * 3. ์ž๋™์™„์„ฑ
131 * ============================================================================= */
132
133void autocomplete_helper(TrieNode* node, char* prefix, int prefix_len,
134                         char** results, int* count, int max_results) {
135    if (*count >= max_results) return;
136
137    if (node->is_end) {
138        results[*count] = malloc(prefix_len + 1);
139        strcpy(results[*count], prefix);
140        (*count)++;
141    }
142
143    for (int i = 0; i < ALPHABET_SIZE; i++) {
144        if (node->children[i]) {
145            prefix[prefix_len] = 'a' + i;
146            prefix[prefix_len + 1] = '\0';
147            autocomplete_helper(node->children[i], prefix, prefix_len + 1,
148                               results, count, max_results);
149        }
150    }
151}
152
153char** autocomplete(TrieNode* root, const char* prefix, int* result_count, int max_results) {
154    char** results = malloc(max_results * sizeof(char*));
155    *result_count = 0;
156
157    /* ์ ‘๋‘์‚ฌ ๋…ธ๋“œ ์ฐพ๊ธฐ */
158    TrieNode* node = root;
159    char* current_prefix = malloc(100);
160    strcpy(current_prefix, prefix);
161    int prefix_len = strlen(prefix);
162
163    while (*prefix) {
164        int idx = *prefix - 'a';
165        if (node->children[idx] == NULL) {
166            free(current_prefix);
167            return results;
168        }
169        node = node->children[idx];
170        prefix++;
171    }
172
173    autocomplete_helper(node, current_prefix, prefix_len, results, result_count, max_results);
174    free(current_prefix);
175    return results;
176}
177
178/* =============================================================================
179 * 4. ์™€์ผ๋“œ์นด๋“œ ๊ฒ€์ƒ‰
180 * ============================================================================= */
181
182bool wildcard_search_helper(TrieNode* node, const char* word) {
183    if (*word == '\0')
184        return node->is_end;
185
186    if (*word == '.') {
187        for (int i = 0; i < ALPHABET_SIZE; i++) {
188            if (node->children[i] && wildcard_search_helper(node->children[i], word + 1))
189                return true;
190        }
191        return false;
192    }
193
194    int idx = *word - 'a';
195    if (node->children[idx] == NULL)
196        return false;
197    return wildcard_search_helper(node->children[idx], word + 1);
198}
199
200bool wildcard_search(TrieNode* root, const char* pattern) {
201    return wildcard_search_helper(root, pattern);
202}
203
204/* =============================================================================
205 * 5. XOR ํŠธ๋ผ์ด (๋น„ํŠธ ํŠธ๋ผ์ด)
206 * ============================================================================= */
207
208typedef struct XORTrieNode {
209    struct XORTrieNode* children[2];
210} XORTrieNode;
211
212XORTrieNode* xor_trie_create_node(void) {
213    XORTrieNode* node = malloc(sizeof(XORTrieNode));
214    node->children[0] = NULL;
215    node->children[1] = NULL;
216    return node;
217}
218
219void xor_trie_free(XORTrieNode* node) {
220    if (node == NULL) return;
221    xor_trie_free(node->children[0]);
222    xor_trie_free(node->children[1]);
223    free(node);
224}
225
226void xor_trie_insert(XORTrieNode* root, int num) {
227    XORTrieNode* node = root;
228    for (int i = 31; i >= 0; i--) {
229        int bit = (num >> i) & 1;
230        if (node->children[bit] == NULL)
231            node->children[bit] = xor_trie_create_node();
232        node = node->children[bit];
233    }
234}
235
236int xor_trie_max_xor(XORTrieNode* root, int num) {
237    XORTrieNode* node = root;
238    int result = 0;
239
240    for (int i = 31; i >= 0; i--) {
241        int bit = (num >> i) & 1;
242        int want = 1 - bit;  /* ๋ฐ˜๋Œ€ ๋น„ํŠธ ์„ ํ˜ธ */
243
244        if (node->children[want]) {
245            result |= (1 << i);
246            node = node->children[want];
247        } else if (node->children[bit]) {
248            node = node->children[bit];
249        } else {
250            break;
251        }
252    }
253
254    return result;
255}
256
257int find_max_xor_pair(int arr[], int n) {
258    XORTrieNode* root = xor_trie_create_node();
259    int max_xor = 0;
260
261    xor_trie_insert(root, arr[0]);
262
263    for (int i = 1; i < n; i++) {
264        int xor_val = xor_trie_max_xor(root, arr[i]);
265        if (xor_val > max_xor) max_xor = xor_val;
266        xor_trie_insert(root, arr[i]);
267    }
268
269    xor_trie_free(root);
270    return max_xor;
271}
272
273/* =============================================================================
274 * 6. ์ตœ์žฅ ๊ณตํ†ต ์ ‘๋‘์‚ฌ
275 * ============================================================================= */
276
277char* longest_common_prefix(char* strs[], int n) {
278    if (n == 0) return "";
279
280    TrieNode* root = trie_create_node();
281
282    /* ์ฒซ ๋ฒˆ์งธ ๋ฌธ์ž์—ด๋งŒ ์‚ฝ์ž… */
283    trie_insert(root, strs[0]);
284
285    char* lcp = malloc(strlen(strs[0]) + 1);
286    int lcp_len = 0;
287
288    TrieNode* node = root;
289    const char* first = strs[0];
290
291    while (*first) {
292        int idx = *first - 'a';
293
294        /* ๋ถ„๊ธฐ๊ฐ€ ์žˆ๊ฑฐ๋‚˜ ๋‹จ์–ด ๋์ด๋ฉด ์ค‘๋‹จ */
295        int child_count = 0;
296        for (int i = 0; i < ALPHABET_SIZE; i++) {
297            if (node->children[i]) child_count++;
298        }
299
300        if (child_count != 1 || node->is_end)
301            break;
302
303        /* ๋‹ค๋ฅธ ๋ฌธ์ž์—ด์—์„œ ์ด ์ ‘๋‘์‚ฌ ํ™•์ธ */
304        bool all_match = true;
305        for (int i = 1; i < n; i++) {
306            if (strs[i][lcp_len] != *first) {
307                all_match = false;
308                break;
309            }
310        }
311
312        if (!all_match) break;
313
314        lcp[lcp_len++] = *first;
315        node = node->children[idx];
316        first++;
317    }
318
319    lcp[lcp_len] = '\0';
320    trie_free(root);
321    return lcp;
322}
323
324/* =============================================================================
325 * ํ…Œ์ŠคํŠธ
326 * ============================================================================= */
327
328int main(void) {
329    printf("============================================================\n");
330    printf("ํŠธ๋ผ์ด (Trie) ์˜ˆ์ œ\n");
331    printf("============================================================\n");
332
333    /* 1. ๊ธฐ๋ณธ ํŠธ๋ผ์ด */
334    printf("\n[1] ๊ธฐ๋ณธ ํŠธ๋ผ์ด ์—ฐ์‚ฐ\n");
335    TrieNode* trie = trie_create_node();
336
337    const char* words[] = {"apple", "app", "apricot", "banana", "band"};
338    printf("    ์‚ฝ์ž…: apple, app, apricot, banana, band\n");
339    for (int i = 0; i < 5; i++)
340        trie_insert(trie, words[i]);
341
342    printf("    search('app'): %s\n", trie_search(trie, "app") ? "true" : "false");
343    printf("    search('apt'): %s\n", trie_search(trie, "apt") ? "true" : "false");
344    printf("    startsWith('ap'): %s\n", trie_starts_with(trie, "ap") ? "true" : "false");
345    printf("    countPrefix('ap'): %d\n", trie_count_prefix(trie, "ap"));
346
347    /* 2. ์‚ญ์ œ */
348    printf("\n[2] ๋‹จ์–ด ์‚ญ์ œ\n");
349    printf("    delete('app')\n");
350    trie_delete(trie, "app");
351    printf("    search('app'): %s\n", trie_search(trie, "app") ? "true" : "false");
352    printf("    search('apple'): %s\n", trie_search(trie, "apple") ? "true" : "false");
353
354    /* 3. ์ž๋™์™„์„ฑ */
355    printf("\n[3] ์ž๋™์™„์„ฑ\n");
356    int result_count;
357    char** suggestions = autocomplete(trie, "ap", &result_count, 10);
358    printf("    'ap'๋กœ ์‹œ์ž‘ํ•˜๋Š” ๋‹จ์–ด:\n");
359    for (int i = 0; i < result_count; i++) {
360        printf("      - %s\n", suggestions[i]);
361        free(suggestions[i]);
362    }
363    free(suggestions);
364
365    /* 4. ์™€์ผ๋“œ์นด๋“œ */
366    printf("\n[4] ์™€์ผ๋“œ์นด๋“œ ๊ฒ€์ƒ‰\n");
367    printf("    search('b.nd'): %s\n", wildcard_search(trie, "b.nd") ? "true" : "false");
368    printf("    search('b..d'): %s\n", wildcard_search(trie, "b..d") ? "true" : "false");
369    printf("    search('.pple'): %s\n", wildcard_search(trie, ".pple") ? "true" : "false");
370
371    trie_free(trie);
372
373    /* 5. XOR ํŠธ๋ผ์ด */
374    printf("\n[5] XOR ํŠธ๋ผ์ด - ์ตœ๋Œ€ XOR ์Œ\n");
375    int arr[] = {3, 10, 5, 25, 2, 8};
376    printf("    ๋ฐฐ์—ด: [3, 10, 5, 25, 2, 8]\n");
377    printf("    ์ตœ๋Œ€ XOR: %d\n", find_max_xor_pair(arr, 6));
378
379    /* 6. ์ตœ์žฅ ๊ณตํ†ต ์ ‘๋‘์‚ฌ */
380    printf("\n[6] ์ตœ์žฅ ๊ณตํ†ต ์ ‘๋‘์‚ฌ\n");
381    char* strs[] = {"flower", "flow", "flight"};
382    char* lcp = longest_common_prefix(strs, 3);
383    printf("    [\"flower\", \"flow\", \"flight\"]\n");
384    printf("    LCP: '%s'\n", lcp);
385    free(lcp);
386
387    /* 7. ๋ณต์žก๋„ */
388    printf("\n[7] ํŠธ๋ผ์ด ๋ณต์žก๋„ (m = ๋ฌธ์ž์—ด ๊ธธ์ด)\n");
389    printf("    | ์—ฐ์‚ฐ         | ์‹œ๊ฐ„๋ณต์žก๋„ |\n");
390    printf("    |--------------|------------|\n");
391    printf("    | ์‚ฝ์ž…         | O(m)       |\n");
392    printf("    | ๊ฒ€์ƒ‰         | O(m)       |\n");
393    printf("    | ์ ‘๋‘์‚ฌ ๊ฒ€์ƒ‰  | O(m)       |\n");
394    printf("    | ์‚ญ์ œ         | O(m)       |\n");
395    printf("    | ๊ณต๊ฐ„         | O(n * m)   |\n");
396
397    printf("\n============================================================\n");
398
399    return 0;
400}