字符串问题---字典树（前缀树）的实现

【题目】

　　字典树又称为前缀树或者Trie树，是处理字符串常用的数据结构。假设组成所有单词的字符仅是‘a’～‘z’，请实现字典树的结构，并包含以下四个主要的功能。

void insert(String word)：添加word，可重复添加
void delete(String word)：删除word，如果word添加过多次，仅删除一次
boolean search(String word)：查询word是否在字典树中
int prefixNumber(String pre)：返回以字符串pre作为前缀的单词数量

【基本思路】

　　字典树介绍。字典树是一种树形结构，优点是利用字符串的公共前缀来节约存储空间。如图，是插入abc, abcd, abd, b, bcd, efg, hik后的字典树。
　　　　　　　　　字符串问题---字典树（前缀树）的实现
　　字典树的基本性质如下：
　　1.根节点没有字符路径。除根节点外，每一个节点都被一个字符路径找到。
　　2.从根节点到某一节点，将路径上经过的字符连接起来，为扫过的对应字符串。
　　3.每个节点向下所有的字符路径上的字符都不同。

下面介绍有关字典树节点的类型，首先定义节点类。

class TrieNode:
def __init__(self):
        self.path = 0
        self.end = 0 
        self.map = [None for i in range(26)]

　　TrieNode类中，path表示有多少个单词共用这个节点，end表示有多少个单词以这个单词结尾，map是一个哈希表结构，key代表该节点的一条字符路径，value表示字符路径指向的节点，根据题目的说明，map是一个长度为26的数组（相当于一棵有26个孩子的树），在字符种类较多的时候可以使用真实的哈希表结构实现map。下面介绍Trie树类如何实现。

void insert(String word)：假设word的长度为N。从左到右遍历word中的每个字符，并依次从头节点开始根据每一个word[i]，找到下一个节点。如果该节点不存在就新建一个，记为a，令a.path = 1.如果节点存在，记为b，令b + 1。通过最后一个字符找到最后一个节点时记为e，令e.path + 1，e.end + 1
boolean search(String word)：从左到右遍历word中字符，并依次从头节点根据word[i]找到下一个节点。如果找的过程中节点不存在，直接返回False。如果能通过最后一个字符找到最后一个节点，并且该节点的end值不等于0，返回True。如果最后一个节点的end值为0，说明word只是一个前缀，返回False
void delete(String word)：先调用search函数看word在不在树中，如果不在，直接返回。否则，进入如下的操作。从左到右依次遍历word中的字符，并依次从头节点根据word[i]找到下一个节点。在找的过程中，把扫过的每个节点的path值减 1 。如果发现下一个path的值减完为0，直接从当前节点的map中删除后续的所有路径，返回即可。如果扫到最后一个节点。记为e，令e.path，e.end都减1
int prefixNumber(String pre)：和查找操作同理，根据pre不断找到节点，假设最后的节点记为e，返回e.path即可

下面是使用python3.5实现的代码。

class Trie:
def __init__(self):
        self.root = TrieNode()

def insert(self, word):
if word == None:
return
        node = self.root
for i in word:
            index = ord(i) - ord('a')
if node.map[index] == None:
                node.map[index] = TrieNode()
            node = node.map[index]
            node.path += 1
        node.end += 1
        print("Inset successful")

def search(self, word):
if word == None:
return False
        node = self.root
for i in word:
            index = ord(i) - ord('a')
if node.map[index] == None:
return False
            node = node.map[index]
return True if node.end != 0 else False

def delete(self, word):
if self.search(word):
            node = self.root
for i in word:
                index = ord(i) - ord('a')
                node.map[index].path -= 1
if node.map[index].path == 0:
                    node.map[index] = None
return
                node = node.map[index]
            node.end -= 1

def prefixNumber(self, pre):
if pre == None:
return
        node = self.root
for i in pre:
            index = ord(i) - ord('a')
if node.map[index] == None:
return 0
            node = node.map[index]
return node.path

秒客网

字符串问题---字典树（前缀树）的实现

相关文章