红黑树是平衡二叉树吗
红黑树是平衡二叉树。红黑树在每个节点增加一个存储位表示节点的颜色，可以是红或黑。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍。因此，红黑树是平衡二叉树。
什么是红黑树？
红黑树（Red Black Tree）是一颗自平衡（self-balancing）的二叉排序树（BST），树上的每一个结点都遵循下面的规则（特别提醒，这里的自平衡和平衡二叉树AVL的高度平衡有别）：
- 每一个结点都有一个颜色，要么为红色，要么为黑色；
- 树的根结点为黑色；
- 树中不存在两个相邻的红色结点（即红色结点的父结点和孩子结点均不能是红色）；
- 从任意一个结点（包括根结点）到其任何后代 NULL 结点（默认是黑色的）的每条路径都具有相同数量的黑色结点。
为什么要有红黑树？
大多数二叉排序树BST的操作（查找、最大值、最小值、插入、删除等等）都是O(h)的时间复杂度，h 为树的高度。但是对于斜树而言（BST极端情况下出现），BST的这些操作的时间复杂度将达到 O(n)。为了保证BST的所有操作的时间复杂度的上限为O(logn)，就要想办法把一颗BST树的高度一直维持在logn，而红黑树就做到了这一点，红黑树的高度始终都维持在log(n)，n 为树中的顶点数目。
