目录
红黑树原理详解及golang实现
在看红黑树原理之前，先看下二叉查找树。
二叉查找树
二叉查找树，又称二叉排序树，二叉搜索树。
性质
它具备一下性质：
1、左子树上的所有节点均小于它的根节点值。
2、右子树上的所有节点的值均大于等于它根节点的值。
3、左佑子树也分别二叉排序树。
4、没有键值相等的节点。
既然叫搜索树，那这种结构的好处当然也就是搜索咯，
假如我们要查找15
1、从root节点开始，15<50，找左子树。
2、15<20，找左子树，
3、15>10，找右子树，这样便找到15了。
插入也是类似方法，一层一层比较大小，找到合适的位置插入。
时间复杂度
看见它查找的次数等同于树的高度，在最好的情况下，其平均查找次数和log 2 (n)成正比。
当然也有坏情况，当先后插入的关键字有序时，构成的二叉排序树蜕变为单支树，树的深度和其节点数成正比(和顺序查找相同）.
例如依序插入 ： 100、200、90、80、70、60、50、40
就会成为如下图形态：
为了解决这种不平衡的情形，就有了红黑树。
红黑树
性质
红黑树是一种自平衡的二叉搜索树，它包含了二叉搜索树的特性，同时具备以下性质：
1、所有节点的颜色不是红色就是黑色。
2、根节点是黑丝。
3、每个叶子节点都是黑色的空节点(nil)。
4、每个红色节点的两个子节点都是黑色。(从每个叶子到根节点的所有路径上不能有两个连续的红色节点)
5、从任一节点到其叶子节点的所有路径上都包含相同数目的黑节点。
前四都能理解其意思吧，所以只解释下第五点，比如60这个节点，到其所有叶子节点的路径都只包含1个黑色节点：40和90。
operation
红黑树为了维持它的这5点性质，于是它支持了这么几个操作 ，
变色 ： 顾名思义变色，红变黑，黑变红。
左旋转 : 这里借用百度百科两张旋转图，以图中红色节点为中心，中心节点为右孩子替代，而自己成为它的左孩子，同时节点b作为pivot的有孩子(至于为什么是右孩子，b原本就在pivot的右子树上，所以肯定大于pivot)。
右选装 : 同左旋转，中心点顺时钟旋转，成为其原来左孩子的右孩子，原来左孩子的右孩子则成为原中心点的左孩子。
接着看看红黑树的插入，看看它是如何通过这几个op维持红黑树这5个性质的。
红黑树的插入
关于插入的特点 ： 由于性质5的约束，每次插入的节点颜色必然为红色。
插入的化存在几种情形，复杂的树可能会涉及到循环的向树上检索做自平衡，这里先从一颗空树开始先简单理解下这些情形。
情形1：空树
直接插入，直接作为根节点，同时由于性质1的约束，通过变色op变为黑色即可。
情形2：插入节点父节为黑色，
不违反任何性质，无需做任何修改。
情形3 插入节点的父节点为红色，父节点为父父节点的左孩子，父父节点的右孩子为黑色，插入节点为左孩子(或者父节点为父父节点的右孩子，父父节点的左孩子为黑色，插入节点为右孩子)。
这是一种插入节点和父节点在一个方向上的情况(例如父节点为左孩子，插入节点也为左孩子)和情形5相反
父节点 及 父父节点变色，在进行左/右旋转， 具体做还是右看你插入的节点的父节点是左子树还是右子树，图例为左子树。
此处 : 变色 - > 右旋转
情形4 插入节点父节点为红色，父父节点的左/右孩子为红色
先将父节点和父父节点右孩子变黑，父父节点变红，然后将父节点当做插入节点一样递归向上进行平衡红黑树性质操作。 若父节点为根节点直接变父节点为黑色即可.
此处 : 变色 -> 变色
情形5 插入节点的父节点为红色，父节点为父父节点的左孩子，父父节点的右孩子为黑色，插入节点为右孩子(或者父节点为父父节点的右孩子，父父节点的左孩子为黑色，插入节点为左孩子)。
和情形3类比是一种反向情况，这种情况进行两次旋转，
先左/右旋转，旋转后变成了情形3，接着按情形3变换即可。
此处 ：左旋转 -> 变色 -> 右旋转
golang实现
类型定义
需要注意的是 红黑树的NIL节点需要单独定义出来，不能直接用nil哦。
const (
RED = true
BLACK = false
)
type Node struct {
Parent *Node
Left *Node
Right *Node
color bool
Item
}
type Rbtree struct {
NIL *Node
root *Node
count uint64
}
func New() *Rbtree{
node := Node{nil, nil, nil, BLACK, nil}
return &Rbtree{
NIL : &node,
root : &node,
count : 0,
}
}leftRotate
// Left Rotate
func (rbt *Rbtree) LeftRotate(no *Node) {
// Since we are doing the left rotation, the right child should *NOT* nil.
if no.Right == nil {
return
}
// | |
// X Y
// / \ left rotate / \
// α Y -------------> X γ
// / \ / \
// β γ α β
rchild := no.Right
no.Right = rchild.Left
if rchild.Left != nil {
rchild.Left.Parent = no
}
rchild.Parent = no.Parent
if no.Parent == nil {
rbt.root = rchild
} else if no == no.Parent.Left {
no.Parent.Left = rchild
} else {
no.Parent.Right = rchild
}
rchild.Left = no
no.Parent = rchild
}
func LeftRotateTest(){
var i10 Int = 10
var i12 Int = 12
rbtree := New()
x := &Node{rbtree.NIL, rbtree.NIL, rbtree.NIL, BLACK, i10}
rbtree.root = x
y := &Node{rbtree.root.Right, rbtree.NIL, rbtree.NIL, RED, i12}
rbtree.root.Right = y
log.Println("root : ", rbtree.root)
log.Println("left : ", rbtree.root.Left)
log.Println("right : ", rbtree.root.Right)
rbtree.LeftRotate(rbtree.root)
log.Println("root : ", rbtree.root)
log.Println("left : ", rbtree