红黑树原理详解及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.root.left)
    log.println("right : ", rbtree.root.right)

}

rightrotate

// right rotate
func (rbt *rbtree) rightrotate(no *node) {
    if no.left == nil {
        return
    }

    //          |                                  |
    //          x                                  y
    //         / \         right rotate           / \
    //        y   γ      ------------->         α  x
    //       / \                                    / \
    //      α  β                                    β  γ

    lchild := no.left
    no.left = lchild.right

    if lchild.right != nil {
        lchild.right.parent = no
    }

    lchild.parent = no.parent

    if no.parent == nil {
        rbt.root = lchild
    } else if no == no.parent.left {
        no.parent.left = lchild
    } else {
        no.parent.right = lchild
    }

    lchild.right = no

    no.parent = lchild

}

func rightrotatetest(){
    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.rightrotate(rbtree.root)
    
    log.println("root : ", rbtree.root)
    log.println("left : ", rbtree.root.left)
    log.println("right : ", rbtree.root.right)

}

item interface

值类型接口

type item interface {
    less(than item) bool
}

type int int

func (x int) less(than item) bool {
    log.println(x, " ", than.(int))
    return x < than.(int)
}

type uint32 uint32

func (x uint32) less(than item) bool {
    log.println(x, " ", than.(uint32))
    return x < than.(uint32)
}

type string string

func (x string) less(than item) bool {
    log.println(x, " ", than.(string))
    return x < than.(string)
}

func itemtest(){
    var itype1 int = 10
    var itype2 int = 12

    log.println(itype1.less(itype2))


    var strtype1 string = "sola"
    var strtype2 string = "ailumiyana"

    log.println(strtype1.less(strtype2))
}

insert

func (rbt *rbtree) insert(no *node) {
    x := rbt.root
    var y *node = rbt.nil

    for x != rbt.nil {
        y = x 
        if less(no.item, x.item) {
            x = x.left
        } else if less(x.item, no.item) {
            x = x.right
        } else {
            log.println("that node already exist")
        }
    }

    no.parent = y
    if y == rbt.nil {
        rbt.root = no
    } else if less(no.item, y.item) {
        y.left = no
    } else {
        y.right = no
    }

    rbt.count++
    rbt.insertfixup(no)

}

func (rbt *rbtree) insertfixup(no *node) {
    for no.parent.color == red {
        if no.parent == no.parent.parent.left {
            y := no.parent.parent.right
            if y.color == red {
                //
                // 情形 4

                log.println("trace do case 4 :", no.item)

                no.parent.color = black
                y.color = black
                no.parent.parent.color = red
                no = no.parent.parent  //循环向上自平衡.
            } else {
                if no == no.parent.right {
                    //
                    // 情形 5 : 反向情形
                    // 直接左旋转 , 然后进行情形3(变色->右旋)
                    log.println("trace do case 5 :", no.item)

                    if no == no.parent.right {
                        no = no.parent
                        rbt.leftrotate(no)
                    }
                }
                log.println("trace do case 6 :", no.item)

                no.parent.color = black
                no.parent.parent.color = red
                rbt.rightrotate(no.parent.parent)
            }
        } else { //为父父节点右孩子情形，和左孩子一样，改下转向而已.
            y := no.parent.parent.left
            if y.color == red {
                no.parent.color = black
                y.color = black
                no.parent.parent.color = red
                no = no.parent.parent
            } else {
                if no == no.parent.left {
                    no = no.parent
                    rbt.rightrotate(no)
                }
                
                no.parent.color = black
                no.parent.parent.color = red
                rbt.leftrotate(no.parent.parent)
            }
        }
    }
    rbt.root.color = black
}

func inserttest(){
    rbtree := new()

    rbtree.insert(&node{rbtree.nil, rbtree.nil, rbtree.nil, red, int(10)})
    rbtree.insert(&node{rbtree.nil, rbtree.nil, rbtree.nil, red, int(9)})
    rbtree.insert(&node{rbtree.nil, rbtree.nil, rbtree.nil, red, int(8)})
    rbtree.insert(&node{rbtree.nil, rbtree.nil, rbtree.nil, red, int(6)})
    rbtree.insert(&node{rbtree.nil, rbtree.nil, rbtree.nil, red, int(7)})

    log.println("rbtree counts : ", rbtree.count)

    log.println("------ ", rbtree.root.item)
    log.println("----", rbtree.root.left.item, "---", rbtree.root.right.item)
    log.println("--", rbtree.root.left.left.item, "-", rbtree.root.left.right.item)

}

inserttest() 仔细瞧瞧这就是我们 讲情形那棵树 哈 。

完整代码

package main

import(
    "log"
)

const (
    red = true
    black = false
)

//-----------------------------------
//item interface
//
type item interface {
    less(than item) bool
}

type int int

func (x int) less(than item) bool {
    log.println(x, " ", than.(int))
    return x < than.(int)
}

type uint32 uint32

func (x uint32) less(than item) bool {
    log.println(x, " ", than.(uint32))
    return x < than.(uint32)
}

type string string

func (x string) less(than item) bool {
    log.println(x, " ", than.(string))
    return x < than.(string)
}

//-----------------------------------

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,
    }
}

func less(x, y item) bool {
    return x.less(y)
}

