文章目錄

• 簡介
• Trie的特性
• Trie樹和Hashing,BST的對比
• Trie樹的程序化表示
• Trie樹的插入
• Trie樹的搜索
• Trie樹的刪除
• Trie樹的疑惑

簡介

字典樹的英文名叫做Trie,取自retrieval，也就是檢索的意思。它是一種特殊的樹狀結構，可以進行快速的字符插入和字符串搜索，特別適用于文本搜索和詞頻統(tǒng)計等應用方面。

本文將會詳細介紹字典樹Trie的特性。

Trie的特性

我們知道字典樹是一棵樹，為什么叫字典樹呢？因為Trie的搜索和存儲結構和字典非常類似。我們回憶一下十幾年前我們使用新華字典查某個漢字的情況。

在新華字典中，所有的漢字都是以拼音來排序的。假如我們需要查詢一個漢字，應該怎么查詢呢？

首先我們需要將漢字轉換為拼音，然后按照拼音順序，一個字母一個字母的去查找。比如我們要查“全”這個字，它的拼音是“quan”。我們先找到Q的目錄，然后在Q的目錄里面再找u，再找a和n，最終就找到我們要找的漢字了。

我們來探討一下字典樹的結構。為了方便起見，我們假設字典是英文字典，Quan的結構存儲結構應該是什么樣

總結

以上是生活随笔為你收集整理的快乐学算法之:字典树Trie的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。