1. 知识体系结构
2. 树
树是一种数据结构，它是n(n>=0)个结点的有限集， n=0时为空树，n>0时，有限集的元素构成一个具有层次感的数据结构
区别与线性表一对一的元素关系，树中的结点时一对多的关系。具有以下特点：
n>0时，根结点是唯一的，不可能存在多个根结点
每个结点右0至多个子结点；除了根姐弟那外，每个结点有且仅有一个父结点，根结点没有父结点
2.1 相关概念
子树：除了根结点外，每个子结点都可以分为多个不相交的子树孩子与双亲：若一个结点有子树，那么该结点称为子树根的”双亲”，子树的根是该结点的”孩子”兄弟：具有相同双亲的结点互为兄弟，例如B和H结点的度：一个结点拥有子树的数目，例如A的度为2， B的度为1，C的度为3叶子：没有子树，即度为0的结点分支结点：除了叶子结点之外的结点，也即是度不为0的结点内部结点：除了根结点之外的分支结点层次：根结点为第一层，其余结点的层次等于器双亲结点的层次加1树的高度：也称为树的深度，树中结点的最大层次有序树：树中结点各子树之间的次序是重要的，不可以随意交换位置无序树：树中结点各子树之间的次序是重要的，可以随意交换位置森林：0或多棵互不相交的树的集合，例如图二中的两棵树为森林
3. 常见树
3.1 二叉树、完全二叉树、满二叉树
二叉树：最多有两棵子树的树被称为二叉树
斜树：所有结点都只有左子树的二叉树叫左斜树，所有结点都只有右子树的二叉树为右斜树(本质就是链表)
满二叉树：二叉树中所有非叶子的度都是2，且叶子结点都在同一层次
- 完全二叉树：如果一个二叉树与满二叉树前m个结点的结构相同，这样的二叉树称为完全二叉树
3.2 二叉查找树 BST
二叉查找树(Binary Search Tree)是指一棵控诉或者具有下列性质的二叉树：
- 若任意结点的左子树不空，则左子树上所有的结点的值均小于它的根结点的值；
- 若任意结点的右子树不空，则右子树上所有的结点的值均小于它的根结点的值；
- 任意结点的左、右子树也分别为二叉查找树
- 没有键值相等的结点
二叉查找树相比与其他数据结构的优势在于查找、插入的时间复杂度较低为O(log n)。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、多重集、关联数组等。
3.3 平衡二叉树 AVL
含有相同结点的二叉查找树可以有不同的形态，而二叉查找树的平均查找长度与树的深度有关，所以需要找出一个查找平均长度最小的一棵，那就是平衡二叉树，具有以下性质：
- 要么是空树，要么器根结点左右子树的深度之差的绝对值不超过1；
- 其左右子树也都是平衡二叉树
- 二叉树结点的平衡因子定义为该结点的左子树的深度减去右子树的深度。而平衡二叉树的所有结点的平衡因子只可能是
-1,0,1.
3.4 红黑树
红黑树也是一种自平衡的二叉查找树。
每个结点要么是红的要么是黑的（红/黑）
根结点是黑的（根黑）
每个叶结点（叶结点指尾端NIL指针或NULL结点）都是黑的（叶黑）
如果一个结点是红的，那么它的两个儿子都是黑的（父红子黑）
对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数量的黑结点（路径下黑相同）
用法最广：
Java ConcurrentHashMap & TreeMap
C++ STL: map & set
Linux 进程调度Completely Fail Scheduler, 用红黑树管理进程控制块
epoll在内核中的实现，用红黑树管理事件块
nginx中，用红黑树管理Timer等
3.5 哈夫曼树 Huffman Tree
哈夫曼又称最有二叉树。是一种是带权路径长度最短的树，权值较大的结点离根较近。一般可以按照下面步骤构建：
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
将w1、w2、…，wn看成是有
n棵树的森林(每棵树仅有一个结点)在森林中选出两棵根结点的权值最小的树(2,3)作为一棵新树的左、右子树，且置新树的附加根结点的权值为其左，右子树上根结点的权值之和(5)。注意：左子树的权值应小于右子树的权值。
从森林中删除这两棵树(2,3)，同时把新树加入到森林中
重复2、3步骤，直到森林中只有一棵树为止，此树就是哈夫曼树
例如：对 2，3，4，6 这四个数进行构造
基本概念：
路径：从树中一个结点到另一个结点之间的分之构成这两个结点间的路径结点的路径长度：两结点之间路径的分支数树的路径长度：从树根到每一个结点的路径长度之和权：给树中结点赋一个数值，这个数值称为该结点的权结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积树的带权路径长度：树中所有叶子结点的带权路径长度之和计作WPL（Weighted path Length）
哈夫曼树的特点：
满二叉树不一定是哈夫曼树
哈夫曼树中权越大的叶子离根越近
具有相同带权结点的哈夫曼树不唯一
只有度(子树的个数)为0或2的结点，没有度为1的结点
包含n给叶子结点的哈夫曼树中共有
2n-1个结点
3.6 B树
B树（B-Tree）是一种自平衡树，能够保持数据有序，这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。
概括来说是一种自平衡的m阶树，与自平衡二叉查找树不同，B树更适用于读写相对大的数据块的存储系统，例如磁盘。
根结点至少两个子女
每个中间节点都包含
k-1个元素和k个孩子，其中m/2 <= k <= m每一个叶子节点都包含
k-1个元素，其中m/2 <= k <= m所有叶子节点都在同一层
每个结点中的元素从小到大排雷，结点当中
k-1个元素正好是k个孩子包含的元素的值域分划
B-Tree中的每个节点根据实际情况可以包含大量的关键字信息和分支，如下图所示为一个3阶的B-Tree:
3.7 B+树
B+树是一种树数据结构，通常用于关系型数据库（如Mysql）和操作系统的文件系统中。B+树的特点是能够保持数据稳定有序，其插入与修改用于叫稳定的对数时间复杂度； B+树自底向上插入，这与二叉树恰好相反。
在B树的基础上，为叶子结点增加链表指针（B树+叶子有序链表），所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中。
B+树的非叶子结点不保存数据，只保存子树的临界值(最大或最小)，所以同样大小的结点，B+树相对于B树能右更多的分支，是的这棵树更加矮胖，查询是做的IO操作次数叶更少。
将上一节中的B-Tree优化，由于B+Tree的非叶子节点只存储键值信息，假设每个磁盘块能存储4个键值及指针信息，则变成B+Tree后其结构如下图所示:
3.8 R 树
R树是用来做空间数据存储的树状数据结构，例如给地理为止，矩形和多边形这类多维数据建立索引。
R树的核心思想是聚合距离想尽的节点并在树结构的上一层将其表示为这些节点的最小外接矩形（MBR），这个最小外接矩形就称为上一层的一个节点。因为所有节点都在它们的最小外接矩形中，所以跟某个矩形不想叫的查询就一定跟这个矩形中的所有节点都不相交。
叶子节点上的每个矩形都代表一个对象，节点都是对象的聚合，并且越往上层聚合的对象就越多。也可以把每一层看做是对数据集的近似，叶子节点层是最细粒度的近似，与数据集相似度100%，越往上层越粗糙。
4. 总结
实际应用当中，经常使用的是查找、排序操作，那么不同的数据结构针对查找、排序操作有不一样的优劣性：
数组：数组的下表寻址十分迅速，但是计算机的内存是有限的，所以数组的长度也是有限的，实际应用当中的数据往往十分庞大；而且无序数组的查找最坏情况需要遍历整个数组；后来提出了二分查找，二分查找要求数组的构造一定有序，二分查找解决了普通数组查找复杂度过高的问题。任何一种数组无法解决的问题就是插入、删除操作表复杂，因此，在一个增删改比较频繁的数据结构中，数组不会被优先考虑普通链表：由于他的结构特点被证明根本不适合进行查找哈希表：是数组和链表的这种，同时它的设计依赖散列函数的设计，数组不能无限长、链表也不适合查找，所以也不适合大规模的查找二叉查找树：可能退化称链表，同样不适合进行查找AVL树：是为了解决可能退化成链表问题，但是AVL树的旋转过程非常麻烦，因此插入和删除很慢，也就是构建AVL树比较麻烦红黑树：是平衡二叉树和AVL树的这种，因此是比较合适的。集合类中的Map、关联数组具有较高的查询效率，它们的底层实现是红黑树。多路查找树：是大规模数据存储中，实现索引查询这样一个实际背景下，树节点存储的元素数量是有限的（如果元素数量非常多的划，查找就退化成节点内部的线性查找了），这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下B树：与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如磁盘。它的应用是文件系统及部分非关系型数据库索引B+树：在B树基础上，为叶子结点增加链表指针(B树+叶子有序链表)，所有关键字都在叶子结点 中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中。通常用于关系型数据库(如Mysql)和操作系统的文件系统中。B*树：是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针, 在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3。R树：是用来做空间数据存储的树状数据结构。例如给地理位置，矩形和多边形这类多维数据建立索引Trie树：是自然语言处理中最常用的数据结构，很多字符串处理任务都会用到。Trie树本身是一种有限状态自动机，还有很多变体。什么模式匹配、正则表达式，都与这有关
针对大量数据，如果在内存中作业优先考虑红黑树(map,set之类多为RB-tree实现)，如果在硬盘中作业优先考虑B系列树(B+, B, B*)
