有关树的查找、插入、删除等等这里先不复制了（

树

树就是一种类似现实生活中的树的数据结构（倒置的树）。任何一颗非空树只有一个根节点。

一棵树具有以下特点：

一棵树中的任意两个结点有且仅有唯一的一条路径连通。
一棵树如果有 n 个结点，那么它一定恰好有 n-1 条边。
一棵树不包含回路。

二叉树

二叉树（Binary tree）是每个节点最多只有两个分支（即不存在分支度大于 2 的节点）的树结构。

二叉树 的分支通常被称作“左子树”或“右子树”。并且，二叉树 的分支具有左右次序，不能随意颠倒。

二叉树 的第 i 层至多拥有 2^(i-1) 个节点，深度为 k 的二叉树至多总共有 2^(k+1)-1 个节点（满二叉树的情况），至少有 2^(k) 个节点（关于节点的深度的定义国内争议比较多，我个人比较认可维基百科对[节点深度的定义）。

满二叉树

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是 满二叉树。也就是说，如果一个二叉树的层数为 K，且结点总数是(2^k) -1 ，则它就是 满二叉树。

满二叉树

完全二叉树

除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则这个二叉树就是 完全二叉树 。

具有n个结点的完全二叉树的深度为：
$$
\left \lfloor log_{2}n \right \rfloor +1
$$

完全二叉树有一个很好的性质：父结点和子节点的序号有着对应关系。

细心的小伙伴可能发现了，当根节点的值为 1 的情况下，若父结点的序号是 i，那么左子节点的序号就是 2i，右子节点的序号是 2i+1。这个性质使得完全二叉树利用数组存储时可以极大地节省空间，以及利用序号找到某个节点的父结点和子节点。

二叉查找树 BST

二叉排序树（Binary Sort Tree）又称二叉查找树、二叉搜索树。

它或者是一棵空树，或者是具有下列性质的二叉树：

若左子树不空，则左子树上所有结点的值均小于它的根结点的值。
若右子树不空，则右子树上所有结点的值均大于它的根结点的值。
左、右子树也分别为二叉排序树。

原理：

若根结点的关键字值等于查找的关键字，成功。
否则，若小于根结点的关键字值，递归查左子树。
若大于根结点的关键字值，递归查右子树。
若子树为空，查找不成功。

图片有点丑别在意，重点是对于二叉搜索树的理解

平衡二叉树

平衡二叉树 是一棵二叉排序树，且具有以下性质：

可以是一棵空树
如果不是空树，它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。

平衡二叉树的常用实现方法有 红黑树、AVL 树、替罪羊树、加权平衡树、伸展树 等。

AVL 树是一种改进版的二叉搜索树，其引入平衡因子（左子支高度与右子支高度之差的绝对值），通过旋转使其尽量保持平衡。

B树 / B-树

B-树是一种平衡的多路查找树（并非二叉的），注意： B树就是B-树，”-“是个连字符号，不是减号 。

一棵m阶的非空B-树具有如下性质：

① 树中每个结点至多有m 棵子树；

② 若根结点不是叶子结点，则至少有两棵子树；

③ 除根之外的所有非叶子结点至少有子树的数量为：
$$
\left \lceil \frac{m}{2} \right \rceil
$$
④ 所有的非叶子结点中包含下列信息数据：(P0, K1, P1, K2, P2, …, Kn, Pn)，其中，Ki（1≤i≤n）为关键字，且Ki＜Ki+1，Pi（1≤i≤n）为指向子树根结点的指针，且指针Pi–1所指子树中所有结点的关键字均小于Ki (i=1, 2, …, n)，Pn所指子树中所有结点的关键字均大于Kn，n为关键字的个数；

其中，
$$
\left \lceil \frac{m}{2} \right \rceil-1\le n\le m-1
$$
⑤ 所有叶子结点都出现在同一层次上，且不包含任何信息

一棵4阶的B-树如下图所示。

B+树

B+树是B-树的一种变形，它和B-树的差别在于：

①有n棵子树的结点中含有n个关键字；

②所有的叶子结点中包含了全部关键字的信息及指向含这些关键字记录的指针，且叶子结点本身按关键字的大小顺序链接；

③所有的分支结点可看成是索引部分，结点中仅含其子树（根结点）中最大（或最小）的关键字。

一棵3阶的B+树如下图所示。通常，在B+树上有两个指针，一个指向根结点，一个指向关键字最小的叶子结点。

B 树& B+树两者有何异同呢？

B 树的所有节点既存放键(key) 也存放数据(data)，而 B+树只有叶子节点存放 key 和 data，其他内节点只存放 key。
B 树的叶子节点都是独立的;B+树的叶子节点有一条引用链指向与它相邻的叶子节点。
B 树的检索的过程相当于对范围内的每个节点的关键字做二分查找，可能还没有到达叶子节点，检索就结束了。而 B+树的检索效率就很稳定了，任何查找都是从根节点到叶子节点的过程，叶子节点的顺序检索很明显。
在 B 树中进行范围查询时，首先找到要查找的下限，然后对 B 树进行中序遍历，直到找到查找的上限；而 B+树的范围查询，只需要对链表进行遍历即可。

B*树

是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；

B*树分配新结点的概率比B+树要低，空间使用率更高。

红黑树

红黑树（Red Black Tree）是一种自平衡二叉查找树，由 2-3 树（最简单的 B-树）发展而来。

由于其自平衡的特性，保证了最坏情形下在 O(logn) 时间复杂度内完成查找、增加、删除等操作，性能表现稳定。

但相比于 AVL 树，高度平衡所带来的时间复杂度，红黑树对平衡的控制要宽松一些，红黑树只需要保证黑色节点平衡即可。

在 JDK 中，TreeMap、TreeSet 以及 JDK1.8 的 HashMap 底层都用到了红黑树。

红黑树特点

红黑树在每个节点上增加一个属性表示节点颜色，每个节点非红即黑。黑色决定平衡，红色不决定平衡。这对应了 2-3 树中一个节点内可以存放 1~2 个节点。
根节点总是黑色的。
每个叶子节点都是黑色的空节点（NIL 节点）。这里指的是红黑树都会有一个空的叶子节点，是红黑树自己的规则。
如果节点是红色的，则它的子节点必须是黑色的（反之不一定）。通常这条规则也叫不会有连续的红色节点。一个节点最多临时会有 3 个节点，中间是黑色节点，左右是红色节点。
从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）。每一层都只是有一个节点贡献了树高决定平衡性，也就是对应红黑树中的黑色节点。

正是这些特点才保证了红黑树的平衡，让红黑树的高度不会超过 2log(n+1)。

红黑树通过重新着色和左右旋转，更加高效地完成了插入和删除之后的自平衡调整。

红黑树结构实现

public class Node {

    public Class<?> clazz;
    public Integer value;
    public Node parent;
    public Node left;
    public Node right;

    // AVL 树所需属性
    public int height;
    // 红黑树所需属性
    public Color color = Color.RED;

}