当前位置: 开发笔记 > 编程语言 > 正文

红黑树原理详解及golang实现

作者：小七 | 来源：互联网 | 2023-05-18 21:48

目录红黑树原理详解及golang实现二叉查找树性质红黑树

红黑树原理详解及golang实现
- 二叉查找树
  - 性质
- 红黑树
  - 性质
  - operation
  - 红黑树的插入
- golang实现
  - 类型定义
  - leftRotate
  - RightRotate
  - Item Interface
  - insert
  - 完整代码
- 小结

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

}

Alt text

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)

}

Alt text

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

 
 
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          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点性质，就好多了。 然后就是两个操作 ： 变色和旋转 理解红黑树是通过他们进行自平衡的就行了。
 由于时间原因只写了插入了 ，没做删除，有机会再补上吧，不过理解了插入原理，删除也不在话下了吧。




    
        
                        golang
                        go
                        io
                        int
                        insert
                        搜索
                        深度
                        百度
                        const
                    
    



    
        写下你的评论吧 !
        
            
                吐个槽吧,看都看了
            
            
                
                                        会员登录 | 用户注册
                                    
                
            
        

        
    

    
        推荐阅读
        
            
                                
                    
                        get
                        go利用(*interface{})(nil)传递参数类型的原理及应用
                    

                    
                                                
                        本文介绍了在go语言中利用(*interface{})(nil)传递参数类型的原理及应用。通过分析Martini框架中的injector类型的声明，解释了values映射表的作用以及parent Injector的含义。同时，讨论了该技术在实际开发中的应用场景。 ...
                        [详细]
                    
                    

                    
                        蜡笔小新   2023-12-10 11:37:12
                    

                

                
                                
                    
                        int
                        Java中vector的使用详解
                    

                    
                                                
                        本文详细介绍了Java中vector的使用方法和相关知识，包括vector类的功能、构造方法和使用注意事项。通过使用vector类，可以方便地实现动态数组的功能，并且可以随意插入不同类型的对象，进行查找、插入和删除操作。这篇文章对于需要频繁进行查找、插入和删除操作的情况下，使用vector类是一个很好的选择。 ...
                        [详细]
                    
                    

                    
                        蜡笔小新   2023-12-13 14:14:39
                    

                

                                
                    
                    
                
                
                                
                    
                        eval
                        也就是|小窗_卷积的特征提取与参数计算
                    

                    
                                                
                            
                        
                                                
                        篇首语：本文由编程笔记#小编为大家整理，主要介绍了卷积的特征提取与参数计算相关的知识，希望对你有一定的参考价值。Dense和Conv2D根本区别在于，Den ...
                        [详细]
                    
                    

                    
                        蜡笔小新   2023-12-13 12:59:48
                    

                

                
                                
                    
                        format
                        Go GUIlxn/walk 学习3.菜单栏和工具栏的具体实现
                    

                    
                                                
                            
                        
                                                
                        本文介绍了使用Go语言的GUI库lxn/walk实现菜单栏和工具栏的具体方法，包括消息窗口的产生、文件放置动作响应和提示框的应用。部分代码来自上一篇博客和lxn/walk官方示例。文章提供了学习GUI开发的实际案例和代码示例。 ...
                        [详细]
                    
                    

                    
                        蜡笔小新   2023-12-12 20:56:55
                    

                

                
                                
                    
                        int
                        十大经典排序算法动图演示+Python实现
                    

                    
                                                
                            
                        
                                                
                        本文介绍了十大经典排序算法的原理、演示和Python实现。排序算法分为内部排序和外部排序，常见的内部排序算法有插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。文章还解释了时间复杂度和稳定性的概念，并提供了相关的名词解释。 ...
                        [详细]
                    
                    

                    
                        蜡笔小新   2023-12-10 19:28:59
                    

                

                
                                
                    
                        get
                        是否可以创建一个struct实例数组？ - Is it possible to create an array of struct instances?
                    

                    
                                                
                        Iamtryingtocreateanarrayofstructinstanceslikethis:我试图创建一个这样的struct实例数组：letinstallers: ...
                        [详细]
                    
                    

                    
                        蜡笔小新   2023-12-10 15:09:37
                    

                

                
                                
                    
                        int
                        深入解析Linux下的I/O多路转接epoll技术
                    

                    
                                                
                            
                        
                                                
                        本文深入解析了Linux下的I/O多路转接epoll技术，介绍了select和poll函数的问题，以及epoll函数的设计和优点。同时讲解了epoll函数的使用方法，包括epoll_create和epoll_ctl两个系统调用。 ...
                        [详细]
                    
                    

                    
                        蜡笔小新   2023-12-10 14:18:30
                    

                

                
                                
                    
                        int
                        机器学习之贝叶斯垃圾邮件分类代码
                    

                    
                                                
                        本文介绍了贝叶斯垃圾邮件分类的机器学习代码，代码来源于https://www.cnblogs.com/huangyc/p/10327209.html，并对代码进行了简介。朴素贝叶斯分类器训练函数包括求p(Ci)和基于词汇表的p(w|Ci)。 ...
                        [详细]
                    
                    

                    
                        蜡笔小新   2023-12-10 12:24:15
                    

                

                
                                
                    
                        int
                        微软头条实习生分享深度学习自学指南
                    

                    
                                                
                            
                        
                                                
                        本文介绍了一位微软头条实习生自学深度学习的经验分享，包括学习资源推荐、重要基础知识的学习要点等。作者强调了学好Python和数学基础的重要性，并提供了一些建议。 ...
                        [详细]
                    
                    

                    
                        蜡笔小新   2023-12-14 20:58:32
                    

                

                
                                
                    
                        get
                        JDK源码学习之HashTable(附带面试题)的学习笔记
                    

                    
                                                
                            
                        
                                                
                        本文介绍了JDK源码学习之HashTable(附带面试题)的学习笔记，包括HashTable的定义、数据类型、与HashMap的关系和区别。文章提供了干货，并附带了其他相关主题的学习笔记。 ...
                        [详细]
                    
                    

                    
                        蜡笔小新   2023-12-12 13:05:17
                    

                

                
                                
                    
                        get
                        文件压缩解压的哈夫曼树实现
                    

                    
                                                
                        本文介绍了使用哈夫曼树实现文件压缩和解压的方法。首先对数据结构课程设计中的代码进行了分析，包括使用时间调用、常量定义和统计文件中各个字符时相关的结构体。然后讨论了哈夫曼树的实现原理和算法。最后介绍了文件压缩和解压的具体步骤，包括字符统计、构建哈夫曼树、生成编码表、编码和解码过程。通过实例演示了文件压缩和解压的效果。本文的内容对于理解哈夫曼树的实现原理和应用具有一定的参考价值。 ...
                        [详细]
                    
                    

                    
                        蜡笔小新   2023-12-11 14:13:46
                    

                

                
                                
                    
                        get
                        android studio生成jks,android studio生成 keystore 以及获取 SHA1值等
                    

                    
                                                
                        合并列值－合并为一列问题需求：createtabletab(Aint,Bint,Cint)inserttabselect1,2,3unionallsel ...
                        [详细]
                    
                    

                    
                        蜡笔小新   2023-12-11 12:32:55
                    

                

                
                                
                    
                        int
                        Codeforces Round #321 (Div. 2) Kefa and Dishes 状压+spfa
                    

                    
                                                
                        本文介绍了Codeforces Round #321 (Div. 2)比赛中的问题Kefa and Dishes，通过状压和spfa算法解决了这个问题。给定一个有向图，求在不超过m步的情况下，能获得的最大权值和。点不能重复走。文章详细介绍了问题的题意、解题思路和代码实现。 ...
                        [详细]
                    
                    

                    
                        蜡笔小新   2023-12-11 10:37:34
                    

                

                
                                
                    
                        express
                        Android日历提醒软件开源项目分享及使用教程
                    

                    
                                                
                            
                        
                                                
                        本文介绍了一款名为Android日历提醒软件的开源项目，作者分享了该项目的代码和使用教程，并提供了GitHub项目地址。文章详细介绍了该软件的主界面风格、日程信息的分类查看功能，以及添加日程提醒和查看详情的界面。同时，作者还提醒了读者在使用过程中可能遇到的Android6.0权限问题，并提供了解决方法。 ...
                        [详细]
                    
                    

                    
                        蜡笔小新   2023-12-10 19:01:03
                    

                

                
                                
                    
                        express
                        设计模式——模板方法模式的应用和优缺点
                    

                    
                                                
                            
                        
                                                
                        本文介绍了设计模式中的模板方法模式，包括其定义、应用、优点、缺点和使用场景。模板方法模式是一种基于继承的代码复用技术，通过将复杂流程的实现步骤封装在基本方法中，并在抽象父类中定义模板方法的执行次序，子类可以覆盖某些步骤，实现相同的算法框架的不同功能。该模式在软件开发中具有广泛的应用价值。 ...
                        [详细]
                    
                    

                    
                        蜡笔小新   2023-12-10 17:59:47

















    

    
        
            
            
                
                
            

            
                小七            

            
                这个家伙很懒，什么也没留下！            


        
    

    
    

    
    

    
        Tags | 热门标签
        
            
                                
                    match
                
                                
                    hook
                
                                
                    bitmap
                
                                
                    format
                
                                
                    typescript
                
                                
                    foreach
                
                                
                    sum
                
                                
                    controller
                
                                
                    md5
                
                                
                    runtime
                
                                
                    char
                
                                
                    split
                
                                
                    stream
                
                                
                    bytecode
                
                                
                    hashcode
                
                                
                    list
                
                                
                    heap
                
                                
                    range
                
                                
                    erlang
                
                                
                    php8
                
                                
                    php7
                
                                
                    hash
                
                                
                    header
                
                                
                    int
                
                                
                    get
                
                                
                    httpclient
                
                                
                    frameworks
                
                                
                    eval
                
                                
                    express
                
                                
                    random
                
                                
            
        
    

    
    
        
            
            
        
        RankList | 热门文章
        
            
                                
                    1linux和jenkins的连接
                
                                
                    2cern.colt.matrix.linalg.Algebra.norm2()方法的使用及代码示例
                
                                
                    3剑指Offer017合并两个排序的链表
                
                                
                    4python开方运算符_OpenCVPython常用图像运算：加减乘除幂开方对数及位运算
                
                                
                    5十六.增加一个项目协作留言板功能（二）----- 建立一个任务管理的列表页面
                
                                
                    6使用CocoaPods管理依赖库
                
                                
                    7上界|下界_重学C++：笔记C++基础容器&C++指针引用
                
                                
                    8OSChina 周五乱弹 —— 论程序员的压力
                
                                
                    9开发笔记:php exif_read_data（）不在utf8中
                
                                
                    10怎么能做到超链接点击后变色
                
                                
                    11java char  character_Java char 与 Character
                
                                
                    12近期新闻汇总：Ref Finance 发布 2023 路线图
                
                                
                    13频域宽带波束形成（fft和LFMsource）代码
                
                                
                    14java编写一个为网站生成验证码的程序_Java后端产生验证码后台验证功能的实现代码...
                
                                
                    15Mysql调优的顺序及面试问题总结

红黑树原理详解及golang实现

红黑树原理详解及golang实现 在看红黑树原理之前，先看下二叉查找树。

二叉查找树

性质

红黑树

性质

operation

红黑树的插入

情形1：空树

情形2：插入节点父节为黑色，

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

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

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

golang实现

类型定义

leftRotate

RightRotate

Item Interface

insert

完整代码

小结

红黑树原理详解及golang实现

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

`情形1`：空树

`情形2`：插入节点父节为黑色，

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

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

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