------------------------------------------------------读《算法》后感

一直以来，对于红黑树都没有很好的理解，指导看了《算法》和上了coursera上的公开课，终于算是有了较好的理解，现写下来和大家分享

前言：2-3查找树         

      虽然二叉搜索树已经很好的解决大多数搜索问题，但是在最坏的情况下的性能还是很差 （~N）,为了保证查找的树的平衡。我们引入了3-结点（相较于二叉查找树中的2-结点），并据此构造出2-3查找树。其性质如下：

Allow 1 or 2 keys per node.

      2-nodes: one key, two children.

      3-nodes: two keys, three children.

Symmetric order. Inorder traversal yields keys in ascending order.

Perfect balance. Every path from root to null link has same length.

 至于对于2-3树的查找，插入的查找都比较简单，可参考下面的图片

图片引用自：http://algs4.cs.princeton.edu

红黑二叉查找树                                      

红黑二叉查找树的基本思想就是用标准的二叉查找树（完全由2-结点构成）和一些额外的信息（替换3-结点）来表示2-3树

.1 替换3-结点

红黑树的一种等价定义：

  . 红链接均为左链接

  . 没有任何一个结点同时和两条红链相连

  . 该树是完全黑色平衡的，即任意空连接到根结点的路径上的黑链接数量相同

.2颜色表示

.3 旋转

    ..左旋转h的右链接

..右旋转h的左链接

..颜色转换：讲一个结点的两个红色子节点的颜色转换，同时将父节点的颜色由黑色转换成红色

平衡搜索树