二叉查找树
它不为空树时，它左子树上所有的元素都小于根节点的元素，而根节点右子树上所有的元素都大于根节点的元素。
为了保证二叉查找树不失衡（出现线性查找的情况），就有了平衡的二叉查找树：红黑树。
平衡二叉树（AVL树）：
平衡二叉树又称为AVL树，是一种特殊的二叉排序树。其左右子树都是平衡二叉树，且左右子树高度之差的绝对值
不超过1。一句话表述为：以树中所有结点为根的树的左右子树高度之差的绝对值不超过1。将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF，那么平衡二叉树上的所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。
红黑树：
红黑树是一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是红或黑（非红即黑）。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍，因此，红黑树是一种弱平衡二叉树，相对于要求严格的AVL树来说，它的旋转次数少，所以对于搜索，插入，删除操作较多的情况下，通常使用红黑树。
红黑树
特性
- 满足二叉树的型组织
- 每个节点或者是黑色，或者是红色。
- 根节点是黑色。
- 每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
- 如果一个节点是红色的，则它的子节点必须是黑色的。
- 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
插入一个元素到红黑树的时间为log(N)；采用迭代器遍历一棵红黑树的时间复杂度是O(N)
红黑树什么时候需要变色或者左旋右旋？
为了满足如上的规则，实现结构的平衡，我们在插入或删除节点的时候，就需要做一些相应的调整，就是对应的变色，左旋，右旋操作。
红黑树的插入
如果插入的节点是根节点，也就是说初始的红黑树为空，这是最简单的情况，直接将该节点标识成黑色即可。
如果新插入的节点不是红黑树的根节点，如果新插入的节点的父节点是黑色的话，那么红黑树是不需要调整的
如果新插入的节点的父亲P和叔叔U都是红色的情况。这时，将P、U都染成黑色，而G染成红色以满足性质5（从任一节点出发到其每个叶子节点的路径，黑色节点的数量是相等的）。现在，当前的红色节点N有一个黑色的父亲，而且所有经过父亲和叔叔节点的路径仍然保持与原来相同的节点个数。但是爷爷节点G可能会违反性质2（根节点必须是黑色）或者性质4（红色节点必须有两个黑色儿子节点）（在G节点的父亲也是红色节点时，会破坏性质4）。要修复这个问题，可以对节点G递归执行Case1的操作
父亲P是红色，叔叔U是黑色，并且N是P的右孩子，P是G的左孩子的情况。这时，对节点P执行左旋操作，使P变成N的左孩子,N变成G的左孩子,也就是说进入了5 的情况。
父亲P是红色，但叔叔U是黑色， N是左孩子，P也是左孩子的情况。此时，对节点G执行一次右旋。使P成为N和G的父节点。已知G是黑色（P是红色，为了不破坏性质4（红色节点必须有两个黑色儿子节点），G肯定是黑色），所以将G染成红色，P染成黑色。
