红黑树

为什么要有红黑树
想必大家对二叉树搜索树都不陌生，首先看一下二叉搜索树的定义：
二叉搜索树（Binary Search Tree），或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
从理论上来说，二叉搜索树的查询、插入和删除一个节点的时间复杂度均为O（log(n)）,已经完全可以满足我们的要求了，那么为什么还要有红黑树呢？
我们来看一个例子，向二叉搜索树中依次插入（1，2，3，4，5，6），插入之后是这样的

可以看到，在这种情况下，二叉搜索树退化成了链表！！！这时候查询、插入和删除一个元素的时候，时间复杂度变成了O（n），显然这是不能接受的。出现这种情况情况的原因是二叉搜索树没有自平衡的机制，所以就有了平衡二叉树的概念。
平衡二叉树（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
还是刚刚的例子，假如我们用平衡二叉树来实现的话，插入完元素后应该是下面这样的（不唯一）

平衡二叉树保证了在最差的情况下，二叉树依然能够保持绝对的平衡，即左右两个子树的高度差的绝对值不超过1。但是这又会带来一个问题，那就是平衡二叉树的定义过于严格，导致每次插入或者删除一个元素之后，都要去维护二叉树整体的平衡，这样产生额外的代价又太大了。二叉搜索树可能退化成链表，而平衡二叉树维护平衡的代价开销又太大了，那怎么办呢？这就要谈到“中庸之道”的智慧了。说白了就是把平衡的定义适当放宽，不那么严格，这样二叉树既不会退化成链表，维护平衡的开销也可以接受。没错，这就是我们要谈的红黑树了。

首先看一下红黑树的定义：
红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须除了满足二叉搜索树的性质外，还要满足下面的性质：
性质1：每个节点要么是黑色，要么是红色。
性质2：根节点是黑色。
性质3：每个叶子节点（NIL）是黑色。
性质4：每个红色结点的两个子结点一定都是黑色。
性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
这就是红黑树的五条性质。我相信很多人都看到过，能背下来的也不在少数，但是真正理解为什么要这样定义的恐怕就不多了。下面就从2-3树的角度来谈谈红黑树的定义。