红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。简单说就是可用于二分查找的（二叉查找树），且高度是平衡的（二叉平衡树）二叉树。红黑树的用途有很多，常用来构造关联数组和集合，STL的关联容器的底层数据结构就是黑红树。
我们知道，对于n个元素的数组arr[n]，如果要查找元素i:
情况1：如果arr[n]没有排序，我们做顺序查找，其时间复杂度是n；
情况2：如果arr[n]有排序，我们做二分法查找，其时间复杂度是logn；
如果数据结构是二叉树，并能实现查找的时间复杂度是logn，则这棵二叉树必须是一棵红黑树。
1 二叉查找树1.1 左子数上所有的节点的值都小于或等于他的根节点上的值；
1.2 右子树上所有节点的值均大于或等于他的根节点的值；
1.3 左、右子树也分别为二叉查找树；
如下图就是一棵二叉查找树：
可以看到如果要查询10的话，10>9，在右子树查找：
右子树根节点为13，10<13，在左子树查找：
左子树根节点为11>10，继续在左子树查找
