在数据结构中我们会学习到一种特殊的结构-----树。老实说刚开始学这段时，感觉树的逻辑太复杂，比之链表、队列、栈都要复杂很多，但是慢慢接触并且在自己敲过代码之后，发现二叉树其实逻辑和我们日常思维逻辑一样简单，它的存储结构和双向链表的存储结构一样。这是刚开始接触树的印象，本文属于树的升级版。
(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
├─────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数，是一种树形结构，它是一种哈希树的变种。
它是不同字符串的相同前缀只保存一份。
相对直接保存字符串肯定是节省空间的，但是它保存大量字符串时会很耗费内存(是内存)。
类似的有：前缀树(prefix tree)，后缀树(suffix tree)，radix tree(patricia tree, compactprefix tree)，crit-bit tree(解决耗费内存问题)，以及前面说的double array trie。
前缀树：字符串快速检索，字符串排序，长公共前缀，自动匹配前缀显示后缀。
后缀树：查找字符串s1在s2中，字符串s1在s2中出现的次数，字符串s1,s2长公共部分，长回文串。
trie 树的一个典型应用是前缀匹配，比如下面这个很常见的场景，在我们输入时，搜索引擎会给予提示。
嵌入式物联网需要学的东西真的非常多，千万不要学错了路线和内容，导致工资要不上去！
无偿分享大家一个资料包，差不多150多G。里面学习内容、面经、项目都比较新也比较全！某鱼上买估计至少要好几十。（点击找小助理领取）
