一條成功路徑證明甚麼?
Trie 節點代表由根沿路徑讀出的前綴。到達節點只證明路徑存在,並不證明該前綴本身是已儲存鍵值;另一個終止標記才回答第二個問題。例如在字典 a, an, ant, ante, bat, bath, bats 中,ba 是多個鍵值的開頭,所以路徑存在,但 ba 本身沒有儲存。
前一節介紹了表示法與刪除;這裏逐步追蹤查找和補全,讓每個中間狀態的意思清楚可見。
定義 7.2.1
(精確查找與前綴補全)
設 為已儲存鍵值的集合, 為查詢字串。精確查找問的是 是否成立。前綴補全問的是所有以 為前綴的鍵值 ,即對某個字串 (可以為空)有 。因此與 相等的鍵值也是 的補全。
讀取時保持不變量
若查詢 的前 條邊均存在,消耗 個字元後,當前節點恰好代表 。起初 ,當前節點是根;若下一條邊存在,走過它便同時令路徑及已消耗前綴增加一個字元。若邊不存在,就沒有已儲存鍵值可以整個查詢為前綴:任何以完整查詢開頭的鍵值都需要這條缺失的邊。
精確查找消耗所有字元後,還要檢查終止標記。ba 的兩條邊存在,但標記為假,所以答案是「不是鍵值」。an 即使有後代,標記仍為真。節點可以同時是一個完整字詞及較長字詞的開頭。
前綴補全先找到查詢節點;若存在,就枚舉其子樹中的終止節點,當該節點本身終止時也要包括它。ba 的補全是 bat、bath、bats。每個輸出鍵值的路徑都經過查詢節點,因此具有所求前綴;每個具有該前綴的已儲存鍵值也必在其下方的終止節點結束,所以完整遍歷會找到它。
概念視角算法
補全是排序鍵值中的一段
把鍵值按字典序排列,則以 為前綴的鍵值恰好組成連續的一段;若這一段非空,它由第一個不小於 的鍵值開始。先用二分搜尋找出這個鍵值,再在前綴仍然匹配時向後掃描,所得的補全與 trie 相同。對上面詞典中的 ba,搜尋落在第五個鍵值 bat,掃描輸出 bat、bath、bats;對 bad,搜尋落在 bat,它沒有這個前綴,所以這一段為空。
定理 7.2.2
(Trie 查找與補全的正確性)
設某個 trie 以標準形式表示已儲存鍵值的集合 ,意思是它的非根節點恰好是已儲存鍵值的非空前綴,而且節點為終止,當且僅當其字串已儲存。設 為查詢字串。若搜尋 時遇到缺失的邊,則 中沒有以 為前綴的鍵值。否則搜尋終止於 的節點,精確查找回答「是」,當且僅當該節點為終止,亦即當且僅當 。前綴補全恰好輸出 中以 為前綴的鍵值,每個一次。
證明
(從兩個方向讀取路徑)
設搜尋遇到缺失的邊。反設某個已儲存鍵值以完整查詢開頭,它的路徑便必須包含查詢的每條邊,包括搜尋報告為缺失的邊,矛盾。這證明沒有補全,特別是 。
若沒有缺失的邊,不變量說明搜尋終止於代表 的節點。在標準 trie 中,該節點為終止,當且僅當 是成員,所以終止標記決定精確查找的結果。
對於補全,每個輸出的鍵值都是查詢節點子樹中某個終止節點的字串,所以它的路徑經過該節點,並以 為前綴。反過來,以 為前綴的已儲存鍵值,其路徑經過查詢節點,並在其下方的終止節點或節點本身結束,所以完整遍歷子樹會到達並輸出它。每個節點只被訪問一次,所以每個鍵值只輸出一次。
證明透視
為何缺失的邊就能決定整個查詢
這個論證在同一個結構上朝兩個方向進行。已儲存鍵值必有完整路徑,因為插入會建立鍵值的每條邊。這使缺失的邊具有決定性:證明取一個假設以查詢開頭的鍵值並讀出它的路徑,而不是搜遍所有鍵值。反過來,終止標記恰好為已儲存鍵值而設,所以路徑成功之後,由標記決定成員關係。
兩項事實都來自標準形式。若先前的剪枝移除了某個已儲存鍵值仍需要的邊,缺失邊的結論便不再成立。路徑成功走完的結論與缺失邊不同:它建立了前綴,之後決定成員關係的是標記,而不是路徑。
反例模式
到達節點並不證明鍵值已儲存
一條誘人的規則是:若搜尋消耗了 的每個字元而沒有遇到缺失的邊,則 已儲存。在字典 a, an, ant, ante, bat, bath, bats 中,查詢 ba 消耗兩個字元並到達節點 ba,但 ba 不在七個鍵值之中,其終止標記為假。規則失敗,是因為該節點只是 bat、bath、bats 的前綴。補救辦法是在路徑成功後檢查終止標記。
反過來的直覺也不成立:有後代的節點並不因此不是鍵值。節點 an 有後代 ant 與 ante,其標記為真,所以 an 已儲存。
例題 7.2.3
(三次精確查找)
取字典 a, an, ant, ante, bat, bath, bats。根以下的節點是 a、an、ant、ante、b、ba、bat、bath、bats,其中終止的是 a、an、ant、ante、bat、bath、bats。
查找 ba:邊 b 與 a 都存在,標記為假,所以 ba 不是鍵值。查找 an:邊都存在,標記為真,所以 an 是鍵值,雖然該節點有子節點。查找 bad:搜尋到達 ba,但沒有邊 d,所以 bad 不是鍵值,而且缺失的邊也說明沒有鍵值以 bad 開頭。
例題 7.2.4
(兩次前綴補全)
對查詢 ba,查詢節點不是終止,所以不為它輸出任何東西。其子樹有子節點 bat,它是終止,最先輸出;在 bat 之下,按字母次序訪問子節點 h 與 s,先後輸出 bath、bats。補全是 bat、bath、bats。
對查詢 an,查詢節點是終止,最先輸出。接著其子節點 ant 是終止,其下的 ante 也是終止。補全是 an、ant、ante。鍵值 a 不是 an 的補全,因為 a 並不以 an 為前綴。
例題 7.2.5
(邊界情況:空查詢與越過葉節點的查詢)
空查詢不消耗任何邊,停在根。這個字典不含空字串,所以根不是終止,精確查找回答「否」。作為前綴,空字串匹配每個鍵值,所以補全輸出全部七個鍵值,次序為 a、an、ant、ante、bat、bath、bats。
再看查詢 batss。字元 b、a、t、s 沿現有的邊走,到達節點 bats。該節點沒有子節點 s,所以搜尋遇到缺失的邊:batss 不是鍵值,也沒有補全。
說清楚計算甚麼工作
命題 7.2.6
(查找與補全的成本)
假設每次子節點查找為常數時間,並且可以按每個現有子節點常數成本枚舉一個節點的子節點。對長度為 的查詢,精確查找至多用 次子節點查找,時間為 。若查詢節點存在,其子樹有 個節點,而輸出的鍵值共有 個字元,補全需時 。
證明
(先沿查詢前進,再訪問子樹)
搜尋每次子節點查找消耗一個查詢字元,在第一條缺失的邊或消耗 個字元後停止,所以至多作 次查找,再讀取一個標記。補全接著以常數成本訪問子樹的 個節點各一次,每個現有子節點再花常數成本;含 個節點的子樹有 條邊,所以合共 。寫出輸出的鍵值花費 。
常見錯誤
(把整個補全稱為 )
沿查詢前進是 ,但補全接著可能遍歷大片子樹並輸出許多字串。上述字典中查詢 a 的長度是 1,卻輸出四個鍵值,所以成本不只取決於 。沒有額外限制就把整個枚舉稱為 會造成誤解。
常見錯誤
(以為空查詢的兩個答案必須一致)
空查詢不消耗邊,搜尋停在根。精確查找為真恰好當根有終止標記,即曾儲存空字串。作為前綴,空字串匹配每個已儲存鍵值。這兩個答案不必相同,上述字典便是例子:查找回答「否」,補全卻列出七個鍵值。
自我檢查
快速檢查
(查找 bad 到達 ba 後發現缺少 d 邊,badger 能否已儲存?)
想一想 badger 需要的路徑。
解答 · 答案
不能;它的路徑會需要缺失的 d 邊。
快速檢查
(在任意字典中,若 an 終止且有子節點,ant 一定已儲存嗎?)
有子節點,是否就知道子節點是哪個字母?
解答 · 答案
不。單有子節點不能證明完整 ant 路徑存在,也不能證明終點有終止標記。例如若 an 唯一的子節點是 g,字典可能含有 ang 而沒有 ant。
快速檢查
(在字典 a, an, ant, ante, bat, bath, bats 中,ante 的補全是甚麼?)
查詢節點是否終止?它有沒有子樹?
解答 · 答案
只有 ante 本身。查詢節點是終止,所以它被輸出;它沒有子節點,所以不再輸出其他東西。