簡單字典樹實現

MonoLog 發布于2019-07-31 11:32 / 859人閱讀

摘要：查找操作查詢指定單詞是否在字典樹中。將單詞標記為當前單詞，將根節點標記為當前節點，執行操作當前單詞為空，那么返回，即字典樹中存在該單詞。字典樹的簡單實現插入操作查找操作刪除操作具體實現放在上，可以在這里找到。

原文地址

字典樹介紹

我們經常會在網上輸入一些單詞，一般情況下，當我們輸入幾個字母時，輸入框中會自動彈出以這些字母開頭的單詞供我們選擇，用戶體驗非常好。

不過這種自動提示功能到底是怎么實現的呢？這就要用到我們的前綴樹了，前綴樹也叫字典樹、Trie樹。假如我們有一個簡單的字典，里面包含以下幾個單詞：apps apple cook cookie cold，那么可以構建以下樹：

圖1. 簡單的字典樹

當我們輸入a時，程序會遍歷a的子樹，找出所有的單詞，這里就是apps和apple了。繼續輸入ppl，那么只用遍歷appl下面的子樹，然后即得到apple。同理，輸入co時，會遍歷o下面的子樹，取得單詞cook, cookie, cold。這里的單詞不一定都在葉節點上，像上例中的cook就是在其中一個子節點上。

從上面的圖中，我們可以總結出字典樹的一些特征來：

根節點不包含字符，除去根節點的每一個節點均包含有一個字符。

從根節點到某一節點，路徑上經過的所有節點的字符連接起來就是該節點對應的字符串。

每個節點的所有子節點包含的字符都不相同。

字典樹的基本操作

字典樹有三個基本操作：插入，查找，刪除：

插入操作：向字典樹中插入某個單詞。將單詞標記為當前單詞，將根節點標記為當前節點，執行操作1：

當前單詞為空，將當前節點標記為單詞位置，終止操作；否則取出當前單詞的首字符記為X，遍歷當前節點的子節點：如果X存在于子節點N，將剩余字符標記為當前單詞，將N標記為當前節點，重復操作1，如果X不存在于當前節點的子節點中，那么進入操作2。

取出當前單詞的首字符記為X，新建一個節點M存儲X，M的父節點為當前節點。剩余字符串記為當前單詞，如果當前單詞為空，將M標記為單詞位置，終止操作；否則，將M標記為當前節點，重復操作2。

查找操作：查詢指定單詞是否在字典樹中。將單詞標記為當前單詞，將根節點標記為當前節點，執行操作1：

當前單詞為空，那么返回true，即字典樹中存在該單詞。否則，取出當前單詞的首字符，標記為X，遍歷當前節點的子節點，如果X存在于子節點N中，將N標記為當前節點，將剩余字符串標記為當前單詞，重復操作1；如果X不存在于子節點中，返回false，即字典樹中不存在該單詞。

刪除操作：刪除字典樹中的某個單詞。將單詞標記為當前單詞，將根節點標記為當前節點，執行操作1：

當前單詞為空，如果當前節點不為葉子節點，那么取消標記當前節點為單詞位置，當前節點為葉子節點，刪除該葉子節點即可，然后終止操作。當前單詞不為空，取出當前單詞的首字符記為X，遍歷當前節點的子節點：如果X存在于當前節點的子節點N上，將N標記為當前節點，將剩余字符串記為當前單詞，重復過程1；否則刪除失敗，即單詞不在字典樹上，終止操作。

字典樹的簡單實現

插入操作：

def insert(word):
    current_word = word
    current_node = root
    insert_operation_1(current_word, current_node)

def insert_operation_1(current_word, current_node):
    if current_word not empty:
        X = current_word[0]

        if X in current_node.child:
            current_word = current_word[1:]
            current_node = child_node
            insert_operation_1(current_word, current_node)
        else:
            insert_operation_2(current_word, current_node)

    else:
        mark current_node insert_node 

