當前位置:成語大全網 - 新華字典 - 三叉樹的性質特點

三叉樹的性質特點

對於壹般的Trie樹的數據結構,它的實現簡單但是空間效率極低。例如,如果要支持26個英文字母,每個節點就要保存26個指針,當數據量繼續增大,需要更多的支持內存用量,使得整個數據結構占用內存太多。

由於節點數組中保存掛起的空指針占用了過多內存,我們采用特殊的Trie樹的數據結構——Ternary Search Trie,三叉搜索樹,它是結合字典樹的高時間效率和二叉搜索樹的高空間效率的壹種數據結構。

三叉搜索樹與二叉搜索樹不同,鍵不是直接保存在節點中,而是由節點在樹中的位置決定。壹個節點的所有子孫都有相同的前綴(prefix),也就是這個節點對應的字符串,而根節點對應空字符串。壹般情況下,不是所有的節點都有對應的值,只有葉子節點和部分內部節點所對應的鍵才有相關的值。

與此同時,三叉搜索樹使用了壹種聰明的手段去解決字典樹的內存問題(空的指針數組)。為了避免多余的指針占用內存,每個節點不再用數組來表示,而是表示成“樹中有樹”。節點裏每個非空指針都會在三叉搜索樹裏得到屬於它自己的節點。

插入字符串的順序會影響三叉搜索樹的結構,為了取得最佳性能,字符串應該以隨機的順序插入到三叉樹搜索樹中,尤其不應該按字母順序插入,否則對應於單個Trie節點的子樹會退化成鏈表,極大地增加查找成本。單詞的讀入順序對於創建平衡的三叉搜索樹很重要,但對於二叉搜索樹就不太重要。通過選擇壹個排序後數據單元集合的中間值,並把它作為開始節點。

三叉搜索樹的基本性質可以歸納為:

(1)根節點不包含字符,除根節點外的每個節點只包含壹個字符。

(2)從根節點到某壹個節點,路徑上經過的字符連接起來,為該節點對應的字符串。

(3)每個節點的所有子節點包含的字符串不相同。

(4)節點采用“樹中有樹”的建立方法,避免多余的內存占用。