色yeye在线视频观看_亚洲人亚洲精品成人网站_一级毛片免费播放_91精品一区二区中文字幕_一区二区三区日本视频_成人性生交大免费看

在數(shù)據(jù)結(jié)構(gòu)中我們會(huì)學(xué)習(xí)到一種特殊的結(jié)構(gòu)-----樹。老實(shí)說(shuō)剛開始學(xué)這段時(shí)，感覺(jué)樹的邏輯太復(fù)雜，比之鏈表、隊(duì)列、棧都要復(fù)雜很多，但是慢慢接觸并且在自己敲過(guò)代碼之后，發(fā)現(xiàn)二叉樹其實(shí)邏輯和我們?nèi)粘Ｋ季S邏輯一樣簡(jiǎn)單，它的存儲(chǔ)結(jié)構(gòu)和雙向鏈表的存儲(chǔ)結(jié)構(gòu)一樣。這是剛開始接觸樹的印象，本文屬于樹的升級(jí)版。

(1)AVL樹: 早的平衡二叉樹之一，是根據(jù)它的發(fā)明者G.M. Adelson-Velsky和E.M. Landis命名的。

它是先發(fā)明的自平衡二叉查找樹，也被稱為高度平衡樹。相比于"二叉查找樹"，它的特點(diǎn)是：AVL樹中任何節(jié)點(diǎn)的兩個(gè)子樹的高度大差別為1。

上面的兩張圖片，左邊的是AVL樹，它的任何節(jié)點(diǎn)的兩個(gè)子樹的高度差別都<=1;而右邊的不是AVL樹，因?yàn)?的兩顆子樹的高度相差為2(以2為根節(jié)點(diǎn)的樹的高度是3，而以8為根節(jié)點(diǎn)的樹的高度是1)。

AVL樹的查找、插入和刪除在平均和壞情況下都是O(logn)。

如果在AVL樹中插入或刪除節(jié)點(diǎn)后，使得高度之差大于1。此時(shí)，AVL樹的平衡狀態(tài)就被破壞，它就不再是一棵二叉樹;為了讓它重新維持在一個(gè)平衡狀態(tài)，就需要對(duì)其進(jìn)行旋轉(zhuǎn)處理。

主要應(yīng)用于windows對(duì)進(jìn)程地址空間的管理。

AVL樹的節(jié)點(diǎn)結(jié)構(gòu)是：

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樹的根節(jié)點(diǎn)保存在進(jìn)程內(nèi)核對(duì)象_EProcess中。_EProcess的結(jié)構(gòu)沒(méi)有出現(xiàn)在文檔中，但是我們可以通過(guò)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輸根節(jié)點(diǎn)所在的地址。因此，在驅(qū)動(dòng)程序中，通過(guò)以下代碼可以獲取當(dāng)前進(jìn)程的AVL樹的根節(jié)點(diǎn)地址。

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. }

既然獲得了根地址，則可以對(duì)二叉樹進(jìn)行遍歷，打印出整個(gè)數(shù)據(jù)結(jié)構(gòu)。以下是某個(gè)測(cè)試進(jìn)程在進(jìn)行了1024*1024次new分配后，AVL樹的內(nèi)容。可以看到，樹基本是平衡的。

0,0
├─────N
└─────280,2b3
            ├─────150,24f
            │          ├─────130,134
            │          │          ├─────20,20
            │          │          │          ├─────10,10
            │          │          │          └─────30,12f
            │          │          └─────140,140
            │          └─────260,275
            │                      ├─────250,25f
            │                      └─────N
            └─────10200,10372
                        ├─────400,502
                        │          ├─────310,315
                        │          │          ├─────2c0,300
                        │          │          └─────370,37f
                        │          │                      ├─────320,360
                        │          │                      └─────380,382
                        │          └─────c10,140f
                        │                      ├─────610,80f
                        │                      │          ├─────510,60f
                        │                      │          └─────810,c0f
                        │                      └─────2410,440f
                        │                                  ├─────1410,240f
                        │                                  └─────4410,840f
                        └─────7c930,7c9ff
                                   ├─────10540,1853f
                                   │          ├─────10480,10536
                                   │          └─────7c800,7c92a
                                   │                      ├─────18540,2853f
                                   │                      └─────N
                                   └─────7ffdd,7ffdd
                                               ├─────7ffa0,7ffd2
                                               │          ├─────7f6f0,7f7ef
                                               │          └─────N
                                                └─────7ffde,7ffde

(2)字典樹，又稱為單詞查找樹，Tire數(shù)，是一種樹形結(jié)構(gòu)，它是一種哈希樹的變種。

它是不同字符串的相同前綴只保存一份。

相對(duì)直接保存字符串肯定是節(jié)省空間的，但是它保存大量字符串時(shí)會(huì)很耗費(fèi)內(nèi)存(是內(nèi)存)。

類似的有：前綴樹(prefix tree)，后綴樹(suffix tree)，radix tree(patricia tree, compactprefix tree)，crit-bit tree(解決耗費(fèi)內(nèi)存問(wèn)題)，以及前面說(shuō)的double array trie。

前綴樹：字符串快速檢索，字符串排序，長(zhǎng)公共前綴，自動(dòng)匹配前綴顯示后綴。

后綴樹：查找字符串s1在s2中，字符串s1在s2中出現(xiàn)的次數(shù)，字符串s1,s2長(zhǎng)公共部分，長(zhǎng)回文串。

trie 樹的一個(gè)典型應(yīng)用是前綴匹配，比如下面這個(gè)很常見(jiàn)的場(chǎng)景，在我們輸入時(shí)，搜索引擎會(huì)給予提示。