什么是红黑树

为什么要有红黑树

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

 

 

从2-3树来看红黑树

一般我们接触最多的是二叉树，也就是一个父节点最多有两个子节点。2-3树与二叉树的不同之处在于，一个父节点可以有两个子节点，也可以有三个子节点，并且其也满足类似二叉搜索树的性质。还有最重要的，2-3树的所有叶子节点都在同一层，且最后一层不能有空节点，类似于满二叉树。
我们依次插入10，9，8，7，6，5，4，3，2，1来看一下2-3数是如何进行自平衡的。
2-3树在插入元素之前首先要进行一次未命中的查找，然后将元素插入叶子节点中，之后再进行平衡操作，下面具体说明。
首先插入10，如下图

 

 

 

 

 

 

 

 

 

 

再看红黑树

那么红黑树与2-3树有什么关系呢？现在我们对2-3树进行改造，改造成一个二叉树。怎么改造呢？对于2节点，保持不变；对于3节点，我们首先将3节点中左侧的元素标记为红色，如下图2所示。