go 语言根据下面定义实现红黑树, 删除方法, 删除时要删除重复元素 // 红黑树节点的颜色 const ( red bool = false black bool = true ) // Node 节点结构体 type Node struct { value interface{} // 节点值 color bool // 节点颜色 left *Node // 左子节点 right *Node // 右子节点 pare...-Go服务器开发

package main

import “fmt”

// 红黑树节点的颜色 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.(int64)

}

// RBTree 红黑树结构体 type RBTree struct {

root *Node // 根节点

}

// Insert 插入节点 func (t *RBTree) Insert(value int64) {

if t.root == nil { // 如果根节点为空，则直接插入
	t.root = &Node{value: value, color: black}
} else {
	// 找到插入位置
	node := t.root
	for {
		if node.getNodeSumNoIndex() < value { // 往右插入
			if node.right == nil { // 如果右子节点为空，则直接插入
				node.right = &Node{value: value, color: red, parent: node}
				t.insertFixup(node.right)
				break
			}
			node = node.right
		} else if node.getNodeSumNoIndex() > value { // 往左插入
			if node.left == nil { // 如果左子节点为空，则直接插入
				node.left = &Node{value: value, color: red, parent: node}
				t.insertFixup(node.left)
				break
			}
			node = node.left
		} else { // 如果节点值已存在，则直接更新节点值
			node.value = value
			break
		}
	}
}

}

// insertFixup 插入后修复红黑树性质 func (t *RBTree) insertFixup(node *Node) {

for node.parent != nil && node.parent.color == red { // 如果父节点是红色，需要修复
	if node.parent == node.parent.parent.left { // 如果父节点是祖父节点的左子节点
		uncle := node.parent.parent.right
		if uncle != nil && uncle.color == red { // Case 1: 叔叔节点是红色
			node.parent.color = black
			uncle.color = black
			node.parent.parent.color = red
			node = node.parent.parent
		} else { // Case 2: 叔叔节点是黑色
			if node == node.parent.right { // 如果当前节点是父节点的右子节点
				node = node.parent
				t.leftRotate(node)
			}
			node.parent.color = black // Case 3: 叔叔节点是黑色，且当前节点是父节点的左子节点
			node.parent.parent.color = red
			t.rightRotate(node.parent.parent)
		}
	} else { // 如果父节点是祖父节点的右子节点
		uncle := node.parent.parent.left
		if uncle != nil && uncle.color == red { // Case 1: 叔叔节点是红色
			node.parent.color = black
			uncle.color = black
			node.parent.parent.color = red
			node = node.parent.parent
		} else { // Case 2: 叔叔节点是黑色
			if node == node.parent.left { // 如果当前节点是父节点的左子节点
				node = node.parent
				t.rightRotate(node)
			}
			node.parent.color = black // Case 3: 叔叔节点是黑色，且当前节点是父节点的右子节点
			node.parent.parent.color = red
			t.leftRotate(node.parent.parent)
		}
	}
}
t.root.color = black // 根节点必须为黑色

}

// Delete 删除节点 func (t *RBTree) Delete(value int64) {

node := t.getNodeByValue(value)
if node == nil { // 节点不存在，则直接返回
	return
}
if node.left != nil && node.right != nil { // 如果节点有两个子节点，则用它的后继节点来替代它
	successor := node.right.getMinNode()
	node.value = successor.value
	node = successor
}
var replacement *Node // 用来替换要被删除的节点
if node.left != nil { // 如果节点只有一个左子节点，则用它的左子节点来替代它
	replacement = node.left
} else if node.right != nil { // 如果节点只有一个右子节点，则用它的右子节点来替代它
	replacement = node.right
}
if replacement != nil { // 如果替换节点不为空，则修改替换节点的父节点
	replacement.parent = node.parent
	if node.parent == nil { // 如果要被删除的节点是根节点，则直接用替换节点来代替它
		t.root = replacement
	} else if node == node.parent.left { // 如果要被删除的节点是父节点的左子节点，则用替换节点来代替它
		node.parent.left = replacement
	} else { // 如果要被删除的节点是父节点的右子节点，则用替换节点来代替它
		node.parent.right = replacement
	}
	if node.color == black { // 如果要被删除的节点是黑色，需要修复红黑树性质
		t.deleteFixup(replacement)
	}
} else if node.parent == nil { // 如果要被删除的节点是根节点且没有子节点，则直接将根节点置空
	t.root = nil
} else { // 如果要被删除的节点没有子节点，则直接删除它
	if node.color == black { // 如果要被删除的节点是黑色，需要修复红黑树性质
		t.deleteFixup(node)
	}
	if node.parent != nil { // 修改父节点的子节点引用
		if node == node.parent.left {
			node.parent.left = nil
		} else if node == node.parent.right {
			node.parent.right = nil
		}
		node.parent = nil
	}
}

}

