- R向單詞查找樹
- 資料結構
- 查找
- 插入
- 查找所有鍵
- 通配符匹配
- 最長前綴
- 洗掉
- R向單詞查找樹的性質
- 三向單詞查找樹
- 三向單詞查找樹的性質
同字串的排序一樣，利用字串的性質開發的查找演算法也比通用的演算法更有效，這些演算法可以用于在以字串作為被查找鍵的場合，這類演算法在面對巨量的資料時，仍然可以取得這樣的性能：查找命中所需的時間與被查找的鍵的長度成正比；而查找未命中時只需檢查若干個字符，這樣的性能是相當驚人的，也是演算法研究的最高成就之一，這些演算法成了建成現在能夠便捷、快速地訪問海量資訊所依賴的基礎設施的重要因素，
R向單詞查找樹
資料結構
單詞查找樹(Trie)是用于字串鍵查找的資料結構，與之前的查找樹類似，它也是由鏈接的結點所組成的資料結構，這些鏈接可能為空，也可能指向其他結點，
結點的資料結構為：
private static class Node {
private Object val;
private Node[] next = new Node[R];
}
每個節點都只有一個或0個指向它的結點（父結點），只有根結點不會有父結點，每個節點都含有R條鏈接，R為字母表的大小，如果字符都由26個小寫英文字母構成，則R為26；如果字符屬于ASCII字符集，則R=128；DNA研究中用4個字母表示4個堿基，R=4，
R條鏈接對應可能出現的字符，這其中會有大量的空鏈接，鍵是由從根節點到含有非空值的結點的路徑所隱式表示的，每個結點也含有一個相應的值，可以是空也可以是符號表中的某個鍵所關聯的值，值為空的結點在符號表中沒有對應的鍵，它們的存在是為了簡化單詞查找樹中的查找操作，每個鍵所關聯的值保存在給定鍵的最后一個字母所對應的結點中，
也將基于含有R個字符的字母表的單詞查找樹稱為R向單詞查找樹，
查找
在單詞查找樹中查找給定字串鍵所對應的值時，是以被查找的鍵中的字符為導向的，單詞查找樹中的每個結點都包含了下一個可能出現的所有字符的鏈接，從根結點開始，首先經過的是鍵的首字母所對應的鏈接，在下一個結點沿著第二個字符所對應的鏈接繼續前進，以此類推，直到找到鍵的最后一個字母所指向的結點，或者遇到了一條空鏈接，
- 如果鍵的尾字符所對應的結點中的值非空，則查找命中，鍵所對應的值就是鍵的尾字符中所存盤的值；
- 如果鍵的尾字符所對應的結點中的值為空，或者查找的程序中遇到了空鏈接，則查找未命中，
public Value get(String key) {
Node x = get(root, key, 0);
if (x == null)
return null;
return (Value) x.val;
}
private Node get(Node x, String key, int d) {
if (x == null)
return null;
if (d == key.length())
return x;
char c = key.charAt(d);
return get(x.next[c], key, d + 1);
}
插入
插入的時候，也需要先進行一次查找
- 如果在到達鍵的尾字符之前就遇到了一個空鏈接，這種情況下單詞查找樹中不存在與鍵的尾字符對應的結點，因此需要為鍵中還未被檢查的每個字符創建一個對應的結點，并將鍵的值保存到最后一個字符的結點中；
- 如果在遇到空鏈接之前就到達了鍵的尾字符，則將該結點的值設為鍵所對應的值，
public void put(String key, Value val) {
root = put(root, key, val, 0);
}
public Node put(Node x, String key, Value val, int d) {
if (x == null)
x = new Node();
if (d == key.length()) {
x.val = val;
return x;
}
char c = key.charAt(d);
x.next[c] = put(x.next[c], key, val, d + 1);
return x;
}
查找所有鍵
單詞查找樹中的字符是被隱式地表示的，查找的時候需要顯式地將它們表示出來，并加入到佇列中，查找基于一個叫做collect的方法，它的引數中包含了一個字串，用來保存從根結點出發的路徑上的一系列字符，每當在collect()呼叫中訪問一個結點時，方法的第一個引數就是這個結點，第二個引數是從根節點到這個結點的路徑上的所有字符，如果結點的值非空，就將和它相關聯的字串加入佇列中，然后遞回地訪問它的鏈接陣列所指向的所有可能的字符結點，在每次呼叫collect之前，都將鏈接對應的字符附加到當前鍵的末尾作為引數，要實作keys()方法，可以用空字符作為引數呼叫keysWithPrefix()方法，要實作keysWithPrefix(),則可以先呼叫get()方法找出給定前綴所對應的單詞查找子樹，再使用collect()，
public Iterable<String> keys() {
return keysWithPrefix("");
}
public Iterable<String> keysWithPrefix(String pre) {
Queue<String> q = new Queue<String>();
collect(get(root, pre, 0), pre, q);
return q;
}
private void collect(Node x, String pre, Queue<String> q) {
if (x == null)
return;
if (x.val != null)
q.enqueue(pre);
for (char c = 0; c < R; c++) {
collect(x.next[c], pre + c, q);
}
}
通配符匹配
通配符匹配的程序類似keysWithPrefix，但需要為collect添加一個用于指定匹配模式的引數，模式中用'.'來表示通配符，如果模式中含有通配符，就需要用遞回呼叫處理所有的鏈接，否則就只需要處理模式中指定字符的鏈接即可，
public Iterable<String> keysThatMatch(String pat) {
Queue<String> q = new Queue<String>();
collect(root, "", pat, q);
return q;
}
private void collect(Node x, String pre, String pat, Queue<String> q) {
int d = pre.length();
if (x == null)
return;
if (d == pat.length() && x.val != null)
q.enqueue(pre);
if (d == pat.length())
return;
char next = pat.charAt(d);
for (char c = 0; c < R; c++) {
if (next == '.' || next == c)
collect(x.next[c], pre + c, pat, q);
}
}
最長前綴
longestPrefixOf方法會找出與給定字串匹配的最長前綴，比如對于鍵by,she, shells，longestPrefixOf("shell")的結果為she，要找到最長前綴，需要一個類似于get的遞回方法來記錄查找路徑上所找到的最長鍵的長度，并在遇到值非空的結點時更新它，然后在被查找的字串結束或者遇到空鏈接時終止查找，
public String longestPrefixOf(String s) {
int length = search(root, s, 0, 0);
return s.substring(0, length);
}
public int search(Node x, String s, int d, int length) {
if (x == null)
return length;
if (x.val != null)
length = d;
if (d == s.length())
return length;
char c = s.charAt(d);
return search(x.next[c], s, d + 1, length);
}
洗掉
要從單詞查找樹中洗掉一個鍵值對，首先需要找到鍵所對應的結點并將它的值設為空，然后分兩種情況：
- 如果這個結點還含有一個指向某個子結點的非空鏈接，就不需要在進行別的操作；
- 如果這個結點的所有鏈接都為空，那馬就需要從樹中洗掉這個結點；如果洗掉這個結點后，使得它的父結點的所有鏈接也都成了空，就要繼續洗掉它的父結點，依次類推，
public void delete(String key) {
root = delete(root, key, 0);
}
private Node delete(Node x, String key, int d) {
if (x == null)
return null;
if (d == key.length())
x.val = null;
else {
char c = key.charAt(d);
x.next[c] = delete(x.next[c], key, d + 1);
}
if (x.val != null)
return x;
for (char c = 0; c < R; c++)
if (x.next[c] != null)
return x;
return null;
}
R向單詞查找樹的性質
單詞查找樹的鏈接結構和鍵的插入或洗掉順序無關，對于任意給定的一組鍵，它們的單詞查找樹都是唯一的，這與之前所有的其它查找樹都不相同，
在單詞查找樹中查找或插入一個鍵時，訪問陣列的次數最多為鍵的長度加1，因為get()和put()都使用了一個指示字符位置的引數d，它的初始值為0，每次遞回都會加1，當長度等于鍵的長度時遞回停止，此時訪問了陣列d+1，如果查找未命中，訪問次數會更少，這說明在單詞查找樹中查找一個鍵所需的時間與樹的大小無關，只與鍵的長度有關，
關于單詞查找樹占用的空間，與樹中的鏈接總數有關，設w為鍵的平均長度，R為字符集的大小，N為鍵的總數，則一顆單詞查找樹中的鏈接總數在RN到RNw之間，
- 如果每個鍵的首字母都不相同，那么每個鍵中的每個字母都有一個結點，一個鍵含有Rw個鏈接，共N個鍵，含有RNw個鏈接；
- 如果鍵的首字母都相同，且都處于一個分支，那么樹將只含有這一條分支，共RN個鏈接，
有一些經驗性的規律：當所有鍵都較短時，鏈接的總數接近于RN;而當所有鍵都較長時，鏈接的總數接近于RNw，所以縮小R或w能夠節省大量的空間，而且在實際應用中，使用單詞查找樹之前，首先了解將要插入的所有鍵的性質是非常重要的，
三向單詞查找樹
R向單詞查找樹雖然檢索速度很快，但空間占用也非常大，尤其是對于比較大的字符集和比較長的鍵，這將消耗非常大的空間，三向單詞查找樹可避免這個問題，
在三向單詞查找樹中，每個節點都含有一個字符，三條鏈接和一個值，這三條鏈接分別對應著當前字母小于、等于、大于節點字母的所有鍵，只有沿著中間鏈接前進時才會找到待查找的鍵，
在三向單詞查找樹中查找鍵時，首先將鍵的首字母和根結點進行比較，如果首字母較小，就選擇左鏈接，如果首字母較大，就選擇右鏈接，首字母與根節點字符相等，就選擇中鏈接，然后遞回查找，直到遇到一個空鏈接或者當鍵結束時結點的值為空，則查找未命中；如果在鍵結束時結點的值非空，則查找命中，
public class TST<Value> {
private Node root;
private class Node {
char c;
Node left, mid, right;
Value val;
}
public Value get(String key) {
Node node = get(root, key, 0);
if (node == null)
return null;
return node.val;
}
private Node get(Node x, String key, int d) {
if (x == null)
return null;
char c = key.charAt(d);
if (c < x.c)
return get(x.left, key, d);
else if (c > x.c)
return get(x.right, key, d);
else if (d < key.length() - 1)
return get(x.mid, key, d);
else
return x;
}
public void put(String key, Value val) {
root = put(root, key, val, 0);
}
private Node put(Node x, String key, Value val, int d) {
char c = key.charAt(d);
if (c < x.c)
x.left = put(x.left, key, val, d);
else if (c > x.c)
x.right = put(x.right, key, val, d);
else if (d < key.length() - 1)
x.mid = put(x.mid, key, val, d);
else
return x.val = val;
return x;
}
}
三向單詞查找樹的性質
三向單詞查找樹可以看作是R向單詞查找樹的緊湊表示，但三向單詞查找樹的形狀是與鍵的插入順序有關的，而且空間占用要比R向單詞查找樹小很多，
三向單詞查找樹的每個結點只含有3個鏈接，樹的鏈接總數在3N到3Nw之間，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/102318.html
標籤：其他
上一篇：PAT乙級1020