def insert_operation_2(current_word, current_node):
    X = current_word[0]
    M.value = x
    M.father = current_node
    current_node.child = M

    current_word = current_word[1:]
    if current_word not empty:
        current_node = M
        insert_operation_2(current_word, current_node)

    else:
        mark M insert_node

查找操作：

def find(word):
    current_word = word
    current_node = root
    return find_opration(current_word, current_node)

def find_opration(current_word, current_node):
    if current_word not empty:
        X = current_word[0]
        if X in current_node.child_node:
            current_word = current_word[1:]
            current_node = child_node
            if current_word not empty:
                return find_opration(current_word, current_node)
            else:
                return current_node.isword
        else:
            return false
    else:
        return true

刪除操作：

def delete(word):
    current_word = word
    current_node = root
    return delete_operation(current_word, current_node)

def delete_operation(current_word, current_node):
    if current_word not empty:
        X = current_word[0]
        if X in current_node.child_node:
            current_word = current_word[1:]
            current_node = child_node
            is_deleted = delete_operation(current_word, current_node)
        else:
            return false
    else:
        if current_node have child_node:
            mark current_node no_word_node
        else:
            delete current_node
        return true

具體實現放在gist上，可以在這里找到。

參考

6天通吃樹結構—— 第五天 Trie樹
從Trie樹（字典樹）談到后綴樹
數據結構之Trie樹

GPU云服務器云服務器字典樹 java字典樹查詢決策樹c語言實現 java實現2-3樹

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/45284.html

大展身手的字典樹

摘要：原文地址在簡單字典樹的實現一文中，我們以單詞輸入自動提示為引子，簡單介紹了字典樹的實現。前綴匹配本文講述前綴匹配的字典樹實現方案。在簡單字典樹的實現一文中，我們已經實現了字典樹的基本操作，這里只需要再加上一個前綴匹配方法即可。原文地址在簡單字典樹(Trie)的實現一文中，我們以單詞輸入自動提示為引子，簡單介紹了字典樹的實現。那么，字典樹到底可以用于哪些場合呢？前綴匹配：給定字典...

Anchorer 2019-07-24 17:36 評論0 收藏0
Trie樹 php 實現敏感詞過濾

摘要：在樹中，每個節點表示一個狀態，每條邊表示一個字符，從根節點到葉子節點經過的邊即表示一個詞條。查找一個詞條最多耗費的時間只受詞條長度影響，因此的查找性能是很高的，跟哈希算法的性能相當。 Last-Modified: 2019年5月10日15:25:35 參考文章 c++ 使用map實現Trie樹關鍵詞過濾擴展，用于檢查一段文本中是否出現敏感詞，基于Double-Array Trie...

王笑朝 2019-07-01 12:46 評論0 收藏0
一種字典樹結構的高效實現

摘要：另一種高效實現下面介紹另一種實現，它將字典樹用數組存儲起來，不僅壓縮了數組，而且不降低查找效率。這就是雙數組字典樹。字典樹的心得體會常見的字典樹實現方法 class Node{ uint node ; uint[] next; }; 或者類似如下結構 class Node{ uint node; map n...

kycool 2019-08-14 17:44 評論0 收藏0
準備下次編程面試前你應該知道的數據結構

摘要：以下內容編譯自他的這篇準備下次編程面試前你應該知道的數據結構瑞典計算機科學家在年寫了一本書，叫作算法數據結構程序。國外 IT 教育學院 Educative.io 創始人 Fahim ul Haq 寫過一篇過萬贊的文章《The top data structures you should know for your next coding interview》,總結了程序員面試中需要掌...

desdik 2019-08-23 14:57 評論0 收藏0
準備下次編程面試前你應該知道的數據結構

摘要：以下內容編譯自他的這篇準備下次編程面試前你應該知道的數據結構瑞典計算機科學家在年寫了一本書，叫作算法數據結構程序。國外 IT 教育學院 Educative.io 創始人 Fahim ul Haq 寫過一篇過萬贊的文章《The top data structures you should know for your next coding interview》,總結了程序員面試中需要掌...

chadLi 2019-08-16 14:48 評論0 收藏0