设为首页 加入收藏

TOP

红黑树原理详解及golang实现(一)
2019-06-02 18:07:52 】 浏览:63
Tags:原理 详解 golang 实现

红黑树原理详解及golang实现


在看红黑树原理之前,先看下二叉查找树。

二叉查找树

二叉查找树,又称二叉排序树,二叉搜索树。

性质

它具备一下性质:

1、左子树上的所有节点均小于它的根节点值。
2、右子树上的所有节点的值均大于等于它根节点的值。
3、左佑子树也分别二叉排序树。
4、没有键值相等的节点。

Alt text

既然叫搜索树,那这种结构的好处当然也就是搜索咯,
假如我们要查找15

1、从root节点开始,15<50,找左子树。
2、15<20,找左子树,
3、15>10,找右子树,这样便找到15了。

插入也是类似方法,一层一层比较大小,找到合适的位置插入。
在这里插入图片描述

时间复杂


看见它查找的次数等同于树的高度,在最好的情况下,其平均查找次数和log 2 (n)成正比。
当然也有坏情况,当先后插入的关键字有序时,构成的二叉排序树蜕变为单支树,树的深度和其节点数成正比(和顺序查找相同).
例如依序插入 : 100、200、90、80、70、60、50、40
就会成为如下图形态:
Alt text

为了解决这种不平衡的情形,就有了红黑树。

红黑树

性质

红黑树是一种自平衡的二叉搜索树,它包含了二叉搜索树的特性,同时具备以下性质:

1、所有节点的颜色不是红色就是黑色。
2、根节点是黑丝。
3、每个叶子节点都是黑色的空节点(nil)。
4、每个红色节点的两个子节点都是黑色。(从每个叶子到根节点的所有路径上不能有两个连续的红色节点)
5、从任一节点到其叶子节点的所有路径上都包含相同数目的黑节点。

Alt text

前四都能理解其意思吧,所以只解释下第五点,比如60这个节点,到其所有叶子节点的路径都只包含1个黑色节点:40和90。

Alt text

operation

红黑树为了维持它的这5点性质,于是它支持了这么几个操作 ,

变色 : 顾名思义变色,红变黑,黑变红。
左旋转 : 这里借用百度百科两张旋转图,以图中红色节点为中心,中心节点为右孩子替代,而自己成为它的左孩子,同时节点b作为pivot的有孩子(至于为什么是右孩子,b原本就在pivot的右子树上,所以肯定大于pivot)。
Alt text

右选装 : 同左旋转,中心点顺时钟旋转,成为其原来左孩子的右孩子,原来左孩子的右孩子则成为原中心点的左孩子。
Alt text

接着看看红黑树的插入,看看它是如何通过这几个op维持红黑树这5个性质的。

红黑树的插入

关于插入的特点 : 由于性质5的约束,每次插入的节点颜色必然为红色。

插入的化存在几种情形,复杂的树可能会涉及到循环的向树上检索做自平衡,这里先从一颗空树开始先简单理解下这些情形。

情形1:空树

直接插入,直接作为根节点,同时由于性质1的约束,通过变色op变为黑色即可。

Alt text

情形2:插入节点父节为黑色,

不违反任何性质,无需做任何修改。

Alt text

情形3 插入节点的父节点为红色,父节点为父父节点的左孩子,父父节点的右孩子为黑色,插入节点为左孩子(或者父节点为父父节点的右孩子,父父节点的左孩子为黑色,插入节点为右孩子)。

这是一种插入节点和父节点在一个方向上的情况(例如父节点为左孩子,插入节点也为左孩子)和情形5相反

父节点 及 父父节点变色,在进行左/右旋转, 具体做还是右看你插入的节点的父节点是左子树还是右子树,图例为左子树。

此处 : 变色 - > 右旋转

Alt text

情形4 插入节点父节点为红色,父父节点的左/右孩子为红色

先将父节点和父父节点右孩子变黑,父父节点变红,然后将父节点当做插入节点一样递归向上进行平衡红黑树性质操作。 若父节点为根节点直接变父节点为黑色即可.

此处 : 变色 -> 变色

Alt text

情形5 插入节点的父节点为红色,父节点为父父节点的左孩子,父父节点的右孩子为黑色,插入节点为右孩子(或者父节点为父父节点的右孩子,父父节点的左孩子为黑色,插入节点为左孩子)。

和情形3类比是一种反向情况,这种情况进行两次旋转,
先左/右旋转,旋转后变成了情形3,接着按情形3变换即可。

此处 :左旋转 -> 变色 -> 右旋转
Alt text

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
			
		  
编程开发网
首页 上一页 1 2 3 4 下一页 尾页 1/4/4
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇深度解密Go语言之unsafe 下一篇golang中,map作为函数参数是如何..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(217) }