二叉树、红黑树以及 Golang 实现红黑树

↓推荐关注↓

【导读】本文介绍了使用 go 实现红黑树。

二叉搜索树（二叉查找树）

二叉查找树也叫二叉搜索树，也叫二叉排序树，它具有以下特点：1. 如果左子树不为空，则左子树上的结点的值都小于根节点；2. 如果右子树不为空，则右子树上的结点的值都大于根节点；3. 子树同样也要遵循以上两点。

二叉树的遍历方式

二叉树的遍历方式：前序遍历、中序遍历、后序遍历和层序遍历（MySql）。

只要一棵树是二叉查找树，那么它的中序遍历（左根右输出）一定是有序的。比如看下边的一棵二叉树：

它的前序遍历（根左右）为：530468；
它的中序遍历（左根右）为：034568；
它的后序遍历（左右根）为：043865。

二叉搜索树有哪些应用？

既然是搜索树，那么它肯定就是用在查找上。我们来分析下它的查找时间复杂度：

先来看下面两颗二叉搜索树：

查找时间复杂度其实就是树的深度。

上图一的时间复杂度：O(n)时间复杂度，表示需要查找 n 次，即循环 n 遍，退化成链表的情况。

上图二的时间复杂度（类似二分查找）：logn，即 树的高度 => x= => logn。

那么为什么会出现退化成链表的情况（图一）呢？我们该怎么处理才不会变成链表呢（怎么解决）？

当插入的节点数值从小到大时，则就会出现二叉树退化成链表的情况，那么有另一种树可以解决这种情况，就是平衡二叉树（AVL树）。

AVL树是一种追求极致平衡的二叉搜索树，即将树调整到最优的情况，由于这种树结构比较苛刻、旋转也比较多，这里就不重点展开讲。

红黑树

红黑树的由来

今天需要重点讲的是红黑树。红黑树的底层数据结构其实就是二叉查找树，也就是说红黑树是一颗特殊的二叉查找树，也叫自平衡二叉查找树。

红黑树出现的目的就是上所讲到的，为了解决二叉树退化成链表的情况。

红黑树的演进过程

链表(暴力查处) -> 二叉树 -> 二叉查找树 -> 特殊的二叉查找树(自平衡的二叉查找树)

红黑色讲解

通过上面的例子以及两个图，我们发现二叉树的结构就决定了其搜索的效率及性能，那么我们需要怎么样才让二叉树达到优化的效果呢？

因此就有了红黑树了，我们看下图（红黑树）：

红黑树的性质：

1. 每个节点不是红色就是黑色（这里不一定要红色和黑色，只要知道这里的红色和黑色是什么意思即可）
2. 一定没有连在一起的红色节点
3. 根节点（第一个节点）是黑色 root
4. 每个红色节点的两个字节点都是黑色
5. 叶子结点都是黑色（上图中其实还有为null的叶子结点没有画出来），如下图所示：

根据以上性质或者说满足了以上性质的树，就可以达到近似平衡了。

怎么判断一个节点是否为根结点？

• 没有父节点
• 入度为0的节点

红黑树变换规则

要满足这些性质，需要对树做什么操作呢？

为了红黑可以满足这些性质，因此出现了旋转，那么红黑树有几种变换规则呢？

有三种变换规则：

• 变色：红变黑 黑变红
• 左旋转
• 右旋转

左旋转示例：

旋转和颜色变换规则：所有插入的点默认为红色； 1. 变颜色的情况：如果插入的节点的父节点和叔叔节点为红色，则：1）把父节点和叔叔节点设为黑色；2）把爷爷(祖父)节点设为红色；3）把指针定位到爷爷节点作为当前需要操作的节点，再根据变换规则来进行判断操作。2. 左旋：如果当前父节点是红色，叔叔节点是黑色，而且当前的节点是右子树时，则需要以父节点作为左旋转。3. 右旋：当前父节点是红色，叔叔节点是黑色，且当前的节点是左子树时，则：1）把父节点变为黑色；2）把爷爷节点变为红色；3）以父节点右旋转。

