概念
树是图的子集，是一种一定有一个根节点(root)的无环图。
Binary Tree
Binary Search Tree
二叉查找树(BST): 要么是一颗空树，否则对于任意节点
- 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值
- 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值
- 任意节点的左、右子树也分别为二叉查找树
- 没有键值相等的节点。
中序遍历二叉查找树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉查找树变成一个有序序列，构造树的过程即为对无序序列进行查找的过程。每次插入的新的结点都是二叉查找树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索、插入、删除的复杂度等于树高，期望O(log n)，最坏O(n)（数列有序，树退化成线性表）。
Self-Balancing Binary Search Tree
平衡二叉搜索树: 任意节点的左子树的高度差不超过1的二叉搜索树。常见的平衡二叉搜索树有AVL Tree，Red-Black Tree，Treap，节点大小平衡树
AVL Tree
红黑树
B Tree
衍生自Self-Balancing Binary Search Tree，但是不同的是，B树是多路的(一个节点可以有2个以上的子节点)。B树是一种自平衡的树，并且保持数据有序，能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。B树非常适合于读写存储在存储系统(如磁盘)中的相对较大的数据块，所以它通常用于数据库和文件系统中，例如 MongoDB。
B+ Tree
B+ Tree是一种多路查询树，它的查询速度与树的高度有关，即O(log n)
