作者有话说
想要玩转红黑树，要对模仿的玩法有一定的了解。我们在玩魔方时只要我们按照规则来，无论你的过程和步骤如何复杂或者如何简单，最后能够使每个面只要一种颜色结算成功。（杠精请离开：以3*3魔方为例）。玩红黑树也是一样的,只要按照规则(左旋、右旋、变色)来无论你中间的过程如何，最后都能写出红黑树(每一个人的步骤顺序可能不一样，其实原理都一样)。
电脑画图太费劲了，下面有一些图我就纸上画，望理解。有好的画图工具推荐的可以评论或私信哦。
找了很久的红黑树代码，没找到完整的。。。无奈之后自己写一份红黑树代码==>全网c++红黑树最全代码
二叉查找树
说起红黑树,首先得知道它的上古老祖: 二叉搜索树
定义:就是一颗二叉树，他的左节点比父节点小，右节点比父节点大。他的高度决定查找效率。
二叉搜索树是排序好的，应该说所有的二叉搜索树以及变种都是排序好的。怎么说，它是排序好的呢？以下能说明:二叉搜索树是基于二分的思想过来的,目的就是为了加快查找的效率。二分之前普遍要做的就是先排序，不可能对一个没有顺序的序列进行二分。
我们再来看下二叉搜索树排序的规则:当我们在一颗二叉搜索树的外围建立起一个坐标系,会发现一个神奇的现象。
是不是,实际上就是在X坐标上排序的，然后进行的二分。包括我们所说的红黑树。
扩展:对于树的前序遍历、中序遍历、后序遍历的思考。无论是哪种便利，所有的访问顺序都一样只不过打印的时间不同而已。这个自己验证，哈。
常见操作
查找(红黑树通用):查找每一个节点我们从根节点开始查找
1.查找值比当前值大，则搜索右子树
2.查找值比当前值相等，则停止查找，返回当前节点
3.查找值比当前值小，则搜索左子树
插入:
要插入节点，必须先找到插入节点位置。依然是从根节点开始比较，小于根节点的话就和左子树比较，反之与右子树比较，直到左子树为空或者右子树为空，则插入到相应为空的位置。
查找最小值(红黑树通用):
沿着根节点的左子树一路查找，直到最后一个不为空的节点，该节点就是当前这个树的最大节点。
查找最大值(红黑树通用):
沿着根节点的右子树一路查找，直到最后一个不为空的节点，该节点就是当前这个树的最大节点。
查找前驱节点(红黑树通用):
小于当前节点的最大值
查找后继节点(红黑树通用):
大于当前节点的最小值
遍历(红黑树通用):
根据一定的顺序来访问整个树，常见的有前序遍历、中序遍历、后序遍历
删除:
本质上是找前驱节点或者后继节点来代替
有三种情况:
1.叶子节点直接删除
2.只有一个子节点的用子节点代替
3.有两个子节点的，需要找到代替节点(前驱节点或者后继节点)
至于为什么要找前驱节点或者后继节点，我们回到二叉搜索树的定义：就是一颗二叉树，他的左节点比父节点小，右节点比父节点大。通过前驱节点和后继节点可以保持性质不变，后面在红黑树删除时也是通过这样的方式，不同的是红黑树需要保证黑色平衡，所以需要调整。
BST问题延续
我们回过头来说下二叉查找树的一个特殊情况:倾斜的二叉查找树，这棵树的高度为N
当我们顺序插入一组元素时就会出现二叉树退化成链表的情况，当退化成链表查找效率就变成了O(n)。
这里扩展说下O(n),O(logN)的差别有多大，我们画个函数曲线:
换句话说，大O表示法表述的是随着N的变化关系。所以我们在考虑是时候，要根据数据规模要考虑，当数据很少很少，用链表反而更快。
回到BST,基于BST存在的问题，平衡二叉查找树产生了。平衡树的插入和删除的时候会通过旋转操作将高度保持在logN，其中两款具有代表性的平衡树分别是AVL树(高度平衡具有二叉搜索树的全部性质，而且左右子树高度差不超过1)和红黑树。
如何选择AVL树还是红黑树:
当查找操作很多，几乎没有插入和删除操作，选择AVL树比红黑树效率更高。
当插入和删除操作比较多，选择红黑树比较合适。(你可以理解为:红黑树是低配折中方案)
AVL树
本来不是特别想说AVL树，既然写到这里就顺带说下，探究下AVL树为了保持平衡的需要的代价。高度平衡具有二叉搜索树的全部性质，而且左右子树高度差不超过1
AVL树实现平衡
通过左旋和右旋(说明下:左旋和右旋后一定不能破坏二叉查找树的查找规则)
有了AVL树为什么还要红黑树呢?
AVL树由于实现比较复杂，而且插入和删除性能比较差，在实际环境下的应用不如红黑树(红黑树只保持黑色节点平衡)。
构建一个AVL树的图示
好像忘记提前说左旋、右旋操作了(很简单，代码也实现也简单)
左旋
怎么表示呢，怎么搞动图。我手画吧，写个例子
不晓得形象波？想象以下，有人沿着3-5-6这个线往下拉(想下定滑轮)，然5下去了，6上去了。此时5变成了6的子节点，6此时有3个子节点显然不符合二叉树，为了保持二叉查找树的基本性质，所以5.5变成5的右孩子最合适。
右旋
跟左旋相反，可以自己画图体会下。
2-3-4树
先说下，为什么要先写2-3-4树。因为2-3-4树的性质可以推导出红黑树的性质，听说红黑树是2-3-4树来了，不晓得是不是真的。反正方便我们理解红黑树是真的，当然要理解，总不能硬背吧，这样不方便根据实际情况进行优化，也容易忘记。
2-3-4树是四阶的B树(Balance Tree)，属于一种多路查找树，它的结构有以下限制。
1.所有叶子节点都拥有相同的高度(深度)
2.节点只能是2-节点，3-节点，4-节点之一
补充说明:
2-节点:其这个节点下面能挂载2个孩子
3-节点:其这个节点下面能挂载3个孩子
4-节点:其这个节点下面能挂载4个孩子
我们画图表示: 
3.元素始终保持排序顺序，整体上保持二叉树的性质，即父节点大于左子节点，小于右子节点；而且节点有多个元素时，每个元素必须大于它左子树的元素。(纠正上图的错误:2-节点、3-节点、4-节点是一个整体)
看一个完整的2-3-4树:
吐槽以下哈，写博客真正太不容易了。期待关注支持以下。。。。。
题外话:2-3-4树的查询操作像普通的二叉搜索树一样，非常简单，但是由于其结点元素数不确定，在一些编程语言中实现起来并不方便，实现一般使用它的等同-红黑树。一个2-3-4树可以对应多个红黑树，一个红黑树只能对应一个2-3-4树。
