红黑树的实现：

package rbtree

// 红黑树节点的颜色
const (
	red   bool = false
	black bool = true
)

// Node 节点结构体
type Node struct {
	value  interface{} // 节点值
	color  bool        // 节点颜色
	left   *Node       // 左子节点
	right  *Node       // 右子节点
	parent *Node       // 父节点
}

func (n *Node) getNodeSumNoIndex() int64 {
	return n.value.(*FileDeploy).SumNoIndex
}

// RBTree 红黑树结构体
type RBTree struct {
	root *Node // 根节点
}

// newNode 新建一个节点
func newNode(value interface{}) *Node {
	return &Node{
		value: value,
		color: red,
	}
}

// isRed 判断节点颜色是否为红色
func isRed(n *Node) bool {
	if n == nil {
		return false
	}
	return n.color == red
}

// rotateLeft 左旋
func rotateLeft(n *Node) *Node {
	if n == nil || n.right == nil {
		return n
	}
	r := n.right
	n.right = r.left
	if r.left != nil {
		r.left.parent = n
	}
	r.parent = n.parent
	if n.parent == nil {
		r.parent = nil
	} else if n.parent.left == n {
		n.parent.left = r
	} else {
		n.parent.right = r
	}
	r.left = n
	n.parent = r
	return r
}

// rotateRight 右旋
func rotateRight(n *Node) *Node {
	if n == nil || n.left == nil {
		return n
	}
	l := n.left
	n.left = l.right
	if l.right != nil {
		l.right.parent = n
	}
	l.parent = n.parent
	if n.parent == nil {
		l.parent = nil
	} else if n.parent.left == n {
		n.parent.left = l
	} else {
		n.parent.right = l
	}
	l.right = n
	n.parent = l
	return l
}

// flipColor 颜色翻转
func flipColor(n *Node) {
	n.color = !n.color
	if n.left != nil {
		n.left.color = !n.left.color
	}
	if n.right != nil {
		n.right.color = !n.right.color
	}
}

// Insert 插入节点
func (t *RBTree) Insert(value interface{}) {
	if t.root == nil {
		t.root = newNode(value)
		t.root.color = black
		return
	}
	var parent *Node
	node := t.root
	for node != nil {
		parent = node
		if node.getNodeSumNoIndex() < value.(*FileDeploy).SumNoIndex {
			node = node.right
		} else {
			node = node.left
		}
	}
	newNode := newNode(value)
	newNode.parent = parent
	if parent.getNodeSumNoIndex() < newNode.getNodeSumNoIndex() {
		parent.right = newNode
	} else {
		parent.left = newNode
	}
	insertFixup(newNode, t)
}

// insertFixup 节点插入后的修复操作
func insertFixup(n *Node, t *RBTree) {
	for isRed(n.parent) {
		if n.parent == n.parent.parent.left {
			y := n.parent.parent.right
			if isRed(y) {
				n.parent.color = black
				y.color = black
				n.parent.parent.color = red
				n = n.parent.parent
			} else {
				if n == n.parent.right {
					n = n.parent
					t.root = rotateLeft(n)
				}
				n.parent.color = black
				n.parent.parent.color = red
				t.root = rotateRight(n.parent.parent)
			}
		} else {
			y := n.parent.parent.left
			if isRed(y) {
				n.parent.color = black
				y.color = black
				n.parent.parent.color = red
				n = n.parent.parent
			} else {
				if n == n.parent.left {
					n = n.parent
					t.root = rotateRight(n)
				}
				n.parent.color = black
				n.parent.parent.color = red
				t.root = rotateLeft(n.parent.parent)
			}
		}
	}
	t.root.color = black
}

