字符串问题---字典树(前缀树)的实现

时间:2022-12-30 14:52:37

【题目】

  字典树又称为前缀树或者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