比如要往上图中插入数字6，则这颗红黑色的演变过程如下：

step1: 插入6节点后如下图，它的父节点和叔叔节点均是红色，则需要根据变换规则来操作，到step2了。

step2: 根据变换规则，需要将插入节点的父节点和叔叔节点均变为黑色，爷爷节点变为红色，然后将指针定位到爷爷节点(蓝色圈)。将指针定位到爷爷节点(12)后，此时做为当前需要操作的节点，再根据变换规则来判断，可以看到下图的当前节点(12)的叔叔节点是黑色的，则不能用变颜色规则的情况了，进行step3，此时需要进行左旋或右旋了。

step3: 根据上图情况可以知道此时是符合左旋规则的：当前节点(12)的父节点(5)是红色，叔叔节点(3)是黑色，而且当前的节点是右子树。接下来需要进行左旋变换(三步走)：

step4：左旋变换后，可以看到当前节点(5)的父节点(12)为红色，叔叔节点(30)为黑色，而且当前节点为左子树，符合右旋的规则。接下来就是进行右旋的变换操作了：1）把父节点(12)变为黑色；2）把爷爷节点(29)变为红色；3）以父节点(12)右旋转

小结

到这里，可以看到经过多次旋转后，这棵树是符合红黑色的性质。

Golang代码实现红黑树

直接上代码，如下：

package main

import (
    "fmt"
    "math/rand"
    "time"
)

const (
    RED bool = true
    BLACK bool = false
)

type Node struct {
    key int
    value interface{}

    left *Node
    right *Node
    //parent *Node

    color bool
}

type RedBlackTree struct {
    size int
    root *Node
}

func NewNode(key, val int) *Node {
    // 默认添加红节点
    return &Node{
        key:    key,
        value:  val,
        left:   nil,
        right:  nil,
        //parent: nil,
        color:  RED,
    }
}

func NewRedBlackTree() *RedBlackTree {
    return &RedBlackTree{}
}

func (n *Node) IsRed() bool {
    if n == nil {
        return BLACK
    }
    return n.color
}

func (tree *RedBlackTree) GetTreeSize() int {
    return tree.size
}

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

    retNode.left = n
    retNode.color = n.color
    n.color = RED

    return retNode
}

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

    retNode.right = n
    retNode.color = n.color
    n.color = RED

    return retNode
}

// 颜色变换
func (n *Node) flipColors() {
    n.color = RED
    n.left.color = BLACK
    n.right.color = BLACK
}

// 维护红黑树
func (n *Node) updateRedBlackTree(isAdd int) *Node {
    // isAdd=0 说明没有新节点，无需维护
    if isAdd == 0 {
        return n
    }

    // 需要维护
    if n.right.IsRed() == RED && n.left.IsRed() != RED {
        n = n.leftRotate()
    }

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

    // 判断是否为情形4，是需要颜色翻转
    if n.left.IsRed() == RED && n.right.IsRed() == RED {
        n.flipColors()
    }

    return n
}

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

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

    // 维护红黑树
    n = n.updateRedBlackTree(isAdd)

    return isAdd, n
}

func (tree *RedBlackTree) Add(key, val int)  {
    isAdd, nd := tree.root.add(key, val)
    tree.size += isAdd
    tree.root = nd
    tree.root.color = BLACK //根节点为黑色节点
}

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

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


// 测试红黑树代码
func main() {
    count := 10
    redBlackTree := NewRedBlackTree()
    nums := make([]int, 0)
    for i := 0; i < count; i++ {
        nums = append(nums, rand.Intn(count))
    }

    fmt.Println("source data: ", nums)
    now := time.Now()
    for _, v := range nums {
        redBlackTree.Add(v, v)
    }

    fmt.Println("redBlackTree:", now.Sub(time.Now()))
    redBlackTree.PrintPreOrder()
    fmt.Println("节点数量:", redBlackTree.GetTreeSize())
}

测试输出结果如下：

data source: [1 7 7 9 1 8 5 0 6 0]
redBlackTree: -2.136µ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. 综合增删改查所有操作，红黑树的统计性能更优