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

百家 作者:程序员的那些事 2022-02-25 15:32:50

推荐关注↓

【导读】本文介绍了使用 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([]int0)
    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. 综合增删改查所有操作,红黑树的统计性能更优


zhuanlan.zhihu.com/p/368944960


- EOF -

推荐阅读  点击标题可跳转

1、元宇宙不是 PPT,已经发展到这个地步了!

2、“阿里味” PUA 编程语言火上 GitHub 热榜

3、一些著名的软件都用什么语言编写?


关注「程序员的那些事」加星标,不错过圈内事

点赞和在看就是最大的支持❤️

关注公众号:拾黑(shiheibook)了解更多

[广告]赞助链接:

四季很好,只要有你,文娱排行榜:https://www.yaopaiming.com/
让资讯触达的更精准有趣:https://www.0xu.cn/

公众号 关注网络尖刀微信公众号
随时掌握互联网精彩
赞助链接