Trie树——字典

我们设计树的数据结构，很多时候都是为了更高效的查找。Trie树就是一种为了快速查找指定前缀的数据结构，它的形式很像我们翻查英语字典一样，所以也被人们称为前缀树、字典树。比如说，我们在一棵字典树中保存了"haoma", "haode", "haoya", "enna"四个字符串。如右图所示，我们完全可以不设定一个根节点，但为了体现其树的特性，我们保持图中根节点是空的，不存储任何键值。

Trie树的字典形式体现在它的数据存储方式上，"haoma", "haode", "haoya"三个字符串具有相同的前缀"hao"，所以在树中节点'm','d','y'具有相同的父节点。我们在树中查找一个字符串，完全可以从根节点开始，依次向下查找字符串的每个元素。当我们成功的遍历了每个元素就找到了对应的字符串，如果在遍历过程中，有一个元素不匹配就说明树中没有该字符串。所以其查找复杂度是\(O(n)\)的，其中\(n\)是字符串的长度。

向Trie树中插入一个字符串的复杂度也是\(O(n)\)的。和查找操作一样，我们需要从根节点开始，依次向下查找字符串的前缀。如果前缀覆盖了整个字符串，意味着树中本来就已经存在了给定的字符串，不需要再创建新的节点了。只要遍历字符串过程中，树中已保存的前缀不能覆盖字符串，就需要为剩余的元素创建新的节点。

从Trie树中删除一个字符串是一个从下向上的过程，我们需要先通过查找操作从叶子节点开始，依次根据其父节点指针，向上追溯到根节点，把整个追溯过程中经历的节点移除。这个过程也是\(O(n)\)复杂度的。

在空间上，Trie是一种多叉树，用相同的节点记录了字符串的共同前缀，相比于完整的记录下每个字符串，可以极大的节省存储空间。本文中，我们用C++模板的形式实现Trie树，它不仅仅可以用于存储字符串，也可以存放其它数据类型的数组序列。

        template <class KeyType, class ValueType>
        class DictionaryNode {
            public:
                KeyType key;
                ValueType value;
                int depth;
                DictionaryNode *p;
            protected:
                RBTree<DictionaryNode> children;
        };

1. 空间结构

右面的代码片段是字典节点中成员变量的定义。我们采用键值对的形式定义节点，键key实际存储了字符串的各个元素是Trie树的各种操作的对象。值value记录了前缀所对应的数据，相当于我们查字典后给出的翻译。为了体现Dictionary可以用于不同的数据类型，这里使用模板类型KeyType和ValueType来定义键值对。

此外，我们还为节点定义了一个整型成员变量depth用于记录节点在树中的深度，它也描述了节点所对应前缀的长度。指针变量p记录了当前节点的父节点，如果我们沿着该指针变量向上追溯，就可以获得对应的前缀。

我们用一个红黑树来记录孩子节点。之所以选择红黑树，是因为整个字典树的插入、查找和删除操作都需要对孩子节点进行大量的查找操作。为了提高系统的查找效率，我们使用红黑树来作为容器记录字典树节点。实际上对于KeyType的值域范围比较小的情况，我们完全可以使用线性表的结构。

由于红黑树的插入查找等操作需要对键值进行对比，所以我们为字典节点重载了如下的两个操作符，用于以节点的键值来参与对比操作。这两个重载分别用于非常量和常量的对象。

        & operator KeyType() { return key; }
        & operator const KeyType() const { return key; }

下面的代码片段是字典树的成员变量定义。为了方便敲代码，我们通过typedef定义了一个NodeType的类型，并定义了一个私有的成员变量root，这个root就是字典树中空的根节点。

        template <class KeyType, class ValueType>
        class Dictionary {
                typedef DictionaryNode<KeyType, ValueType> NodeType;
            private:
                NodeType root;
        };

2. 插入

