未完待续 还差个删除，删除貌似比较难
package main
import "fmt"
type node struct {
key int
value int
left *node
right *node
color int
}
type RBST struct {
head *node
n int
}
func (this *RBST)put(key,value int){
if this.head == nil{
this.head = &node{key:key,value:value,color:1}
return
}
this.head = this.putValue(this.head,key,value)
return
}
func (this *RBST)rotateLeft(node *node)*node{
tmp := node.right
node.right = node.right.left
tmp.left = node
tmp.color = 1
node.color = 2
return tmp
}
func (this *RBST)rotateRight(node *node)*node{
tmp := node.left
node.left = node.left.right
tmp.right = node
tmp.color = 1
node.color = 2
return tmp
}
func (this *RBST)flipColor(node *node)*node{
node.left.color = 1
node.right.color = 1
node.color = 2
return node
}
func (this *RBST)get(key int)int{
return this.getValue(this.head,key)
}
func (this *RBST)getValue(node *node,key int)int{
if node == nil{
return 0
}
if key > node.key{
return this.getValue(node.right,key)
}else if key < node.key{
return this.getValue(node.left,key)
}
return node.value
}
func (this *RBST)putValue(Node *node,key int,value int)*node{
if Node == nil{
return &(node{key:key,value:value,color:2})
}
if key > Node.key{
Node.right = this.putValue(Node.right,key,value)
}else if key < Node.key{
Node.left = this.putValue(Node.left,key,value)
}else{
Node.value = value
return Node
}
//如果有右红链接 则左转
if Node.right != nil && Node.right.color == 2 && ( (Node.left != nil && Node.left.color == 1) || Node.left == nil){
Node = this.rotateLeft(Node)
}
//如果有左子子红链接 则右转
if Node.left != nil && Node.left.left != nil && Node.left.color == 2 && Node.left.left.color == 2{
Node = this.rotateRight(Node)
}
//如果左子红链接 且右子红链接 则 flipcolor
if Node.right != nil && Node.left != nil && Node.right.color == 2 && Node.left.color == 2{
Node = this.flipColor(Node)
}
return Node
}
func main(){
var redBlack RBST
redBlack.put(1,1)
redBlack.put(2,2)
redBlack.put(3,3)
redBlack.put(4,4)
redBlack.put(5,5)
redBlack.put(6,6)
redBlack.put(7,7)
redBlack.put(8,8)
redBlack.put(9,9)
fmt.Println(redBlack.get(9))
}
