从零开始学golang之RedBlackTree-Delete

freedbg 发表了文章 • 0 个评论 • 98 次浏览 • 1 天前 • 来自相关话题

package main

import (
    "fmt"
)

func main() {
    fmt.Println("red... 			查看全部
					
package main

import (
"fmt"
)

func main() {
fmt.Println("red-black-tree")
var data = []int{6, 5, 3, 1, 8, 7, 2, 4, 9, 0, 3}
//var data = []int{6, 5, 3, 1}

tree := NewTree()
for _, v := range data {
tree.insertB(v)
}
//fmt.Println(tree.size)
tree.tdelete(tree.root, 2)
printT(tree.root)
}

type node struct {
l, r, p *node
v int
c bool //0 = red 1=black
}

type Tree struct {
root *node
last *node
size int
}

func NewTree() *Tree {
return &Tree{}
}

func (n *node) getGp() *node {
if n.p == nil {
return nil
}
if n.p.p == nil {
return nil
}
return n.p.p
}

func (n *node) getUn() *node {
if n.getGp() == nil {
return nil
}
if n.p == n.getGp().l {
return n.getGp().r
} else {
return n.getGp().l
}
}

// rotate cur node
func (tree *Tree) rotateR(n *node) {
gp := n.getGp()
p := n.p
r := n.r

n.r = p
n.p = gp

if p != nil {
p.p = n
p.l = r
if r != nil {
r.p = p
}
}
if tree.root == p {
tree.root = n
}

if gp != nil {
if gp.l == p {
gp.l = n
} else {
gp.r = n
}
}
}

func (tree *Tree) rotateL(n *node) {
gp := n.getGp()
p := n.p
l := n.l

n.l = p
n.p = gp

if p != nil {
p.p = n
p.r = l
if l != nil {
l.p = p
}
}

if tree.root == p {
tree.root = n
}

if gp != nil {
if gp.l == p {
gp.l = n
} else {
gp.r = n
}
}

}

func getMin() {

}

func getMax() {

}

func (tree *Tree) tdelete(n *node, v int) {
if tree == nil {
return
}
if v < n.v {
tree.tdelete(n.l, v)
}
if v > n.v {
tree.tdelete(n.r, v)
}

if n.v == v {
if n.l != nil && n.r != nil {
mn := tree.findMax(n)
//转换为 mu.r 必定为 nil 依据为2叉搜寻树特性 小的放左边 大的放右边
n.v = mn.v //swap data
if tree.deleteR(mn) {
tree.size--
}
} else {
if tree.deleteR(n) {
tree.size--
}
}

}
}

//n.l != nil && n.r != nil 前置条件
func (Tree *Tree) findMax(n *node) *node {
//选择n节点的左子树中最大节点
maxn := n.l
for maxn.r != nil {
maxn = maxn.r
}
return maxn
// n.v = maxn.v
// if maxn == n.l {
// maxn.p.l = n.l
// } else {
// maxn.p.r = maxn.l
// }
}
func (tree *Tree) deleteR(n *node) bool {
if n.l == nil && n.r == nil && n.p == nil {
n = nil
tree.root = n
return true
}

var child *node
if n.l != nil {
child = n.l
} else {
child = n.r
}

if n.p == nil {
child.p = nil
tree.root = child
child.c = true
return true
}

if n.p.l == n {
n.p.l = child
} else {
n.p.r = child
}
child.p = n.p

//black
if n.c == true {
if child.c == false {
child.c = true
} else {
//n= black n.child=black
//need fix
tree.fix(child)
}
}
//if red is ok
return true
}

//兄弟
func (n *node) br() *node {
if n.p.l == n {
return n.r
} else {
return n.l
}
}

//修复红黑树平衡 n.c = black n.p.c = black
func (tree *Tree) fix(n *node) {
// if n.p == nil {
// n.c = true
// tree.root = n
// return
// }
red := false
black := true
//br = red
if n.br().c == red {
n.p.c = red
n.br().c = black
if n == n.p.l {
tree.rotateL(n.br())
} else {
tree.rotateR(n.br())
}
}
if n.p.c == black && n.br().c == black && n.br().l.c == black && n.br().r.c == black {
n.br().c = red
tree.fix(n.p) //????????????
} else if n.p.c == red && n.br().c == black && n.br().l.c == black && n.br().r.c == black {
n.br().c = red
n.p.c = black
} else {
if n.br().c == black {
if n == n.p.l && n.br().l.c == red && n.br().r.c == black {
n.br().c = red
n.br().l.c = black
tree.rotateR(n.br().l)
} else if n == n.p.r && n.br().l.c == black && n.br().r.c == red {
n.br().c = red
n.br().r.c = black
tree.rotateL(n.br().r)
}
}
n.br().c = n.p.c
n.p.c = black
if n == n.p.l {
n.br().r.c = black
tree.rotateL(n.br())
} else {
n.br().l.c = black
tree.rotateR(n.br())
}
}

}

func (tree *Tree) insertB(v int) {
if tree.root == nil {
tree.root = new(node)
tree.root.v = v
tree.root.c = true
tree.size++
}

if v < tree.root.v {
if tree.Insert(&tree.root.l, v, tree.root) {
printT(tree.root)
tree.size++
tree.inserCase(tree.last)
}
}

if v > tree.root.v {
if tree.Insert(&tree.root.r, v, tree.root) {
printT(tree.root)
tree.size++
tree.inserCase(tree.last)
}
}
printT(tree.root)
}

func (tree *Tree) Insert(n **node, v int, fa *node) bool {

pn := (*n)
if (*n) == nil {
(*n) = new(node)
(*n).v = v
(*n).p = fa
tree.last = (*n)
return true
}

if v > pn.v {
tree.Insert(&(pn.r), v, *n)
}

if v < pn.v {
tree.Insert(&(pn.l), v, *n)
}

if v == pn.v {
return false
}
return true
}

func (tree *Tree) inserCase(n *node) {
if n.p == nil {
n.c = true
tree.root = n
return
}

if n.p.c == false {
if n.getUn() != nil && n.getUn().c == false {
n.p.c = true
n.getUn().c = true
n.getGp().c = false
tree.inserCase(n.getGp()) //if root node
} else {
//nil or black
if n == n.p.r && n.getGp() != nil && n.p == n.getGp().l {
tree.rotateL(n)
tree.rotateR(n)
n.c = true
n.l.c = false
n.r.c = false
}
if n == n.p.l && n.getGp() != nil && n.p == n.getGp().r {
tree.rotateR(n)
tree.rotateL(n)
n.c = true
n.l.c = false
n.r.c = false
}
if n == n.p.l && n.getGp() != nil && n.p == n.getGp().l {

n.p.c = true
if n.getGp() != nil {
n.getGp().c = false
}
tree.rotateR(n.p)
}
if n == n.p.r && n.getGp() != nil && n.p == n.getGp().r {
n.p.c = true
if n.getGp() != nil {
n.getGp().c = false
}
tree.rotateL(n.p)
}
}

}
}

//test print ----------------------------------------------
var fstr = make([]string, 20, 20)

func printT(tree *node) {
fmt.Println(tree)
fstr = make([]string, 8, 8)
printTree(tree, 0, "")
for i, str := range fstr {
fmt.Println("L", i, str)
}
}

func printTree(tree *node, i int, n string) {
fmt.Println("-----", tree)
i++
str := " "
for n := i; n < 9; n++ {
str += "-"
}
var tmp string
if tree.c == true {
tmp = fmt.Sprintf("%s\033[40;37m [%d] \033[0m%s%s", str, tree.v, n, str)
} else {
tmp = fmt.Sprintf("%s\033[41;37m [%d] \033[0m%s%s", str, tree.v, n, str)
}

fstr[i] += tmp
if tree.l != nil {
printTree(tree.l, i, "L"+fmt.Sprintf("%d", tree.v))
}
if tree.r != nil {
printTree(tree.r, i, "R"+fmt.Sprintf("%d", tree.v))
}
}

修正了 BST 时候的 delete 函数 增加了rbt 删除判断


https://github.com/godla/golang-sort-data-structures-study.git


一起每天来写一点吧

老马带您学习Go语言资料及配套视频

mazhiguo01 发表了文章 • 0 个评论 • 162 次浏览 • 2 天前 • 来自相关话题

多年混迹于IT开发和培训行业的老马和您一起学习Go语言编程。希望共同学习,共同进步! 资料+视频最佳学习方案,免费的呦。 视频地址(土豆网):查看全部

多年混迹于IT开发和培训行业的老马和您一起学习Go语言编程。希望共同学习,共同进步! 资料+视频最佳学习方案,免费的呦。
视频地址(土豆网):http://list.youku.com/albumlist/show/id_51453937.html
教程资料(博客园):http://www.cnblogs.com/mazg/

timezone转换的奇怪问题

回复

olsen 回复了问题 • 0 人关注 • 1 个回复 • 155 次浏览 • 2018-01-08 03:54 • 来自相关话题

学习笔记:在windows和linux下写文件的些许不同

3zheng 发表了文章 • 1 个评论 • 214 次浏览 • 2017-12-21 17:35 • 来自相关话题

以下代码在跨平台时存在的一个小陷阱,windows下可以正常跑,linux下fp.Write(b)会报错“bad file descriptor”

查看全部
					

以下代码在跨平台时存在的一个小陷阱,windows下可以正常跑,linux下fp.Write(b)会报错“bad file descriptor”


package main

import (
"log"
"os"
)

func main() {
fp, err := os.OpenFile("1.log", os.O_APPEND|os.O_CREATE, 0666)
if err != nil {
return
}
defer fp.Close()
b := []byte("1234567890")
n, err := fp.Write(b)
if err != nil {
log.Println("error:", err)
}
log.Println("n = ", n)
}

linux也要正常运行得把os.OpenFile(fileName, os.O_APPEND|os.O_CREATE, 0666)改成
os.OpenFile(fileName, os.O_APPEND|os.O_CREATE|os.O_RDWR, 0666)或者os.OpenFile(fileName, os.O_APPEND|os.O_CREATE|os.O_WRONLY, 0666)


因为我是根据C的写文件的方式来写的,以为os.O_APPEND|os.O_CREATE作为C的open(filename, "a"),然而实际上os.O_APPEND|os.O_CREATE|os.O_WRONLY才是C的open(filename, "a")


和我一样从C/C++转过来的gopher小伙伴千万注意啊

GO 调用C++ dll,报 is not a valid Win32 application.

plain 回复了问题 • 4 人关注 • 3 个回复 • 1250 次浏览 • 2017-12-21 15:21 • 来自相关话题

gogland 设置Run Configurations

tupunco 回复了问题 • 2 人关注 • 3 个回复 • 697 次浏览 • 2017-12-02 21:36 • 来自相关话题

我想用go实现类似http代理的功能,有什么可行的方案吗?

detailyang 回复了问题 • 2 人关注 • 1 个回复 • 299 次浏览 • 2017-11-30 15:59 • 来自相关话题

golang有在线编译环境吗?

xiaoma 回复了问题 • 5 人关注 • 4 个回复 • 456 次浏览 • 2017-11-28 10:33 • 来自相关话题

使用Beego框架如何在函数中的日志中打印ID?

回复

g00355049 发起了问题 • 2 人关注 • 0 个回复 • 382 次浏览 • 2017-11-03 20:46 • 来自相关话题

golang websocket android连接的问题

回复

lywsbcn 发起了问题 • 1 人关注 • 0 个回复 • 463 次浏览 • 2017-09-25 11:32 • 来自相关话题

go 编写yml文件

回复

KSpeer 回复了问题 • 1 人关注 • 1 个回复 • 672 次浏览 • 2017-09-01 14:41 • 来自相关话题

语法问题,帮忙看看

gongxun 回复了问题 • 2 人关注 • 1 个回复 • 402 次浏览 • 2017-08-31 19:22 • 来自相关话题

项目中过多的使用反射等功能是不是对别的程序员不太友好?

moxie 回复了问题 • 7 人关注 • 7 个回复 • 704 次浏览 • 2017-08-17 12:46 • 来自相关话题

go在不使用任何框架的情况下,能不能进行web开发

飞雪无情 回复了问题 • 9 人关注 • 9 个回复 • 1010 次浏览 • 2017-08-15 22:01 • 来自相关话题

go get github.com/elastic/beats 命令出错,求指点

voidint 回复了问题 • 3 人关注 • 3 个回复 • 667 次浏览 • 2017-08-12 09:10 • 来自相关话题