数据结构树应用在哪儿比较多

在数据结构中我们会学习到一种特殊的结构-----树。老实说刚开始学这段时，感觉树的逻辑太复杂，比之链表、队列、栈都要复杂很多，但是慢慢接触并且在自己敲过代码之后，发现二叉树其实逻辑和我们日常思维逻辑一样简单，它的存储结构和双向链表的存储结构一样。这是刚开始接触树的印象，本文属于树的升级版。

(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。里面学习内容、面经、项目都比较新也比较全！某鱼上买估计至少要好几十。（点击找小助理领取）