數據結構樹應用在哪兒比較多
時間：2018-01-18 來源：未知
在數據結構中我們會學習到一種特殊的結構-----樹。老實說剛開始學這段時，感覺樹的邏輯太復雜，比之鏈表、隊列、棧都要復雜很多，但是慢慢接觸并且在自己敲過代碼之后，發現二叉樹其實邏輯和我們日常思維邏輯一樣簡單，它的存儲結構和雙向鏈表的存儲結構一樣。這是剛開始接觸樹的印象，本文屬于樹的升級版。
(1)AVL樹: 早的平衡二叉樹之一，是根據它的發明者G.M. Adelson-Velsky和E.M. Landis命名的。
它是先發明的自平衡二叉查找樹，也被稱為高度平衡樹。相比于"二叉查找樹"，它的特點是：AVL樹中任何節點的兩個子樹的高度大差別為1。
上面的兩張圖片，左邊的是AVL樹，它的任何節點的兩個子樹的高度差別都<=1;而右邊的不是AVL樹，因為7的兩顆子樹的高度相差為2(以2為根節點的樹的高度是3，而以8為根節點的樹的高度是1)。
AVL樹的查找、插入和刪除在平均和壞情況下都是O(logn)。
如果在AVL樹中插入或刪除節點后，使得高度之差大于1。此時，AVL樹的平衡狀態就被破壞，它就不再是一棵二叉樹;為了讓它重新維持在一個平衡狀態，就需要對其進行旋轉處理。
主要應用于windows對進程地址空間的管理。
AVL樹的節點結構是：
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樹的根節點保存在進程內核對象_EProcess中。_EProcess的結構沒有出現在文檔中，但是我們可以通過windbg獲取。在Windows 2003中，用windbg獲取如下輸出：
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
上圖中偏移量為0x250處的VadRoot字段保存了AVL輸根節點所在的地址。因此，在驅動程序中，通過以下代碼可以獲取當前進程的AVL樹的根節點地址。
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. }
既然獲得了根地址，則可以對二叉樹進行遍歷，打印出整個數據結構。以下是某個測試進程在進行了1024*1024次new分配后，AVL樹的內容。可以看到，樹基本是平衡的。
0,0(2)字典樹，又稱為單詞查找樹，Tire數，是一種樹形結構，它是一種哈希樹的變種。
它是不同字符串的相同前綴只保存一份。
相對直接保存字符串肯定是節省空間的，但是它保存大量字符串時會很耗費內存(是內存)。
類似的有：前綴樹(prefix tree)，后綴樹(suffix tree)，radix tree(patricia tree, compactprefix tree)，crit-bit tree(解決耗費內存問題)，以及前面說的double array trie。
前綴樹：字符串快速檢索，字符串排序，長公共前綴，自動匹配前綴顯示后綴。
后綴樹：查找字符串s1在s2中，字符串s1在s2中出現的次數，字符串s1,s2長公共部分，長回文串。
trie 樹的一個典型應用是前綴匹配，比如下面這個很常見的場景，在我們輸入時，搜索引擎會給予提示。
