func (rbt *RBT) insertBalance5(node *Node) {
	g := node.grandparent()
	node.Parent.Color = BLACK
	g.Color = RED
	if node == node.Parent.Left {
		rbt.rotateRight(g)
	} else {
		rbt.rotateLeft(g)
	}
}
insertBalance5 covers the final balancing case where we do a relabelling so
we don't have two red nodes in a row from case 4. As well, it does a
rotation around the grandparent node. This final rotation makes the parent
node of our original node the new parent to the node and the grandparent.
This case should have the tree / subtree fullfilling all properties of a
red-black tree.
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
}
func (node *Node) uncle() *Node {
	g := node.grandparent()
	if g == nil {
		return nil
	}
	return node.Parent.sibling()
}
func (node *Node) sibling() *Node {
	if node == nil || node.Parent == nil {
		return nil
	}
	if node == node.Parent.Left {
		return node.Parent.Right
	}
	return node.Parent.Left
}
func (rbt *RBT) insertBalance1(node *Node) {
	if node.Parent == nil {
		node.Color = BLACK
	} else {
		rbt.insertBalance2(node)
	}
}
func (rbt *RBT) insertBalance2(node *Node) {
	if node.Parent.IsBlack() {
		return
	}
	rbt.insertBalance3(node)
}
func (rbt *RBT) insertBalance3(node *Node) {
	u := node.uncle()
	if u != nil && u.IsRed() {
		node.Parent.Color = BLACK
		u.Color = BLACK
		g := node.grandparent()
		g.Color = RED
		rbt.insertBalance1(g)
	} else {
		rbt.insertBalance4(node)
	}
}
func (rbt *RBT) insertBalance4(node *Node) {
	g := node.grandparent()
	if node == node.Parent.Right && node.Parent == g.Left {
		rbt.rotateLeft(node.Parent)
		node = node.Left
	} else if node == node.Parent.Left && node.Parent == g.Right {
		rbt.rotateRight(node.Parent)
		node = node.Right
	}
	rbt.insertBalance5(node)
}