1.树
1.1 树定义：是n>0个结点的有序集。n=0时称为空树，在任何一颗非空树中：
1）：有且仅有一个特定的称为根（Root）的节点。
2）：当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1，T2----Tn,其中每一个集合又是一棵树，并且称为根的子数。
由树的定义可以看出，树的定义使用了递归的方式，递归在树的学习过程中起着重要作用。
3）结点拥有的子树数目称为结点的度。
1.2 二叉树
1）定义：
二叉树是n（n>=0）个结点的有限集合，改集合或者为空集（空二叉树），或者由一个根结点和两颗互不相交的，分别称为根节点的左子树和右子树
2）特点
- 每个节点最多有两颗子树，所以二叉树中不存在度大于2的特征
- 左子树和右子树是有序的，次序不能任意颠倒。
- 及时树中只有一颗子树，也要区分是左树和右树。
3）斜树
所有的结点都只有左子树的二叉树叫左斜树。所有结点都只有右子树的二叉树叫右斜树。这两者统称为斜树。
4）满二叉树
在一颗二叉树上，如果所有分支结点都存在左子树和右子树，并且所有的叶子节点都在同一层，这样的二叉树叫做满二叉树。
5）完全二叉树
对一颗具有n个结点的二叉树按层编号，如果编号为1<=i<=n的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这颗二叉树称为完全二叉树。
注：满二叉树一定是完全二叉树，反之则不一定成立。
1.3 二叉树的存储结构
2. 红黑树简介
R-B Tree 全称是Red-Black Tree,又称红黑树，它是一种特殊的二叉查找树。红黑树每个节点上都有存储位表示节点的颜色，可以是红色或者黑色。
红黑树特点
- 每个节点或者是黑色或者是红色。
- 根节点是黑色。
- 每个叶子节点（NIL）是黑色.这里叶子节点是指为空（NIL或NULL）的叶子节点。
- 如果一个节点是红色的，则它的子节点必须是黑色的。
- 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
2.1 红黑树应用
主要应用存在有序的数据，它的时间复杂度为O（lgn）,效率非常高
例如：java集合中TreeSet和TreeMap,以及liunx虚拟内存的管理，都是通过红黑树实现的
2.2 红黑树时间复杂度
红黑树的时间复杂度为：o(lgn)
2.3 红黑树基本操作（一）左旋右旋
红黑树的基本操作是增加，删除。在对红黑树进行增加删除后需要使用旋转来保持红黑树的特性
左旋：
对x进行左旋，就是以x节点右节点作为父节点，即将x变成一个左节点。因此左旋中的左意味着被旋转的节点将变成一个左节点。
右旋：
对x进行右旋，就是以x节点左节点作为父节点，即将x变成一个右节点。因此右旋中的右意味着被旋转的节点将变成一个右节点。