红黑树是平衡二叉树吗

红黑树是平衡二叉树。红黑树在每个节点增加一个存储位表示节点的颜色,可以是红或黑。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制,红黑树确保没有一条路径会比其它路径长出两倍。因此,红黑树是平衡二叉树。

什么是红黑树?

红黑树(Red Black Tree)是一颗自平衡(self-balancing)的二叉排序树(BST),树上的每一个结点都遵循下面的规则(特别提醒,这里的自平衡和平衡二叉树AVL的高度平衡有别):

  1. 每一个结点都有一个颜色,要么为红色,要么为黑色;
  2. 树的根结点为黑色;
  3. 树中不存在两个相邻的红色结点(即红色结点的父结点和孩子结点均不能是红色);
  4. 从任意一个结点(包括根结点)到其任何后代 NULL 结点(默认是黑色的)的每条路径都具有相同数量的黑色结点。

为什么要有红黑树?

大多数二叉排序树BST的操作(查找、最大值、最小值、插入、删除等等)都是O(h)的时间复杂度,h 为树的高度。但是对于斜树而言(BST极端情况下出现),BST的这些操作的时间复杂度将达到 ​O(n)。为了保证BST的所有操作的时间复杂度的上限为O(logn),就要想办法把一颗BST树的高度一直维持在logn,而红黑树就做到了这一点,红黑树的高度始终都维持在log(n),n 为树中的顶点数目。