目录
二叉树
满二叉树
完全二叉树
平衡二叉树
B树和B+树
红黑数
二叉树
二叉树的存储分为：链式存储，顺序存储
二叉树的遍历： 先序（根左右） ，中序（左根右） ，后序 （右左根）
满二叉树
每一层的节点数都达到最大的值
完全二叉树
除了最后一层，其他层都是满的，最后一层可以是满的，或者是在右边缺少连续节点
平衡二叉树
左子树和右子数的高度绝对值不超过1
B树和B+树
定义：
B 树，指多叉搜索树，一颗M阶B树的定义是指。 定义
1）树的每个结点最多包含m个孩子
2）除了根结点和叶子结点外，它的每个节点至少包含 m/2 个孩子
3）若根结点不是叶子结点，则至少有2个孩子
4）所有叶子结点都在同一层，叶子结点不包含任何关键字信息
区别：
1）B+数的所有子节点都是通过指针连接到一起
2）B 树把key 和data 放在每个节点，B+数将data 放在叶子节点，非叶子节点只存key 值关键信息，每个叶子节点之间都有一个链指针。
3)B+数的叶子节点的关键字是从小到排序，左边结尾数据会保留右边开始数据的指针。
B+树：
红黑数
红黑数需要满足5个条件：
- 每个节点不是红色就是黑色
- 根节点必须是黑色
- 每个叶子节点都是黑色的空节点（NIL）
- 如果节点是红色节点，那么它的子节点必须是黑色的
- 从根节点到每个叶子节点或者空子节点的每条路径，所包含的 黑色子节点数是一样的。
TreeMap ,TreeSet 和 HashMap 都用了红黑数， hashMap 是采用二叉查找数，它在某种顺序插入的情况下会变成线性结构，红黑数可以解决这个问题，红黑树的的添加和删除元素的时间复杂度是O(logn)
