---
tags: Data Structure
title: Trie（字典樹）
---
# Trie（字典樹）
[TOC]

## 簡單介紹([Wiki介紹](https://en.wikipedia.org/wiki/Trie))
Trie 這個術語來自於 re**trie**val，一種 tree data structure，也稱為**字典樹**。root node 會是 **空字串（`\0`）**，某一個 node 的 children nodes 都會是有相同的**字首**。

Trie 存的鍵（key）通常是字串，但也可以是其它的結構（如：32-bit value），每個 node 都是存一個 character（或是 bit）。


## 複雜度([GeeksforGeeks](https://www.geeksforgeeks.org/trie-insert-and-search/))
核心思想是空間換時間，降低查詢的時間達到提高效率
不過相比於 hash table 來說還是省空間，因為 Trie 的 node 不是存 key 而是 char

||Average|
|:---:|:---:|
|空間複雜度|$O(mn)$|
|搜尋（search）|$O(n)$|
|插入（insert）|$O(n)$|
|刪除（delete）|$O(n)$|

$n$：Length of the longest word.
$m$：Number of the words.

## 改良版Trie
原本的 Trie，每個 node 的 leaf node 需要 26 個字母的 node，**空間複雜度太高**。

我們可把 node 變成 hash table（如：C++ 的 `unorder_map<char, TrieNode*>`），降低 leaf node 的數量，而且 leaf node 可以存不僅限於英文字母。

## 應用
* 搜尋提示。當輸入一個網址，可以自動搜尋出可能的選擇；沒有完全匹配的搜尋結果，可以返回字首最相似的可能。
* 排序。用於字典排序（Lexicographic sorting）非常方便。

## Pseudo Code
* 每個 TrieNode 的結構

    struct TrieNode {
        struct TrieNode *children[ALPHABAT_SIZE];    /* 每個 node 可能的 children nodes. */
        bool isEndOfWord;                            /* 這個 node 是不是一個 key 的結尾. */
        /* Constructor. */
        TrieNode() {
            isEndOfWord = false;
            for(auto child: children)
                child = NULL;
        };
        /* Destructor. */
        ~TrieNode() {
            isEndOfWord = false;
            for(auto child: children) {
                delete child;
                child = NULL;
            }
        };
    };

* 插入（insert）

    void insert(struct TrieNode *root, string key) {
        struct TrieNode *curr = root;                /* 從 Trie 的 root node 開始. */
        /* Traverse key 中每個 char. */
        for(int i = 0; i < key.length(); i++) {
            int index = key[i] - 'a';                /* char 在 ALPHABAT_SIZE 的位置. */
            if(!curr->children[index])               /* 該位置的 node 是 NULL. */
                curr->children[index] = new TrieNode();
            curr = curr->children[index];            /* 移動到新的 child node 上. */
        }
        curr->isEndOfWord = true;                    /* key 最尾端的 node 設定 isEndOfWord. */
    }

* 搜尋（search）

    bool search(struct TrieNode *root, string key) {
        struct TrieNode *curr = root;                /* 從 Trie 的 root node 開始. */
        /* Traverse key 中每個 char. */
        for(int i = 0; i < key.length(); i++) {
            int index = key[i] - 'a';                /* char 在 ALPHABAT_SIZE 的位置. */
            if(!curr->children[index])               /* 該位置的 node 是 NULL. */
                return false;
            curr = curr->children[index];            /* 移動到新的 child node 上. */
        }
        return curr->isEndOfWord;                    /* Traverse 完 key 後，當前 node 是不是 key 的結尾. */                
    }

* 刪除（delete）

    /* 檢查當前的 node 的 children nodes 是不是都是 NULL. */
    bool isEmpty(struct TrieNode *node) {
        for(auto child: node->children)
            if(child)
                return false;                         /* 有一個 child node 不是 NULL. */
        return true;
    }

    /* 使用 backtracking 來刪除 Trie 中存的 key. */
    struct TrieNode* remove(struct TrieNode *root, string key, int depth=0) {
        /* node 是 NULL，Trie 中並沒有儲存預刪除的 key. */
        if(!root)
            return NULL;
        /* 已經到了要刪除 key 的最後一個 node.  */
        if(depth == key.size()) {
            /* 原本是 key 的結尾，刪除後就不是了. */
            if(root->isEndOfWord)
                root->isEndOfWord = false;
            /* 該 node 的 children node 都是 NULL. */
            if(isEmpty(root)) {
                delete root;                           /* 刪除空間. */
                root = NULL;                           /* 重新指回 NULL. */
            }
            return root;
        }
        int index = key[depth] - 'a';                  /* char 在 ALPHABAT_SIZE 的位置. */
        /* Traverse 到該位置的 node 做刪除. */
        root->children[index] = remove(root->children[index], key, depth+1);
        /* 當前 node 的 children node 都是 NULL 且 該 node 並不是其他 key 的結尾 node，可以放心刪除該 node. */
        if(isEmpty(root) && root->isEndOfWord == false) {
            delete root;
            root = NULL;
        }
        return root;
    }

## 範例題目
* [208. Implement Trie (Prefix Tree)](https://leetcode.com/problems/implement-trie-prefix-tree/)
* [211. Design Add and Search Words Data Structure](https://leetcode.com/problems/design-add-and-search-words-data-structure/)
* [421. Maximum XOR of Two Numbers in an Array](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/)