對于字典樹/前綴樹可能大部分情況很難直觀或者有接觸的體驗，尤其是對前綴這個玩意沒啥概念，可能做題遇到前綴問題也是使用暴力匹配蒙混過關(guān)，如果字符串比較少使用哈希表等結(jié)構(gòu)可能也能蒙混過關(guān)，但如果字符串比較長、相同前綴較多那么使用字典樹可以大大減少內(nèi)存的使用和效率。

一個字典樹的應(yīng)用場景：在搜索框輸入部分單詞下面會有一些神關(guān)聯(lián)的搜索內(nèi)容，你有時候都很神奇是怎么做到的，這其實就是字典樹的一個思想。

一、字典樹trie樹

Trie樹，又叫字典樹、前綴樹（Prefix Tree）、單詞查找樹，是一種多叉樹結(jié)構(gòu)。

二、trie樹的作用

Trie樹的核心思想是空間換時間，利用字符串的公共前綴來減少無謂的字符串比較以達(dá)到提高查詢效率的目的。

（1）核心應(yīng)用

1. 字符串檢索；

2. 詞頻統(tǒng)計；

3. 字符串排序；

4. 前綴匹配。

（2）trie樹節(jié)點

每個字母都占用一個trie樹節(jié)點，根節(jié)點與子節(jié)點沒有本質(zhì)的區(qū)別，主要有這幾個屬性：

1. root: 是否為根節(jié)點

2. dict: 裝子節(jié)點的hash表

3. flag: 是否為一個單詞的結(jié)尾

4. value: 該單詞的完整內(nèi)容（只有在flag為True時才有）

5. count: 該單詞出現(xiàn)的次數(shù)（只有在flag為True時才有）

6. list: 是一個字典，用于遍歷儲存東西的(只有root節(jié)點才有)

class Trie(object):

    def __init__(self, root=None,flag=False,count=None,value=None):
        self.root = root  # root 節(jié)點用于裝內(nèi)容
        self.count = count  # count 用于計數(shù)，可以統(tǒng)計詞頻
        self.dict = {}  # dict 用于裝子節(jié)點，子節(jié)點還是trie樹
        self.flag = flag  # flag用于判斷是否結(jié)束
        self.value = value # value就表示這個單詞是什么
        self.list = {}

（3）常規(guī)操作

先來實現(xiàn)最基礎(chǔ)的四個操作：

1. insert: 增,注意最后一個字母的判斷以及處理即可

2. search: 查

3. delete: 刪

4. startsWith: 判斷前綴是否存在

①增

def insert(self, word):
        """
        :type word: str
        :rtype: None
        """
        trie = self
        for j,i in enumerate(word):
            # 如果是不是最后一個字母就遍歷(或添加)
            if j != len(word) - 1:
                if i not in trie.dict:
                    trie.dict[i] = Trie(root=i)
                trie = trie.dict[i]
            else:
                # 是最后一個字母且flag為true就加計數(shù)
                if i in trie.dict and trie.dict[i].flag:
                    trie = trie.dict[i]
                    trie.count += 1
                # 是最后一個字母但flag為false就修改flag將計數(shù)改為1
                elif i in trie.dict and not trie.dict[i].flag:
                    trie = trie.dict[i]
                    trie.flag = True
                    trie.count = 1
                    trie.value = word
                # 如果trie.dict中沒有就新增
                else:
                    trie.dict[i] = Trie(root=i,flag=True,count=1,value=word)

②查

def search(self, word):
        """
        :type word: str
        :rtype: bool
        """
        trie = self
        for i in word:
            if i in trie.dict:
                trie = trie.dict[i]
            else:
                return False
        return trie.flag

③刪

def delete(self, word):
        '''
        :type word: str
        :rtype: None
        '''
        if self.search(word):
            trie = self
            for i in word:
                if len(trie.dict) == 1:
                    trie.dict.pop(i)
                    break
                else:
                    trie = trie.dict[i]
        else:
            print('該單詞不在trie樹中')

④判斷前綴是否存在

def startsWith(self, prefix):
        """
        :type prefix: str
        :rtype: bool
        """
        trie = self
        for i in prefix:
            if i in trie.dict:
                trie = trie.dict[i]
            else:
                return False
        return True

（4）遍歷操作

遍歷操作就首選DFS深度優(yōu)先搜索,參數(shù)中加入prefix的目的是為了后面的聯(lián)想操作，如果只做遍歷可以不加；值得一提的是，我對子節(jié)點的儲存采用的是字典的形式，遍歷出來的結(jié)果排序剛剛好就是字典序，也就實現(xiàn)了前面說的字符串字典序的處理（其實真要排字典序，直接sorted就好了，沒必要用trie樹）

def dfs(self,path,trie,prefix=''):
        # 如果為真說明走到了一個單詞的結(jié)尾
        if trie.flag:
            self.list[prefix + ''.join(path)] = trie.count
            if trie.dict == {}:
                return
        
        for i in trie.dict:
            path.append(i)
            self.dfs(path,trie.dict[i],prefix)
            path.pop()

給trie樹創(chuàng)建可迭代方法

def __iter__(self):
        self.list = {}  # 重置self.list
        self.dfs([],self)
        return iter(self.list)

（5）聯(lián)想操作

聯(lián)想業(yè)務(wù)應(yīng)該是這樣的： 用戶輸入前幾個字母，然后匹配出完整的單詞，使用頻率越高的單詞理應(yīng)放在最前面；

所以整體思路是這樣的： 根據(jù)前綴找到前綴最后一個字母所在的trie樹節(jié)點，從那個節(jié)點開始進(jìn)行DFS遍歷，然后在遍歷結(jié)果前加上一個前綴，最后將結(jié)果按照count進(jìn)行排序最后以列表形式輸出結(jié)果；

先實現(xiàn)排序算法，這里用的是快速排序,注意比較的值是count，最后留下的是單詞；

def quick_sorted(self,dict):
        '''
        :type dict: dict
        :rtype: list
        '''
        if len(dict) >= 2:
            nums = list(dict.keys())
            mid = nums[len(nums) // 2]
            left, right = {}, {}
            nums.remove(mid)
            for d in nums:
                if dict[d] < dict[mid]:
                    left[d] = dict[d]
                else:
                    right[d] = dict[d]
            return self.quick_sorted(right) + [mid] + self.quick_sorted(left)
        return list(dict.keys())

再實現(xiàn)聯(lián)想操作

def dream(self,prefix):
        '''
        :type prefix: str
        :rtype: list
        '''
        trie = self
        for i in prefix:
            if i in trie.dict:
                trie = trie.dict[i]
            elif dict[d] == dict[mid]:
                if d > mid:
                    right[d] = dict[d]
                else:
                    left[d] = dict[d]
            else:
                return []
        self.list = {}  # 重置self.list
        self.dfs([],trie,prefix)
        return self.quick_sorted(self.list)