二叉查找树（二叉排序树）
二叉查找树是一种动态查找表
性质
（1）若它的左子树不为空，则左子树上的所有节点的值都小于它的根节点的值；
（2）若它的右子树不为空，则右子树上所有节点的值都大于它的根节点的值；
（3）其他的左右子树也分别为二叉查找树；
（4）二叉查找树是动态查找表，在查找的过程中可见添加和删除相应的元素，在这些操作中需要保持二叉查找树的以上性质。
应用
- 判断一个单词是否拼写正确
- 请模拟实现一个简单的中英互译的字典
- log 文件中有许多异常重复的 IP 地址，请统计出每个异常 IP 出现了多少次？
平衡二叉树之 AVL 树
含有相同节点的二叉查找树可以有不同的形态，而二叉查找树的平均查找长度与树的深度有关，所以需要找出一个查找平均长度最小的一棵，那就是平衡二叉树
性质
（1）要么是棵空树，要么其根节点左右子树的深度之差的绝对值不超过 1；
（2）其左右子树也都是平衡二叉树；
（3）二叉树节点的平衡因子定义为该节点的左子树的深度减去右子树的深度。则平衡二叉树的所有节点的平衡因子只可能是 -1,0,1。
最小二叉平衡树的节点的公式如下：
F(n)=F(n-1)+F(n-2)+1
应用
1、实现快速查找
2、windows 对进程地址空间的管理用到了 AVL
平衡二叉树之红黑树
红黑树是一种自平衡二叉树，在平衡二叉树的基础上每个节点又增加了一个颜色的属性，节点的颜色只能是红色或黑色。
性质
（1）根节点只能是黑色；
（2）红黑树中所有的叶子节点后面再接上左右两个空节点，这样可以保持算法的一致性，而且所有的空节点都是黑色；
（3）其他的节点要么是红色，要么是黑色，红色节点的父节点和左右孩子节点都是黑色，及黑红相间；
（4）在任何一棵子树中，从根节点向下走到空节点的路径上所经过的黑节点的数目相同，从而保证了是一个平衡二叉树。
应用
TODO
B- 树
不是念 B减树，就是 B树，多路平衡查找树
性质
（1）树中每个节点至多有 m 棵子树；
（2）若根节点不是叶子节点，则至少有 2 棵子树；
（3）除根节点之外的所有非终端节点至少有
棵子树；
（4）每个节点中的信息结构为（A0,K1,A1,K2......Kn,An），其中 n 表示关键字个数，Ki 为关键字，Ai 为指针；
（5）所有的叶子节点都出现在同一层次上，且不带任何信息，也是为了保持算法的一致性。
应用
文件系统
B+ 树
B+ 数是 B- 树的一种变形
性质
它与 B- 树的差别在于：
（1）有 n 棵子树的节点含有 n 个关键字；
（2）所有的叶子节点包含了全部关键字的信息，及指向这些关键字记录的指针，且叶子节点本身按关键字大小自小到大顺序链接；
（3）所有非终端节点可以看成是索引部分，节点中仅含有其子树（根节点）中最大（或最小）关键字，所有 B+ 树更像一个索引顺序表；
（4）对 B+ 树进行查找运算，一是从最小关键字起进行顺序查找，二是从根节点开始，进行随机查找。
应用
TODO
字典树（tire 树）
字典树是一种以树形结构保存大量字符串，以便于字符串的统计和查找
性质
（1）根节点为空；
（2）除根节点外，每个节点包含一个字符；
（3）从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
（4）每个字符串在建立字典树的过程中都要加上一个区分的结束符，避免某个短字符串正好是某个长字符串的前缀而淹没。
应用
搜索引擎系统用于文本词频统计
参考
贡献者
jiechen