1.二叉排序树
二叉排序树（Binary Sort Tree）又称二叉查找树（Binary Search Tree），亦称二叉搜索树。
定义：
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的节点。
主要操作：
（1）遍历（小到大）
（2）查找结点
（3）求子树的最大最小值
（4）求前趋和后继结点
（5）插入结点
（6）删除结点
简单描述：
（1）最大值：左孩子的左孩子的……左孩子的左孩子
（2）最小值：右孩子的右孩子的……右孩子的右孩子
（3） 前趋：
<情况一：>有左子树，则左孩子的右孩子的右孩子的右孩子……的右孩子。
<情况二：>无左子树，且为父结点的右孩子，则为父结点。
否则无前趋。
（4）后继：
<情况一：>有右子树，则右孩子的左孩子的左孩子的左孩子……的左孩子。
<情况二：>情况二：无右子树，且为父结点的左孩子，则为父结点。
否则无后继。
（5）删除结点：
<情况一：>结点为叶子结点，则直接删除结点，把父结点的对应指针设为NULL。
<情况二：>结点有一个孩子，则把结点的孩子代替结点的位置。
<情况三：>结点左、右孩子都有，则把结点的左孩子代替结点的位置，把右孩子接到左孩子的最右边。也可以找到结点的直接前驱（或直接后继），用直接前驱（或后继）来替换删除结点，然后再删除直接前驱（或后继）结点。（这种方法较麻烦！！！）如图两种情况：
模板题：https://www.luogu.org/problem/show?pid=3369
题解： http://www.cnblogs.com/zwfymqz/p/7151959.html#_label2
2.SPLAY伸展树
简介：
伸展树(Splay Tree)是一种二叉排序树，它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。 摊平时间是指在一系列最坏情况的操作序列中单次操作的平均时间。 类别：二叉排序树 空间效率：O(n) 时间效率：O(log n)内完成插入、查找、删除操作 功能超级强大！！
简单介绍一下操作：
SPLAY树的基本操作：
（1）旋转和伸展
（2）查找
（3）插入、删除
（4）最大最小值
（5）前驱后继
（6）合并、分离
详细介绍一下：
差不多就这些了，对于指针版的代码，并不懂。
3.AVL树：
摘自 teacher'ppt。