数据结构树应用在哪儿比较多
时间：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 树的一个典型应用是前缀匹配，比如下面这个很常见的场景，在我们输入时，搜索引擎会给予提示。
