国产成人精品三级麻豆,色综合天天综合高清网,亚洲精品夜夜夜,国产成人综合在线女婷五月99播放,色婷婷色综合激情国产日韩

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

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

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

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

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

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

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

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

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

既然獲得了根地址，則可以對二叉樹進行遍歷，打印出整個數(shù)據(jù)結(jié)構(gòu)。以下是某個測試進程在進行了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)，它是一種哈希樹的變種。

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

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

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

前綴樹：字符串快速檢索，字符串排序，長公共前綴，自動匹配前綴顯示后綴。

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

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