字典树的实现

发表于 | 阅读次数

简单字典树的实现

字典树特征

根节点不包含字符，除去根节点的每一个节点均包含有一个字符。
从根节点到某一节点，路径上经过的所有节点的字符连接起来就是该节点对应的字符串。
每个节点的所有子节点包含的字符都不相同

字典树基本操作

  • 插入
  • 查找
  • 删除

插入操作

向字典树中插入某个单词。将单词标记为当前单词，将根节点标记为当前节点，执行操作1：

1.当前单词为空，将当前节点标记为单词位置，终止操作；否则取出当前单词的首字符记为X，遍历当前节点的子节点：如果X存在于子节点N，将剩余字符标记为当前单词，将N标记为当前节点，重复操作1，如果X不存在于当前节点的子节点中，那么进入操作2。

2.取出当前单词的首字符记为X，新建一个节点M存储X，M的父节点为当前节点。剩余字符串记为当前单词，如果当前单词为空，将M标记为单词位置，终止操作；否则，将M标记为当前节点，重复操作2。

查找操作

查询指定单词是否在字典树中。将单词标记为当前单词，将根节点标记为当前节点，执行操作1：

1.当前单词为空，那么返回true，即字典树中存在该单词。否则，取出当前单词的首字符，标记为X，遍历当前节点的子节点，如果X存在于子节点N中，将N标记为当前节点，将剩余字符串标记为当前单词，重复操作1；如果X不存在于子节点中，返回false，即字典树中不存在该单词。

删除操作

删除字典树中的某个单词。将单词标记为当前单词，将根节点标记为当前节点，执行操作1：

1.当前单词为空，如果当前节点不为叶子节点，那么取消标记当前节点为单词位置，当前节点为叶子节点，删除该叶子节点即可，然后终止操作。当前单词不为空，取出当前单词的首字符记为X，遍历当前节点的子节点：如果X存在于当前节点的子节点N上，将N标记为当前节点，将剩余字符串记为当前单词，重复过程1；否则删除失败，即单词不在字典树上，终止操作。

python 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
# -*- coding: utf -*-
class Trie_tree(object):
    def __init__(self):
        # node = [father, child, keep_char, is_word]
        self._root = [None, [], None, False]
        self.tmp = []
    def insert(self, word):
        current_word = word
        current_node = self._root
        self._insert_operation_1(current_word, current_node)
    def _insert_operation_1(self, current_word, current_node):
        if current_word:
            first_char = current_word[0]
            child_node = current_node[1]
            is_in_child_node = False
            for node in child_node:
                if first_char == node[2]:
                    is_in_child_node = True
                    current_word = current_word[1:]
                    current_node = node
                    self._insert_operation_1(current_word, current_node)
                    break
            if not is_in_child_node:
                self._insert_operation_2(current_word, current_node)
        else:
            current_node[3] = True
    def _insert_operation_2(self, current_word, current_node):
        first_char = current_word[0]
        # create a new node and insert it in the tree
        new_node = [None, [], None, False]
        new_node[2] = first_char
        new_node[0] = current_node
        current_node[1].append(new_node) # add in child
        current_word = current_word[1:]
        if current_word:
            current_node = new_node
            self._insert_operation_2(current_word, current_node)
        else:
            new_node[3] = True
    def find(self, word):
        current_word = word
        current_node = self._root
        return self._find_operation(current_word, current_node)
    def _find_operation(self, current_word, current_node):
        if current_word:
            first_char = current_word[0]
            child_node = current_node[1]
            if not child_node:
                return False
            is_in_child_node = False
            for node in child_node:
                if first_char == node[2]:
                    is_in_child_node =True
                    current_word = current_word[1:]
                    current_node = node
                    return self._find_operation(current_word, current_node)
            if not is_in_child_node:
                return False
        else:
            return current_node[3]
    def delete(self, word):
        current_word = word
        current_node = self._root
        return self._delete_operation(current_word, current_node)
    def _delete_operation(self, current_word, current_node):
        if current_word:
            first_char = current_word[0]
            child_node = current_node[1]
            if not child_node:
                return False
            is_in_child_node = False
            for node in child_node:
                if first_char == node[2]:
                    is_in_child_node = True
                    current_word = current_word[1:]
                    current_node = node
                    return self._delete_operation(current_word, current_node)
            if not is_in_child_node:
                return False
        else:
            if current_node[1]:
                current_node[3] = False
            # current_node is leaf_node
            else:
                father_node = current_node[0]
                father_node[1].remove(current_node)
            return True
    def print_tree(self, current_node):
        if current_node:
            self._dfs_print(current_node)
    def _dfs_print(self, current_node):
        if current_node[2]:
            self.tmp.append(current_node[2])
        # if it is a word
        if current_node[3]:
            print ("".join(self.tmp))
        for child in current_node[1]:
            self._dfs_print(child)
        if self.tmp:
            self.tmp.pop()
if __name__ == '__main__':
    demo_trie = Trie_tree()
    print ("--------Insert:---------")
    for word in ["apps", "apple", "cook", "cookie", "cold"]:
        print (word)
        demo_trie.insert(word)
    print ("--------Print Test:---------")
    demo_trie.print_tree(demo_trie._root)
    print ("--------Find Test:--------")
    print ("ap:     ", demo_trie.find("ap"))
    print ("apps:   ", demo_trie.find("apps"))
    print ("apple:  ", demo_trie.find("apple"))
    print ("apples: ", demo_trie.find("apples"))
    print ("coo:    ", demo_trie.find("coo"))
    print ("cook:   ", demo_trie.find("cook"))
    print ("cookie: ", demo_trie.find("cookie"))
    print ("cold:   ", demo_trie.find("cold"))
    print ("--------Delete Test:--------")
    demo_trie.delete("cookie")
    print ("> Delete cookie")
    print ("Find cook   ?", demo_trie.find("cook"))
    print ("Find cookie ?", demo_trie.find("cookie"))
    demo_trie.delete("apple")
    print ("> Delete apple")
    print ("Find apps   ?", demo_trie.find("apps"))
    print ("Find apple  ?", demo_trie.find("apple"))
    print ("--------Print Test:---------")
    demo_trie.print_tree(demo_trie._root)

输出结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
--------Insert:---------
apps
apple
cook
cookie
cold
--------Print Test:---------
apps
apple
cook
cookie
cold
--------Find Test:--------
ap:      False
apps:    True
apple:   True
apples:  False
coo:     False
cook:    True
cookie:  True
cold:    True
--------Delete Test:--------
> Delete cookie
Find cook   ? True
Find cookie ? False
> Delete apple
Find apps   ? True
Find apple  ? False
--------Print Test:---------
apps
cook
cold
[Finished in 0.1s]