func (node *Node) uncle() *Node {
	g := node.grandparent()
	if g == nil {
		return nil
	}
	return node.Parent.sibling()
}
uncle represents the current node's "uncle" node which represents the
sibling of the node's parent.
package rbt
import "fmt"
const (
	RED   = true
	BLACK = false
)
type Node struct {
	Val                 int
	Color               bool
	Parent, Left, Right *Node
}
var LEAF = &Node{Color: BLACK, Val: -1}
func NewNode(val int) *Node {
	return &Node{
		Val:   val,
		Color: RED,
		Left:  LEAF,
		Right: LEAF,
	}
}
type RBT struct {
	root *Node
	size int
}
func NewRBT() *RBT {
	return &RBT{size: 0}
}
func (node *Node) IsRed() bool {
	if node == nil {
		return false
	}
	return node.Color == RED
}
func (node *Node) IsBlack() bool {
	return !node.IsRed()
}
func (rbt *RBT) Cardinality() int {
	return rbt.size
}
func (rbt *RBT) IsEmpty() bool {
	return rbt.Cardinality() == 0
}
func (rbt *RBT) Root() *Node {
	return rbt.root
}
func (rbt *RBT) Find(val int) *Node {
	if rbt.IsEmpty() {
		return nil
	}
	node := rbt.Root()
	for node != LEAF {
		if node.Val == val {
			return node
		} else if node.Val < val {
			node = node.Right
		} else {
			node = node.Left
		}
	}
	return nil
}
func (rbt *RBT) String() string {
	str := "RedBlackTree\n"
	if !rbt.IsEmpty() {
		output(rbt.Root(), "", true, &str)
	}
	return str
}
func (rbt *RBT) Insert(val int) bool {
	if inserted := rbt.insert(rbt.Root(), NewNode(val)); inserted != nil {
		rbt.size++
		rbt.insertBalance1(inserted)
		return true
	}
	return false
}
func (rbt *RBT) Delete(val int) bool {
	if rbt.IsEmpty() {
		return false
	}
	node := rbt.Find(val)
	if node == nil {
		return false
	}
	if node.Left != LEAF && node.Right != LEAF {
		next := node.Right
		for next.Left != LEAF {
			next = next.Left
		}
		node.Val = next.Val
		node = next
	}
	child := node.Right
	if node.Right == LEAF {
		child = node.Left
	}
	rbt.replaceNode(node, child)
	if node.IsBlack() {
		if child.IsRed() {
			child.Color = BLACK
		} else {
			rbt.deleteBalance1(child)
		}
	}
	return true
}
func (rbt *RBT) Iter(t Traversable) chan int {
	ch := make(chan int)
	go func() {
		t.Traverse(rbt.Root(), ch)
		close(ch)
	}()
	return ch
}
func (rbt *RBT) replaceNode(curNode, newNode *Node) {
	newNode.Parent = curNode.Parent
	if curNode == curNode.Parent.Left {
		curNode.Parent.Left = newNode
	} else {
		curNode.Parent.Right = newNode
	}
}
func output(node *Node, prefix string, isTail bool, str *string) {
	if node.Right != LEAF {
		newPrefix := prefix
		if isTail {
			newPrefix += "|   "
		} else {
			newPrefix += "    "
		}
		output(node.Right, newPrefix, false, str)
	}
	*str += prefix
	if isTail {
		*str += "└── "
	} else {
		*str += "┌── "
	}
	color := "BLACK"
	if node.IsRed() {
		color = "RED"
	}
	*str += fmt.Sprintf("%v (%s)", node.Val, color) + "\n"
	if node.Left != LEAF {
		newPrefix := prefix
		if isTail {
			newPrefix += "    "
		} else {
			newPrefix += "|   "
		}
		output(node.Left, newPrefix, true, str)
	}
}
func (rbt *RBT) insert(curNode, newNode *Node) *Node {
	if rbt.IsEmpty() {
		rbt.root = newNode
		return newNode
	} else if newNode.Val < curNode.Val {
		if curNode.Left == LEAF {
			curNode.Left = newNode
			newNode.Parent = curNode
			return newNode
		}
		return rbt.insert(curNode.Left, newNode)
	} else if newNode.Val > curNode.Val {
		if curNode.Right == LEAF {
			curNode.Right = newNode
			newNode.Parent = curNode
			return newNode
		}
		return rbt.insert(curNode.Right, newNode)
	}
	return nil
}
func (node *Node) grandparent() *Node {
	if node != nil && node.Parent != nil {
		return node.Parent.Parent
	}
	return nil
}