国内精品麻豆美女在线播放视频,国产免费永久在线观看,亚洲国产高清aⅴ视频

隨筆分類

隨筆檔案

統計

隨筆 - 79
文章 - 0
評論 - 15
引用 - 0

留言簿(1)

閱讀排行榜

評論排行榜

Trie Tree

#Trie Tree的基本特點
1）根節點不包含字符，除根節點外每個節點只包含一個字符
2）從根節點到某一個節點，路徑上經過的字符連接起來，為該節點對應的字符串
3）每個節點的所有子節點包含的字符串不相同

原理圖：

參考：
數據結構之Trie樹
 Trie Tree on Answers.com

#Trie Tree簡單的Python實現
最近在學習Python，下面的代碼就用來學習下語法了：）

#coding:utf-8

'''

Created on 2011-6-14

@author: Dokie

'''

ALPHABET_SIZE = 26

class Node:

def __init__(self, is_end = False):

self.is_end = is_end

self.prefix_count = 0

self.children = [None for child in range(ALPHABET_SIZE)]

class Trie:

def __init__(self):

self.head = Node()

def insert(self, word):

current = self.head

count = 0

for letter in word:

int_value = ord(letter) - ord('a')

try:

assert ( 0 <= int_value <= 26)

except Exception:

raise Exception("invalid Word")

if current.children[int_value] is None:

current.children[int_value] = Node()

current = current.children[int_value]

count += 1

current.prefix_count = count

current.is_end = True

def search(self, word):

current = self.head

for letter in word:

int_value = ord(letter) - ord('a')

try:

assert (0 <= int_value <= 26)

except Exception:

return False

if current.children[int_value] is None:

return False

else:

current = current.children[int_value]

return current.is_end

def count_words_with_prefix(self, word):

current = self.head

for letter in word:

int_value = ord(letter) - ord('a')

try:

assert (0 <= int_value <= 26)

except Exception:

return None

if current.children[int_value] is None:

return None

else:

current = current.children[int_value]

return current.prefix_count

if __name__ == '__main__':

import doctest

doctest.testmod()

t = Trie()

t.insert("apple")

t.insert("good")

print t.search("apple")

print t.search("fff")

print t.count_words_with_prefix("apple")

附：TrieMap Javap實現

posted on 2011-06-14 16:57 XXXXXX 閱讀(1091) 評論(0) 編輯收藏所屬分類: Algorithm

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關文章: Trie Tree Bloom Filter 【編程珠現】-算法設計技術【編程珠璣】-啊哈！算法【編程珠璣】-開篇 K-Menas算法打印全排列

導航

隨筆分類

隨筆檔案

統計

留言簿(1)

DB

Others

QA

Tech Website

閱讀排行榜

評論排行榜

Trie Tree