在計算機科學中，后綴樹（也稱為 PAT 樹或更早的形式，位置樹）是一種壓縮的特里樹，包含給定文本的所有后綴作為它們的鍵和文本中的位置作為它們的值。 后縮樹允許特別快速地實現許多重要的字符串操作。

為字符串 S {\displaystyle S} 構建這樣一棵樹需要時間和空間與 S {\displaystyle S} 的長度成線性關系。 一旦構造完成，可以快速執行多個操作，例如在 S {\displaystyle S} 中定位子串，如果允許一定數量的錯誤則定位子串，定位匹配正則表達式模式等。后縮樹還提供 最長公共子串問題的xxx個線性時間解決方案之一。 這些加速是有代價的：存儲字符串的后綴樹通常比存儲字符串本身需要更多的空間。

該概念最早由 Weiner (1973) 提出。而不是后綴 S [ i 。 . n ] {\displaystyle S[i..n]} ，維納在他的樹中存儲了每個位置的前綴標識符，即從 i {\displaystyle i} 開始并且在 S { displaystyle S} 。 他的算法 D 采用 S [ k + 1.. n ] {\displaystyle S[k+1..n]} 的未壓縮特里樹并將其擴展為 S [ k 的特里樹。 . n ] {\displaystyle S[k..n]} 。 這樣，從 S [ n 的平凡特里樹開始。 . n ] {\displaystyle S[n..n]} ， S [ 1.. n ] {\displaystyle S[1..n]} 的特里樹可以由 n ? 1 {\displaystyle n- 1}連續調用算法D； 然而，整體運行時間為 O ( n 2 ) {\displaystyle O(n{2})} 。 Weiner 的算法 B 維護了幾個輔助數據結構，以實現與構建的 trie 大小成線性關系的整體運行時間。 后者仍然可以是 O ( n 2 ) {\displaystyle O(n{2})} 個節點，例如 對于 S = a n b n a n b n $ 。 {\displaystyle S=a{n}b{n}a{n}b{n}\$.} Weiner's Algorithm C 最終使用壓縮嘗試來實現線性整體存儲大小和運行時間。Donald Knuth 隨后 后者被評為 1973 年年度算法。教科書 Aho, Hopcroft & Ullman (1974, Sect.9.5) 以簡化和更優雅的形式再現了 Weiner 的結果，引入了術語位置樹。

McCreight (1976) 是xxx個為 S {\displaystyle S} 的所有后綴構建（壓縮）特里樹的人。 雖然以 i {\displaystyle i} 開始的后綴通常比前綴標識符長，但它們在壓縮的 trie 中的路徑表示在大小上沒有差異。 另一方面，McCreight 可以免除 Weiner 的大部分輔助數據結構； 僅保留后綴鏈接。

Ukkonen (1995) 進一步簡化了結構。 他提供了xxx個后綴樹的在線構造，現在稱為 Ukkonen 算法，其運行時間與當時最快的算法相匹配。這些算法對于恒定大小的字母表都是線性時間的，并且具有最壞情況的運行 通常 O ( n log ? n ) {\displaystyle O(n\log n)} 的時間。

Farach (1997) 給出了xxx個對所有字母都最優的后綴樹構造算法。 特別是，這是xxx個線性時間算法，用于從多項式范圍內的整數字母表中提取的字符串。 Farach 的算法已成為構建后綴樹和后綴數組的新算法的基礎，例如，在外部存儲器、壓縮、簡潔等中。

長度為 n {\displaystyle n} 的字符串 S {\displaystyle S} 的后綴樹被定義為這樣一棵樹：

• 這棵樹正好有 n 片葉子，編號從 1 {\displaystyle 1} 到 n {\displaystyle n} 。
• 除根節點外，每個內部節點至少有兩個子節點。
• 每條邊都標有 S {\displaystyle S} 的非空子串。
• 從一個節點開始的兩條邊不能有以相同字符開頭的字符串標簽。
• 通過連接從根到葉 i {\displaystyle i} 路徑上找到的所有字符串標簽獲得的字符串拼出后綴 S [ i 。 . n ] {\displaystyle S[i..n]} ，因為 i {\displaystyle i} 從 1 {\displaystyle 1} 到 n {\displaystyle n} 。

由于并非所有字符串都存在這樣的樹，因此 S {\displaystyle S} 被填充了一個在字符串中看不到的終端符號（通常表示為 $）。 這確保沒有后綴是另一個后綴的前綴，并且將有 n {\displaystyle n} 個葉節點，一個對應于 S {\displaystyle S} 的 n {\displaystyle n} 個后綴中的每一個。 由于所有內部非根節點都是分支的，因此最多可以有 n ? 1 個這樣的節點，并且總共有 n + (n ? 1) + 1 = 2n 個節點（n 個葉子，n - 1 個內部非根節點，1 根）。

后綴鏈接是較舊的線性時間構建算法的關鍵特征，盡管大多數基于 Farach 算法的較新算法都省去了后綴鏈接。