golang 实现红黑树（未完成）

未完待续 还差个删除，删除貌似比较难

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))
}