红黑树-转

java的HashSet,

mysql的索引底层都涉及用红黑树

之前只知道二叉查找树，现在学习一下红黑树

总结：

1、二叉排序树：

二叉搜索树（Binary Search Tree），或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。

缺点：向二叉搜索树中依次插入（1，2，3，4，5，6），插入之后是这样的；

红黑树-转

在这种情况下，二叉搜索树退化成了链表！！！这时候查询、插入和删除一个元素的时候，时间复杂度变成了O（n），显然这是不能接受的。出现这种情况情况的原因是二叉搜索树没有自平衡的机制，所以就有了平衡二叉树的概念。

2、平衡二叉树

平衡二叉树（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

但是这又会带来一个问题，那就是平衡二叉树的定义过于严格，导致每次插入或者删除一个元素之后，都要去维护二叉树整体的平衡，这样产生额外的代价又太大了。

3、从2-3树来看红黑树

特点：

(1)2-3树与二叉树的不同之处在于，一个父节点可以有两个子节点，也可以有三个子节点

(2)其也满足类似二叉搜索树的性质

(3)2-3树的所有叶子节点都在同一层，且最后一层不能有空节点，类似于满二叉树

(4)叶子可以包含一个或两个数据项

红黑树-转

红黑树-转 8,9 是根节点、也是叶子节点

红黑树-转

插入后6、7、8三个元素所在的叶子节点不再满足2-3树的定义，需要进行分裂，即抽出元素7融入父节点，6和8分裂为7的左右子节点

红黑树-转

4、红黑树

上面的2-3树转红黑树

红黑树-转

特点1：每个节点要么是黑色，要么是红色。

特点2：在2-3树中，根节点只能是2节点或者3节点，2节点与3节点在红黑树中的等价形式

红黑树-转

特点3：每个叶子节点（NIL）是黑色

特点4：每个红色结点的两个子结点一定都是黑色

特点5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点

2-3树是一颗绝对平衡的树，即2-3树中任意一个节点出发，到达叶子节点后所经过的节点数都是一样的

再看下红黑树维持平衡的三种操作，即变色、左旋、右旋怎么理解呢

变色

左旋：

右旋：

本文中提到的红黑树是一种特殊的红黑树——左倾红黑树，即红色节点都是父节点的左子树

只要满足红黑树的五条性质，就是红黑树，比如完全可以实现右倾红黑树等等