红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。简单说就是可用于二分查找的（二叉查找树），且高度是平衡的（二叉平衡树）二叉树。红黑树的用途有很多，常用来构造关联数组和集合，STL的关联容器的底层数据结构就是黑红树。

我们知道，对于n个元素的数组arr[n]，如果要查找元素i:

情况1：如果arr[n]没有排序，我们做顺序查找，其时间复杂度是n；

情况2：如果arr[n]有排序，我们做二分法查找，其时间复杂度是logn；

如果数据结构是二叉树，并能实现查找的时间复杂度是logn，则这棵二叉树必须是一棵红黑树。

1.1 左子数上所有的节点的值都小于或等于他的根节点上的值；

1.2 右子树上所有节点的值均大于或等于他的根节点的值；

1.3 左、右子树也分别为二叉查找树；

如下图就是一棵二叉查找树：

可以看到如果要查询10的话，10>9，在右子树查找：

右子树根节点为13，10<13，在左子树查找：

左子树根节点为11>10，继续在左子树查找