树，二叉树，二叉搜索树，平衡树（AVL），红黑树，2-3树，B树，B+树

树是一种很特别的数据结构，树这种数据结构叫做树就是因为它长得像一棵树，但是这颗树确实一棵倒着的树，根在上，叶在下，
树是图的一种，区别是，树是没有环的，而图是可以有环，（环：从节点按照顺序出发，经过多个节点，能否回到本节点）

树（Tree）基本概念：

树是由节点或顶点和边组成的（可能是非线性的）且不存在着任何环的一种数据结构，
没有节点的树成为空（null或empty）树，
一棵非空的树包含一个根节点，还（很可能）由很多附加节点，所有的节点构成一个多级分层结构

树的一些术语定义：

节点的度：一个节点含有的子树的个数称为该节点的度
叶节点：度为9 的节点成为叶节点
分支节点：度不为0 的节点
父节点：若一个节点含有子节点，则这个节点称为起子节点的父节点
子节点：一个节点含有的子树的根节点，称为该节点的子节点
兄弟节点：具有相同父节点的节点，互称为兄弟节点，
树的度：一棵树中最大的节点的度称为树的度
节点的层次：从根开始定义起，根为第一层，根的子节点为第二层，以此类推
树的高度或者深度：树中节点的最大层次
堂兄弟节点：双亲在同一层的节点互为堂兄弟
节点的祖先：从根到该节点所经分支上的所有节点
子孙：以某节点为根的子树种任一节点都称为该节点的子孙
森林：由m（m>=0）棵不相交的树的集合称为森林

树的表现方式

图像表现法，符号表现法和遍历表示法

二叉树

每个节点至多拥有两颗子树（即二叉树中不存在度大于2的节点），并且，二叉树的子树由左右之分起次序不能颠倒，常用来实现二叉查找树和二叉堆
二叉树分为：完美二叉树（满二叉树），完全二叉树，完满二叉树
二叉树是无序的

二叉查找树

也叫有序二叉查找树，左子树小于父节点，右子树大于父节点，但是不是平衡的，
因为有时候会退化为线性表，所以有了平衡二叉树

AVL树

也叫平衡树，左右子树高度不贵超过1，通过旋转来维持平衡，（左旋，右旋）
添加：直接添加到底部叶子节点，然后通过旋转来维持平衡
删除：叶子节点，非叶子节点，非叶子节点通过置换原则替换成叶子节点（前驱节点，后驱节点）
因为需要平衡，需要多次旋转，比较浪费资源，所以有了红黑树

红黑树

红黑树跟AVL树相比，多了颜色区别，红黑，没有AVL树的那种高度差不超过1的平衡，红黑树维持的是每条路径的黑色节点相同，这种平衡，红色不计算在内，
相比于AVL树，平衡要求没有那么高，旋转次数减小，
红黑树的操作，只是比AVL树多了变色，都是固定的情况固定的操作
添加：在根部添加红色叶子节点，然后自平衡，旋转，换色
删除：叶子节点，非叶子节点，也是置换成为叶子节点后删除，通过分析红黑，旋转，变色，实现自平衡
红黑树其实是2-3树，是2-3树用二叉树的形式表现出来的

2-3树

就是子树的数量是2个或者三个，不过是绝对平衡，左右子树高度一致
其他的跟二叉树没什么区别，
添加：通过判断，直接添加到已有叶子节点中，然后判断数量，超出，向上移动，直到推到根节点
删除：叶子节点与非叶子节点，非叶子节点通过替换成为叶子节点删除，删除叶子节点，判断最小数量，不够向兄弟元素借，或者合并兄弟元素，达到绝对平衡
红黑树就是2-3树转换的，因为节点存在2个或者一个元素，将左侧的元素分离开，成为2个节点，3个子节点，再将左侧节点成为右侧节点的左子树，标记上红色，就成为了红黑树

B树

平衡多路搜索树，不止有两个子树，树的高度比较低，所有的叶子节点都在同一层，
有序数组+平衡多叉树
添加：跟2-3树类似，先添加到叶子节点中，然后判断数量，向上移动合并，
删除：非叶子节点删除，通过替换转换成删除叶子节点，叶子节点删除，判断数量，向兄弟节点或者父节点借一个元素，

B+树

B树的变体，跟B树相比，B+树的非叶子节点不会存储数据，只有有关键字，所有的数据都存储在叶子节点，并且通过链表关联起来，（没有具体的定义，节点数，跟阶数的关系，没有确定）
有序数组链表+平衡多叉树
添加：添加到叶子节点，判断数量，向上移动，
删除：非叶子节点，替换后驱元素，转换成删除叶子节点，删除叶子节点，判断数量，向兄弟节点或者父节点借一个元素，
B+树的优点：
1.层次更低，IO次数更少
2.每次都需要查询到叶子节点，查询性能稳定
3.叶子节点形成有序链表，范围查询方便
B+树还有一个虽大的好处，方便扫库，B树必须用中序遍历的方法按序扫库，而B+树直接从叶子节点挨个扫一遍就可以，B+树支持range-query 非常方便，而B树不支持，这就是数据库用B+树的主要原因