// Delete 删除节点
func (t *RBTree) Delete(value interface{}) {
	node := t.Search(value)
	if node == nil {
		return
	}
	var replaceNode *Node // 被删除节点的替换节点
	var replaceColor bool // 被删除节点的替换节点的颜色
	if node.left == nil {
		replaceNode = node.right
		transplant(node, node.right, t)
	} else if node.right == nil {
		replaceNode = node.left
		transplant(node, node.left, t)
	} else {
		min := minimum(node.right)
		replaceNode = min.right
		replaceColor = min.color
		if min.parent == node {
			replaceNode.parent = min
		} else {
			transplant(min, min.right, t)
			min.right = node.right
			min.right.parent = min
		}
		transplant(node, min, t)
		min.left = node.left
		min.left.parent = min
		min.color = node.color
	}
	if replaceColor == black {
		deleteFixup(replaceNode, t)
	}
}

// transplant 替换节点
func transplant(n1, n2 *Node, t *RBTree) {
	if n1.parent == nil {
		t.root = n2
	} else if n1 == n1.parent.left {
		n1.parent.left = n2
	} else {
		n1.parent.right = n2
	}
	if n2 != nil {
		n2.parent = n1.parent
	}
}

// deleteFixup 删除节点后的修复操作
func deleteFixup(n *Node, t *RBTree) {
	for n != t.root && !isRed(n) {
		if n == n.parent.left {
			s := n.parent.right
			if isRed(s) {
				s.color = black
				n.parent.color = red
				t.root = rotateLeft(n.parent)
				s = n.parent.right
			}
			if !isRed(s.left) && !isRed(s.right) {
				s.color = red
				n = n.parent
			} else {
				if !isRed(s.right) {
					s.left.color = black
					s.color = red
					t.root = rotateRight(s)
					s = n.parent.right
				}
				s.color = n.parent.color
				n.parent.color = black
				s.right.color = black
				t.root = rotateLeft(n.parent)
				n = t.root
			}
		} else {
			s := n.parent.left
			if isRed(s) {
				s.color = black
				n.parent.color = red
				t.root = rotateRight(n.parent)
				s = n.parent.left
			}
			if !isRed(s.left) && !isRed(s.right) {
				s.color = red
				n = n.parent
			} else {
				if !isRed(s.left) {
					s.right.color = black
					s.color = red
					t.root = rotateLeft(s)
					s = n.parent.left
				}
				s.color = n.parent.color
				n.parent.color = black
				s.left.color = black
				t.root = rotateRight(n.parent)
				n = t.root
			}
		}
	}
	n.color = black
}

// minimum 查找最小值节点
func minimum(n *Node) *Node {
	for n.left != nil {
		n = n.left
	}
	return n
}

// Search 查找节点
func (t *RBTree) Search(value interface{}) *Node {
	node := t.root
	for node != nil {
		if node.getNodeSumNoIndex() == value.(*FileDeploy).SumNoIndex {
			return node
		} else if node.getNodeSumNoIndex() < value.(*FileDeploy).SumNoIndex {
			node = node.right
		} else {
			node = node.left
		}
	}
	return nil
}

// PreOrder 前序遍历
func (t *RBTree) PreOrder() []interface{} {
	res := make([]interface{}, 0)
	var preOrder func(*Node)
	preOrder = func(n *Node) {
		if n == nil {
			return
		}
		res = append(res, n.value)
		preOrder(n.left)
		preOrder(n.right)
	}
	preOrder(t.root)
	return res
}

// InOrder 中序遍历
func (t *RBTree) InOrder() []interface{} {
	res := make([]interface{}, 0)
	var inOrder func(*Node)
	inOrder = func(n *Node) {
		if n == nil {
			return
		}
		inOrder(n.left)
		res = append(res, n.value)
		inOrder(n.right)
	}
	inOrder(t.root)
	return res
}

// PostOrder 后序遍历
func (t *RBTree) PostOrder() []interface{} {
	res := make([]interface{}, 0)
	var postOrder func(*Node)
	postOrder = func(n *Node) {
		if n == nil {
			return
		}
		postOrder(n.left)
		postOrder(n.right)
		res = append(res, n.value)
	}
	postOrder(t.root)
	return res
}