红黑树的定义

红黑树是一种自平衡的二叉搜索树，它的每个节点都具有以下属性：

1. 颜色：每个节点要么是红色，要么是黑色。
2. 根节点是黑色的。
3. 所有叶子节点（NIL节点）都是黑色的。
4. 如果一个节点是红色的，则它的两个子节点都是黑色的。
5. 任意一个节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。
   根据这些属性，红黑树的定义可以简单地描述为：一棵红黑树是一棵满足上述五个条件的二叉搜索树。

红黑树go语言实现

  1package main
  2
  3import "fmt"
  4
  5const (
  6	red = true
  7	black = false
  8)
  9
 10type Node struct {
 11	val int
 12	left *Node
 13	right *Node
 14	color bool
 15}
 16
 17type RedBlackTree struct {
 18	root *Node
 19}
 20
 21func NewRedBlackTree() *RedBlackTree {
 22	return &RedBlackTree{}
 23}
 24
 25func (t *RedBlackTree) rotateLeft(node *Node) *Node {
 26	rightNode := node.right
 27	node.right = rightNode.left
 28	rightNode.left = node
 29	rightNode.color = node.color
 30	node.color = red
 31	return rightNode
 32}
 33
 34func (t *RedBlackTree) rotateRight(node *Node) *Node {
 35	leftNode := node.left
 36	node.left = leftNode.right
 37	leftNode.right = node
 38	leftNode.color = node.color
 39	node.color = red
 40	return leftNode
 41}
 42
 43func (t *RedBlackTree) flipColors(node *Node) {
 44	node.color = red
 45	node.left.color = black
 46	node.right.color = black
 47}
 48
 49func (t *RedBlackTree) isRed(node *Node) bool {
 50	if node == nil {
 51		return false
 52	}
 53	return node.color == red
 54}
 55
 56func (t *RedBlackTree) insert(node *Node, val int) *Node {
 57	if node == nil {
 58		return &Node{val: val, color: red}
 59	}
 60
 61	if val < node.val {
 62		node.left = t.insert(node.left, val)
 63	} else if val > node.val {
 64		node.right = t.insert(node.right, val)
 65	} else {
 66		node.val = val
 67	}
 68
 69	if t.isRed(node.right) && !t.isRed(node.left) {
 70		node = t.rotateLeft(node)
 71	}
 72	if t.isRed(node.left) && t.isRed(node.left.left) {
 73		node = t.rotateRight(node)
 74	}
 75	if t.isRed(node.left) && t.isRed(node.right) {
 76		t.flipColors(node)
 77	}
 78
 79	return node
 80}
 81
 82func (t *RedBlackTree) Insert(val int) {
 83	t.root = t.insert(t.root, val)
 84	t.root.color = black
 85}
 86
 87func (t *RedBlackTree) search(node *Node, val int) bool {
 88	if node == nil {
 89		return false
 90	}
 91	if val < node.val {
 92		return t.search(node.left, val)
 93	} else if val > node.val {
 94		return t.search(node.right, val)
 95	} else {
 96		return true
 97	}
 98}
 99
100func (t *RedBlackTree) Search(val int) bool {
101	return t.search(t.root, val)
102}
103
104func main() {
105	t := NewRedBlackTree()
106
107	// Insert some nodes
108	t.Insert(5)
109	t.Insert(3)
110	t.Insert(7)
111	t.Insert(1)
112	t.Insert(9)
113
114	// Search for some nodes
115	fmt.Println(t.Search(5)) // true
116	fmt.Println(t.Search(4)) // false
117}

解释

这里我们定义了一个 Node 结构体和一个 RedBlackTree 结构体。在 Node 结构体中，我们存储节点值，左右子节点以及节点颜色。在 RedBlackTree 结构体中，我们存储根节点，并定义了插入和搜索方法。插入方法使用递归实现，在插入过程中，根据红黑树的规则进行旋转和变色操作。

旋转操作分为左旋和右旋，左旋将右子节点提升为根节点，右子节点的左子节点作为原根节点的右子节点，原根节点作为右子节点的左子节点；右旋将左子节点提升为根节点，左子节点的右子节点作为原根节点的左子节点，原根节点作为左子节点的右子节点。

变色操作是将一个节点和它的两个子节点的颜色都改为相反的颜色。

我们还定义了一个 isRed 方法，用于判断节点是否为红色。

在 insert 方法中，我们首先使用递归将节点插入到正确的位置。然后，我们依次进行三种操作：右旋、左旋和变色。这三种操作的顺序不同，可以通过编写不同的代码实现。在本例中，我们使用了左旋和右旋的顺序，最后再进行变色操作。这个操作顺序是符合标准的红黑树的规则的。

最后，在 Insert 方法中，我们将根节点的颜色设置为黑色。

我们还定义了一个 search 方法，用于在红黑树中搜索节点。该方法也使用递归实现。在 Search 方法中，我们将搜索的操作委托给 search 方法。

在 main 函数中，我们创建了一个新的红黑树，插入了一些节点，并使用 Search 方法搜索了一些节点。