BST：二叉搜索树，所有节点的左子树都小于右,子树。读和写的复杂度都是O(logN)。
缺点：当是顺序情况下，复杂度是O(N)
AVL：平衡二叉树，左子树和右子树深度差小于等于1，是BST的一种。读和写都是O(logN)而且最坏情况下也是O(logN)。相对于BST是一种很好的优化。
红黑树： root节点是一个黑节点（B），叶结点（包括null）也必须是黑节点（一半以上都是黑节点）。红节点的子节点必须是黑节点。新插入的节点必须是红节点。从任意一个节点出发到叶子结点的黑节点都是一样的（此条件的上界：结点数相同，下界：结点数差一倍）。读写复杂度：O（logN）
红黑树对于任意节点开始黑节点都是一样可以是这样两种情况：五个节点都是黑节点，或者是十个红盒相间的节点。
红黑树相对于AVL树的平衡条件更宽松，只需要左右深度差一倍以内。
TreeMap和HashMap都是使用红黑树，而不是AVL树，更不是BST树。
红黑树插入流程：
类型：当前节点相对于它的爷爷是什么方向。
左旋：
上面左图（a-b-c）向右图的装换就是左旋，若b节点有个左节点”星“，那么左旋之后”星“是变成a的右节点还是c的左节点呢？其实都是可以的。但是要考虑c节点是否在左旋之前就有”x，y“节点，否则”星“就去挂在a上当它的右儿子。当然”星“是一定可以去a节点的，因为a原来的右节点是b，左旋之后b变成了父节点，a的右边就没有节点了，这个空位就留给了“星”。
右旋：