// left rotate
func (rbt *rbtree) leftrotate(no *node) {
    // since we are doing the left rotation, the right child should *not* nil.
    if no.right == rbt.nil {
        return
    }

    //          |                                  |
    //          x                                  y
    //         / \         left rotate            / \
    //        α  y       ------------->         x   γ
    //           / \                            / \
    //          β  γ                            α  β

    rchild := no.right
    no.right = rchild.left

    if rchild.left != rbt.nil {
        rchild.left.parent = no
    }

    rchild.parent = no.parent

    if no.parent == rbt.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

}

// right rotate
func (rbt *rbtree) rightrotate(no *node) {
    if no.left == rbt.nil {
        return
    }

    //          |                                  |
    //          x                                  y
    //         / \         right rotate           / \
    //        y   γ      ------------->         α  x
    //       / \                                    / \
    //      α  β                                    β  γ

    lchild := no.left
    no.left = lchild.right

    if lchild.right != rbt.nil {
        lchild.right.parent = no
    }

    lchild.parent = no.parent

    if no.parent == rbt.nil {
        rbt.root = lchild
    } else if no == no.parent.left {
        no.parent.left = lchild
    } else {
        no.parent.right = lchild
    }

    lchild.right = no

    no.parent = lchild

}

func (rbt *rbtree) insert(no *node) {
    x := rbt.root
    var y *node = rbt.nil

    for x != rbt.nil {
        y = x 
        if less(no.item, x.item) {
            x = x.left
        } else if less(x.item, no.item) {
            x = x.right
        } else {
            log.println("that node already exist")
        }
    }

    no.parent = y
    if y == rbt.nil {
        rbt.root = no
    } else if less(no.item, y.item) {
        y.left = no
    } else {
        y.right = no
    }

    rbt.count++
    rbt.insertfixup(no)

}

func (rbt *rbtree) insertfixup(no *node) {
    for no.parent.color == red {
        if no.parent == no.parent.parent.left {
            y := no.parent.parent.right
            if y.color == red {
                //
                // 情形 4

                log.println("trace do case 4 :", no.item)

                no.parent.color = black
                y.color = black
                no.parent.parent.color = red
                no = no.parent.parent  //循环向上自平衡.
            } else {
                if no == no.parent.right {
                    //
                    // 情形 5 : 反向情形
                    // 直接左旋转 , 然后进行情形3(变色->右旋)
                    log.println("trace do case 5 :", no.item)

                    if no == no.parent.right {
                        no = no.parent
                        rbt.leftrotate(no)
                    }
                }
                log.println("trace do case 6 :", no.item)

                no.parent.color = black
                no.parent.parent.color = red
                rbt.rightrotate(no.parent.parent)
            }
        } else { //为父父节点右孩子情形，和左孩子一样，改下转向而已.
            y := no.parent.parent.left
            if y.color == red {
                no.parent.color = black
                y.color = black
                no.parent.parent.color = red
                no = no.parent.parent
            } else {
                if no == no.parent.left {
                    no = no.parent
                    rbt.rightrotate(no)
                }
                
                no.parent.color = black
                no.parent.parent.color = red
                rbt.leftrotate(no.parent.parent)
            }
        }
    }
    rbt.root.color = black
}

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.root.left)
    log.println("right : ", rbtree.root.right)

}

func rightrotatetest(){
    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.left = y

    log.println("root : ", rbtree.root)
    log.println("left : ", rbtree.root.left)
    log.println("right : ", rbtree.root.right)

    rbtree.rightrotate(rbtree.root)
    
    log.println("root : ", rbtree.root)
    log.println("left : ", rbtree.root.left)
    log.println("right : ", rbtree.root.right)

}

func itemtest(){
    var itype1 int = 10
    var itype2 int = 12

    log.println(itype1.less(itype2))


    var strtype1 string = "sola"
    var strtype2 string = "ailumiyana"

    log.println(strtype1.less(strtype2))
}

func inserttest(){
    rbtree := new()

    rbtree.insert(&node{rbtree.nil, rbtree.nil, rbtree.nil, red, int(10)})
    rbtree.insert(&node{rbtree.nil, rbtree.nil, rbtree.nil, red, int(9)})
    rbtree.insert(&node{rbtree.nil, rbtree.nil, rbtree.nil, red, int(8)})
    rbtree.insert(&node{rbtree.nil, rbtree.nil, rbtree.nil, red, int(6)})
    rbtree.insert(&node{rbtree.nil, rbtree.nil, rbtree.nil, red, int(7)})

    log.println("rbtree counts : ", rbtree.count)

    log.println("------ ", rbtree.root.item)
    log.println("----", rbtree.root.left.item, "---", rbtree.root.right.item)
    log.println("--", rbtree.root.left.left.item, "-", rbtree.root.left.right.item)

}


func main()  {
    log.println(" ---- main ------ ")
    leftrotatetest()
    rightrotatetest()
    itemtest()
    inserttest()
}

小结

好了本文 对红黑树的讲解到此结束，刚开始看红黑树的时候这些性质确实特别绕，但是理解了这5点性质，就好多了。 然后就是两个操作 ： 变色和旋转 理解红黑树是通过他们进行自平衡的就行了。
由于时间原因只写了插入了 ，没做删除，有机会再补上吧，不过理解了插入原理，删除也不在话下了吧。

如对本文有疑问， 点击进行留言回复！！