Red-black tree implementation in Go

rbtree.go

package rbtree

type Node struct {
	Color string
	Key int
	Value int
	Left, Right *Node
	P *Node
}

type RBTree struct {
	Root *Node
	Nil *Node
}

func(T *RBTree) LeftRotate(x *Node){
	y := x.Right
	x.Right = y.Left
	if y.Left != T.Nil{
		y.Left.P = x
	}
	y.P = x.P
	if x.P == T.Nil {
		T.Root = y
	}else if x == x.P.Left{
		x.P.Left = y
	}else {
		x.P.Right = y
	}
	y.Left = x
	x.P = y
}

func(T *RBTree) RightRotate(y *Node){
	x := y.Left
	y.Left = x.Right
	if x.Right != T.Nil{
		x.Right.P = y
	}
	x.P = y.P
	if y.P == T.Nil {
		T.Root = x
	}else if y == y.P.Right{
		y.P.Right = x
	}else {
		y.P.Left = x
	}
	x.Right = y
	y.P = x
}

func(T *RBTree) Insert(z *Node){
	y := T.Nil
	x := T.Root
	for x != T.Nil{
		y = x
		if z.Key < x.Key{
			x = x.Left
		}else{
			x = x.Right
		}
	}
	z.P = y
	if y == T.Nil{
		T.Root = z
	}else if z.Key < y.Key{
		y.Left = z
	}else {
		y.Right = z
	}
	z.Left = T.Nil
	z.Right = T.Nil
	z.Color = "Red"
	T.InsertFixup(z)
}

func (T *RBTree) InsertFixup(z *Node) {
	for z.P.Color == "Red"	{
		if z.P == z.P.P.Left{
			y := z.P.P.Right
			if y.Color == "Red"{
				z.P.Color = "Black"
				y.Color = "Black"
				z.P.P.Color = "Red"
				z = z.P.P
			}else {
				if z == z.P.Right{
					z = z.P
					T.LeftRotate(z)
				}
				z.P.Color = "Black"
				z.P.P.Color = "Red"
				T.RightRotate(z.P.P)
			}
		}else{
			y := z.P.P.Left
			if y.Color == "Red"{
				z.P.Color = "Black"
				y.Color = "Black"
				z.P.P.Color = "Red"
				z = z.P.P
			}else {
				if z == z.P.Left{
					z = z.P
					T.RightRotate(z)
				}
				z.P.Color = "Black"
				z.P.P.Color = "Red"
				T.LeftRotate(z.P.P)
			}
		}
	}
	T.Root.Color = "Black"
}