// deleteFixup 删除后修复红黑树性质 func (t *RBTree) deleteFixup(node *Node) {

for node != t.root && node.color == black { // 如果节点是黑色，需要修复
	if node == node.parent.left { // 如果节点是父节点的左子节点
		sibling := node.parent.right
		if sibling.color == red { // Case 1: 兄弟节点是红色
			sibling.color = black
			node.parent.color = red
			t.leftRotate(node.parent)
			sibling = node.parent.right
		}
		if sibling.left.color == black && sibling.right.color == black { // Case 2: 兄弟节点和它的两个子节点都是黑色
			sibling.color = red
			node = node.parent
		} else {
			if sibling.right.color == black { // Case 3: 兄弟节点是黑色，且它的左子节点是红色，右子节点是黑色
				sibling.left.color = black
				sibling.color = red
				t.rightRotate(sibling)
				sibling = node.parent.right
			}
			sibling.color = node.parent.color // Case 4: 兄弟节点是黑色，且它的右子节点是红色
			node.parent.color = black
			sibling.right.color = black
			t.leftRotate(node.parent)
			node = t.root // 跳出循环
		}
	} else { // 如果节点是父节点的右子节点
		sibling := node.parent.left
		if sibling.color == red { // Case 1: 兄弟节点是红色
			sibling.color = black
			node.parent.color = red
			t.rightRotate(node.parent)
			sibling = node.parent.left
		}
		if sibling.left.color == black && sibling.right.color == black { // Case 2: 兄弟节点和它的两个子节点都是黑色
			sibling.color = red
			node = node.parent
		} else {
			if sibling.left.color == black { // Case 3: 兄弟节点是黑色，且它的右子节点是红色，左子节点是黑色
				sibling.right.color = black
				sibling.color = red
				t.leftRotate(sibling)
				sibling = node.parent.left
			}
			sibling.color = node.parent.color // Case 4: 兄弟节点是黑色，且它的左子节点是红色
			node.parent.color = black
			sibling.left.color = black
			t.rightRotate(node.parent)
			node = t.root // 跳出循环
		}
	}
}
node.color = black // 如果节点是红色，则直接将其变为黑色

}

// getNodeByValue 根据节点值获取节点 func (t *RBTree) getNodeByValue(value int64) *Node {

node := t.root
for node != nil {
	if node.getNodeSumNoIndex() == value {
		return node
	} else if node.getNodeSumNoIndex() < value {
		node = node.right
	} else {
		node = node.left
	}
}
return nil

}

// getMinNode 获取以当前节点为根节点的最小节点 func (n *Node) getMinNode() *Node {

for n.left != nil {
	n = n.left
}
return n

}

// leftRotate 左旋操作 func (t *RBTree) leftRotate(node *Node) {

right := node.right
node.right = right.left
if right.left != nil {
	right.left.parent = node
}
right.parent = node.parent
if node.parent == nil {
	t.root = right
} else if node == node.parent.left {
	node.parent.left = right
} else {
	node.parent.right = right
}
right.left = node
node.parent = right

}

// rightRotate 右旋操作 func (t *RBTree) rightRotate(node *Node) {

left := node.left
node.left = left.right
if left.right != nil {
	left.right.parent = node
}
left.parent = node.parent
if node.parent == nil {
	t.root = left
} else if node == node.parent.left {
	node.parent.left = left
} else {
	node.parent.right = left
}
left.right = node
node.parent = left

}

func main() {

tree := &RBTree{}
tree.Insert(11)
tree.Insert(2)
tree.Insert(14)
tree.Insert(1)
tree.Insert(7)
tree.Insert(15)
tree.Insert(5)
tree.Insert(8)
tree.Insert(4)
tree.Insert(0)
tree.Insert(3)
tree.Insert(6)
tree.Delete(2)
fmt.Println(tree.root.getNodeSumNoIndex()) // Output: 7

}