概念篇
1.BST， 二叉查找树，也叫二叉搜索树、二叉排序树，Binary Search Tree
在二叉查找树中，有以下性质；
- 若任意节点的左子树不为空，则左子树上的所有节点的值小于它的根节点；
- 若右子树不为空，则右子树的所有节点大于它的根节点；
- 任意节点的左右子树也都是二叉查找树；
- 树中不存在重复值；（也可以通过链表或动态数组把数值相同的数据存储在一个节点上，或者把新插入的数据当做大于这个节点的值来处理）
二叉查找树的中序遍历一定是从小到大的。
2.AVL，平衡搜索二叉树
平衡二叉树的提出就是为了保证树不会太倾斜，尽量维持两边平衡。定义如下：
- 平衡二叉树要么是一棵空树
- 要么保证左右子树的高度之差不大于 1
- 子树也必须是一颗平衡二叉树
3.RBT，红黑树
转自：BST 二叉排序树，AVL 平衡二叉树，RBT 红黑树，B - 树，B + 树，B * 树
AVL 是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多；
红黑是弱平衡的，用非严格的平衡来换取增删节点时候旋转次数的降低；
所以简单说，搜索的次数远远大于插入和删除，那么选择 AVL 树，如果搜索，插入删除次数几乎差不多，应该选择 RB 树。
红黑树上每个结点内含五个域，color，key，left，right，p。如果相应的指针域没有，则设为 NIL。
一般的，红黑树，满足以下性质，即只有满足以下全部性质的树，我们才称之为红黑树：
1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
最后两点证明高度差是小于两倍的；
4.Size Balanced Tree，SB 树
同一层的节点称为叔叔节点，叔叔节点的子节点为侄子节点。
SB 树的平衡性来自于，任何一个叔叔节点的节点个数，不能少于任何一个侄子节点的节点个数。
5. 各种树操作的时间复杂度对比
最后附上一张对比图（来自：https://blog.csdn.net/wuhuagu_wuhuaguo/article/details/78531650）