下面左边的函数是Dictionary中插入一个数组的接口，它有两个函数，其中buf是数组序列的缓存，len则指定了序列的长度。在该函数中，它依次遍历数组中的每个元素，并调用字典节点的add_child函数，将数组元素添加到字典中。

        // class Dictionary<KeyType, ValueType>
        NodeType * insert(KeyType const * buf, int len) {
            NodeType *pNode = &root;

            for (int i = 0; i < len; i++)
                pNode = pNode->add_child(buf[i]);

            return pNode;
        }

        // class DictionaryNode<KeyType, ValueType>
        DictionaryNode  * add_child(KeyType const & data) {
            RBTreeNode *rbnode = children.find(data);
            if (NULL == rbnode) {
                rbnode = children.insert(DictionaryNode(data));
                rbnode->key.depth = depth+1;
                rbnode->key.p = this;
            }
            return &(rbnode->key);
        }

上面右边的函数则是字典节点对象的add_child接口。在该函数中，首先通过红黑树接口查找数组元素。如果孩子节点中不存在对应的元素，将得到一个空指针NULL。此时就需要在红黑树中新建一个节点，如代码中第5行所示。同时修改新建节点的深度和父节点指针。

3. 查找

下面左边的函数是Dictionary中用于查找给定数组序列的接口，同样的buf是数组序列缓存，len是序列长度。在函数中，从根节点开始依次向下查找序列中的各个元素。中间只要有一个元素没有查找到，就说明对应的数组序列不在字典中，函数返回空指针NULL。

        // class Dictionary<KeyType, ValueType>
        NodeType * find(KeyType const * buf, int len) {
            NodeType *pNode = &root;
            for (int i = 0; i < len; i++) {
                pNode = pNode->find_child(buf[i]);
                if (NULL == pNode)
                    return NULL;
            }
            return pNode;
        }

        // class DictionaryNode<KeyType, ValueType>
        DictionaryNode * find_child(KeyType const & data) {
            RBTreeNode *rbnode = children.find(data);

            if (NULL == rbnode)
                return NULL;

            return &(rbnode->key);
        }

上面右边的函数是字典节点中用于查找孩子集合中是否存在指定元素的接口。该函数仍然是调用红黑树的find接口，如果不存在将得到一个空指针，否则就返回对应的字典节点。

4. 删除

下面左边仍然以buf和len只是数组序列和序列长度，来进行删除操作。在该函数中，首先需要先检查一下字典中是否存在目标序列。如果不存在目标序列，或者查找到的序列节点还有孩子节点，我们将不执行删除操作，直接报错返回。在以上两个条件都不满足的情况下，我们从叶节点开始沿着父节点指针p向上追溯，依次删除经过的各个节点。

        // class Dictionary<KeyType, ValueType>
        bool remove(KeyType const * buf, int len) {
            NodeType *pNode = find(buf, len);
            if (NULL == pNode || pNode->num_children() > 0)
                return false;
            NodeType *p = pNode->p;
            while (NULL != p) {
                p->remove_child(pNode->key);
                pNode = p;
                p = pNode->p;
            }
            return true;
        }

        // class DictionaryNode<KeyType, ValueType>
        bool remove_child(KeyType const & data) {
            RBTreeNode *rbnode = children.find(data);

            if (NULL == rbnode || !rbnode->key.children.empty())
                return false;

            children.remove(rbnode);
            return true;
        }

上面右边的函数是字典节点中移除孩子节点的接口。该函数先检查孩子节点中是否存在指定节点，如果存在则调用红黑树的移除接口执行移除操作。

5. 追溯

追溯的目的就是给定字典节点，根据其父节点指针依次向上查询，知道根节点为止，并记录下经历的节点键值返回。该函数有两个参数，其中buf是输出缓存用于记录经过的节点键值， len则指示了需要追溯的序列长度，该函数最后会返回一个数据，指示了实际追溯的序列长度。

        // class DictionaryNode<KeyType, ValueType>
        int trace_back(KeyType *buf, int len) const {
            DictionaryNode const *pNode = this;
            len = (depth < len) ? depth : len;
            int re = len;
            for (; 0 <= len; len--) {
                buf[len] = pNode->key;
                pNode = pNode->p;
            }
            return re;
        }

由于节点的深度决定了实际可以追溯的序列长度，所以这里取节点的深度和len的最小值作为实际的追溯长度，如代码中第4行所示。在第6到9行的循环中，我们沿着父节点指针p依次向上追溯，并将追溯到的键值记录在buf中。

6. 完

本文中，我们用C++模板提供了一个字典树的实现，并介绍了插入、查找、删除和追溯操作，这些操作都是\(O(n)\)的复杂度，其中\(n\)是序列长度。