（24）Go实现红黑树-实现和总结

继上一篇《（23）Go实现红黑树-算法解析》的后续：
https://www.jianshu.com/p/8c41d1e52c32

红黑树的定义和实现
const (
    Red   = true
    Black = false
)

type node struct {
    key   int
    value int
    color bool
    left  *node
    right *node
}

type redBlackTree struct {
    size int
    root *node
}

func newNode(key, val int) *node {
    // 默认添加红节点
    return &node{key, val, Red, nil, nil}
}

func NewRedBlackTree() *redBlackTree {
    return new(redBlackTree)
}

func (nd *node) isRed() bool {
    if nd == nil {
        return Black
    }
    return nd.color
}

func (tree *redBlackTree) GetSize() int {
    return tree.size
}

// 向红黑树中添加元素
func (tree *redBlackTree) Add(key, val int) {
    isAdd, nd := tree.root.add(key, val)
    tree.size += isAdd
    tree.root = nd
    tree.root.color = Black //根节点为黑色节点
}

// 递归写法:向树的root节点中插入key,val
// 返回1,代表加了节点
// 返回0,代表没有添加新节点,只更新key对应的value值
func (nd *node) add(key, val int) (int, *node) {
    if nd == nil { // 默认插入红色节点
        return 1, newNode(key, val)
    }

    isAdd := 0
    if key < nd.key {
        isAdd, nd.left = nd.left.add(key, val)
    } else if key > nd.key {
        isAdd, nd.right = nd.right.add(key, val)
    } else { // nd.key == key
        // 对value值更新,节点数量不增加,isAdd = 0
        nd.value = val
    }

    // 维护红黑树
    nd = nd.updateRedBlackTree(isAdd)
    return isAdd, nd
}

// 红黑树维护
func (nd *node) updateRedBlackTree(isChange int) *node {
    // 0说明无新节点,不必维护
    if isChange == 0 {
        return nd
    }

    // 维护
    // 判断是否为情形2，是需要左旋转
    if nd.right.isRed() == Red && nd.left.isRed() != Red {
        nd = nd.leftRotate()
    }

    // 判断是否为情形3，是需要右旋转
    if nd.left.isRed() == Red && nd.left.left.isRed() == Red {
        nd = nd.rightRotate()
    }

    // 判断是否为情形4，是需要颜色翻转
    if nd.left.isRed() == Red && nd.right.isRed() == Red {
        nd.flipColors()
    }
    return nd
}

//    nd                      x
//  /   \     左旋转         /  \
// T1   x   --------->   node   T3
//     / \              /   \
//    T2 T3            T1   T2
func (nd *node) leftRotate() *node {
    // 左旋转
    retNode := nd.right
    nd.right = retNode.left

    retNode.left = nd
    retNode.color = nd.color
    nd.color = Red

    return retNode
}

//      nd                    x
//    /   \     右旋转       /  \
//   x    T2   ------->   y   node
//  / \                       /  \
// y  T1                     T1  T2
func (nd *node) rightRotate() *node {
        //右旋转
    retNode := nd.left
    nd.left = retNode.right
    retNode.right = nd

    retNode.color = nd.color
    nd.color = Red

    return retNode
}

// 颜色翻转
func (nd *node) flipColors() {
    nd.color = Red
    nd.left.color = Black
    nd.right.color = Black
}

// 前序遍历打印出key,val,color
func (tree *redBlackTree) PrintPreOrder() {
    resp := [][]interface{}{}
    tree.root.printPreOrder(&resp)
    fmt.Println(resp)
}

func (nd *node) printPreOrder(resp *[][]interface{}) {
    if nd == nil {
        return
    }
    *resp = append(*resp, []interface{}{nd.key, nd.value, nd.color})
    nd.left.printPreOrder(resp)
    nd.right.printPreOrder(resp)
}

测试代码
func main() {
    const count = 10
    redBlackTree := redblacktree1.NewRedBlackTree()
    nums := []int{}
    for i := 0; i < count; i++ {
        nums = append(nums, rand.Intn(count))
    }
    fmt.Println("数据源:", nums)
    t := time.Now()
    for _, v := range nums {
        redBlackTree.Add(v, v)
    }
    fmt.Println("redBlackTree:", t.Sub(time.Now()))
    redBlackTree.PrintPreOrder()
    fmt.Println("节点数量:", redBlackTree.GetSize())
}

测试结果
数据源: [1 7 7 9 1 8 5 0 6 0]
redBlackTree: -3.294µs
[[7 7 false] [1 1 true] [0 0 false] [6 6 false] [5 5 true] [9 9 false] [8 8 true]]
节点数量: 7

红黑树是保持“黑平衡”的二叉树，严格意义上讲红黑树不是平衡二叉树，他的最大高度为2*logn

二分搜索树，AVL树，红黑树对比：
1）对于完全随机的数据源，普通二分搜索树很好用，缺陷是在极端情况下容易退化成链表
2）对于查询较多的使用情况，AVL树很好用，因为他的高度一直保持h=logn
3）红黑树牺牲了平衡性，即h=2*logn，但在添加和删除操作中，红黑树比AVL树有优势
4）综合增删改查所有操作，红黑树的统计性能更优

红黑树和go自带map性能对比
const count = 1000000
    redBlackTree := redblacktree1.NewRedBlackTree()
    nums := []int{}
    for i := 0; i < count; i++ {
        nums = append(nums, rand.Intn(count))
    }

    t := time.Now()
    for _, v := range nums {
        redBlackTree.Add(v, v)
    }
    fmt.Println("redBlackTree:", t.Sub(time.Now()))
    m := map[int]int{}
    t = time.Now()
    for _, v := range nums {
        m[v] = v
    }
    fmt.Println("map:", t.Sub(time.Now()))

测试结果//
redBlackTree: -2.859348172s
map: -673.106001ms

map在速度上还是很大优势，劣势就是无法顺序遍历。
一种数据结构在某方面性能更优，往往是因为他多维护或少维护了某些东西，
如哈希表和红黑树对比，哈希表牺牲了顺序，赢得了速度，而红黑树赢了顺序，输了速度。
不存在说一定要使用某种数据结构，要具体问题具体分析。

有bug欢迎支持，转载请注明出处。