數據(ju)結構樹應用在哪兒(er)比較多
時間：2018-01-18 來源：未(wei)知
在(zai)數(shu)據(ju)結(jie)構中(zhong)我們會學習到(dao)一種特殊的結(jie)構-----樹。老實(shi)說剛開(kai)始學這段時，感覺(jue)樹的邏輯(ji)太復雜，比之(zhi)鏈表、隊列、棧都(dou)要復雜很多(duo)，但是(shi)慢慢接(jie)觸并且在(zai)自己敲過代碼之(zhi)后，發(fa)現二叉樹其(qi)實(shi)邏輯(ji)和我們日常思維邏輯(ji)一樣(yang)簡單，它的存(cun)儲結(jie)構和雙(shuang)向鏈表的存(cun)儲結(jie)構一樣(yang)。這是(shi)剛開(kai)始接(jie)觸樹的印(yin)象，本文(wen)屬于樹的升級版。
(1)AVL樹(shu): 早的(de)平(ping)衡二(er)叉樹(shu)之一，是根據它的(de)發明(ming)者(zhe)G.M. Adelson-Velsky和E.M. Landis命名的(de)。
它是先(xian)發(fa)明(ming)的自(zi)平衡二(er)叉查找樹(shu)(shu)(shu)，也(ye)被(bei)稱為(wei)(wei)高度(du)平衡樹(shu)(shu)(shu)。相比于"二(er)叉查找樹(shu)(shu)(shu)"，它的特(te)點是：AVL樹(shu)(shu)(shu)中任何節點的兩個子樹(shu)(shu)(shu)的高度(du)大(da)差(cha)別為(wei)(wei)1。
上面(mian)的(de)(de)兩(liang)(liang)張圖(tu)片，左邊(bian)的(de)(de)是(shi)AVL樹，它的(de)(de)任何節(jie)點(dian)的(de)(de)兩(liang)(liang)個子樹的(de)(de)高(gao)(gao)度(du)(du)差(cha)(cha)別(bie)都<=1;而右邊(bian)的(de)(de)不是(shi)AVL樹，因為(wei)7的(de)(de)兩(liang)(liang)顆子樹的(de)(de)高(gao)(gao)度(du)(du)相差(cha)(cha)為(wei)2(以2為(wei)根(gen)節(jie)點(dian)的(de)(de)樹的(de)(de)高(gao)(gao)度(du)(du)是(shi)3，而以8為(wei)根(gen)節(jie)點(dian)的(de)(de)樹的(de)(de)高(gao)(gao)度(du)(du)是(shi)1)。
AVL樹的查找、插入和刪除在平均和壞(huai)情況下都(dou)是O(logn)。
如果在(zai)AVL樹(shu)中插(cha)入或刪除節(jie)點后，使得高度之差大(da)于(yu)1。此時(shi)，AVL樹(shu)的平(ping)衡(heng)狀態就被(bei)破壞，它就不再(zai)是一(yi)棵二叉樹(shu);為了讓它重(zhong)新維(wei)持在(zai)一(yi)個平(ping)衡(heng)狀態，就需要對其(qi)進行(xing)旋轉處理。
主要(yao)應用于windows對進程地址空間的管理。
AVL樹的節點(dian)結構是(shi)：
1. typedef struct _MMADDRESS_NODE {
2. ULONG_PTR StartingVpn; // 起始虛擬地址
3. ULONG_PTR EndingVpn; // 終止虛擬地址
4. struct _MMADDRESS_NODE *Parent;
5. struct _MMADDRESS_NODE *LeftChild;
6. struct _MMADDRESS_NODE *RightChild;
7.} MMADDRESS_NODE, *PMMADDRESS_NODE;
AVL樹的(de)(de)根節點保存在(zai)進程內核對象_EProcess中。_EProcess的(de)(de)結構沒有出現在(zai)文檔中，但是我(wo)們可以通過windbg獲(huo)取(qu)。在(zai)Windows 2003中，用windbg獲(huo)取(qu)如下(xia)輸出：
1. kd> dt _EProcess
2. nt!_EPROCESS
3. +0x000 Pcb : _KPROCESS
4. +0x078 ProcessLock : _EX_PUSH_LOCK
5. +0x080 CreateTime : _LARGE_INTEGER
6. +0x088 ExitTime : _LARGE_INTEGER
7. ……
8. +0x24c PriorityClass : UChar
9. +0x250 VadRoot : _MM_AVL_TABLE
10. +0x270 Cookie : Uint4B
上圖中偏移量(liang)為0x250處的(de)(de)VadRoot字段保存了(le)AVL輸根(gen)節(jie)點(dian)所在的(de)(de)地(di)址(zhi)。因此，在驅動(dong)程序中，通過(guo)以(yi)下代(dai)碼可以(yi)獲取當前(qian)進程的(de)(de)AVL樹的(de)(de)根(gen)節(jie)點(dian)地(di)址(zhi)。
1. PMMADDRESS_NODE ZsaGetVmRoot(){
2. char * pEProcess = (char*)PsGetCurrentProcess();
3. char * avlRoot = pEProcess + 0x250;
4. char * p_MM_AVL_TABLE = avlRoot;
5. return (PMMADDRESS_NODE) p_MM_AVL_TABLE;
6. }
既然獲(huo)得(de)了根(gen)地(di)址，則可以對二叉樹(shu)進(jin)(jin)行遍歷，打印出(chu)整個(ge)數據結構。以下是(shi)(shi)某個(ge)測試(shi)進(jin)(jin)程在進(jin)(jin)行了1024*1024次new分(fen)配后(hou)，AVL樹(shu)的內容。可以看到，樹(shu)基本是(shi)(shi)平衡的。
0,0(2)字典(dian)樹，又稱為單詞查找(zhao)樹，Tire數，是一種樹形結構，它是一種哈希樹的變種。
它是不同字符串的(de)相(xiang)同前綴只(zhi)保存一份(fen)。
相對(dui)直接保存(cun)(cun)字符串肯定是節(jie)省空間(jian)的(de)，但(dan)是它(ta)保存(cun)(cun)大量字符串時會(hui)很耗費內(nei)存(cun)(cun)(是內(nei)存(cun)(cun))。
類似的有：前綴樹(prefix tree)，后綴樹(suffix tree)，radix tree(patricia tree, compactprefix tree)，crit-bit tree(解(jie)決耗(hao)費內存問(wen)題)，以及前面說的double array trie。
前(qian)綴(zhui)樹：字符串快速檢索，字符串排序，長公共前(qian)綴(zhui)，自動匹配前(qian)綴(zhui)顯示后綴(zhui)。
后綴樹：查找(zhao)字(zi)(zi)符串s1在s2中(zhong)，字(zi)(zi)符串s1在s2中(zhong)出(chu)現(xian)的次數，字(zi)(zi)符串s1,s2長公共部分，長回文串。
trie 樹的一個典型應用是(shi)前(qian)綴匹配(pei)，比(bi)如下(xia)面這個很(hen)常見的場景(jing)，在我(wo)們(men)輸(shu)入時，搜(sou)索引擎(qing)會(hui)給予提(ti)示。
