红黑树go语言实现

红黑树的定义

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

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

红黑树go语言实现

package main

import "fmt"

const (
	red = true
	black = false
)

type Node struct {
	val int
	left *Node
	right *Node
	color bool
}

type RedBlackTree struct {
	root *Node
}

func NewRedBlackTree() *RedBlackTree {
	return &RedBlackTree{}
}

func (t *RedBlackTree) rotateLeft(node *Node) *Node {
	rightNode := node.right
	node.right = rightNode.left
	rightNode.left = node
	rightNode.color = node.color
	node.color = red
	return rightNode
}

func (t *RedBlackTree) rotateRight(node *Node) *Node {
	leftNode := node.left
	node.left = leftNode.right
	leftNode.right = node
	leftNode.color = node.color
	node.color = red
	return leftNode
}

func (t *RedBlackTree) flipColors(node *Node) {
	node.color = red
	node.left.color = black
	node.right.color = black
}

func (t *RedBlackTree) isRed(node *Node) bool {
	if node == nil {
		return false
	}
	return node.color == red
}

func (t *RedBlackTree) insert(node *Node, val int) *Node {
	if node == nil {
		return &Node{val: val, color: red}
	}

	if val < node.val {
		node.left = t.insert(node.left, val)
	} else if val > node.val {
		node.right = t.insert(node.right, val)
	} else {
		node.val = val
	}

	if t.isRed(node.right) && !t.isRed(node.left) {
		node = t.rotateLeft(node)
	}
	if t.isRed(node.left) && t.isRed(node.left.left) {
		node = t.rotateRight(node)
	}
	if t.isRed(node.left) && t.isRed(node.right) {
		t.flipColors(node)
	}

	return node
}

func (t *RedBlackTree) Insert(val int) {
	t.root = t.insert(t.root, val)
	t.root.color = black
}

func (t *RedBlackTree) search(node *Node, val int) bool {
	if node == nil {
		return false
	}
	if val < node.val {
		return t.search(node.left, val)
	} else if val > node.val {
		return t.search(node.right, val)
	} else {
		return true
	}
}

func (t *RedBlackTree) Search(val int) bool {
	return t.search(t.root, val)
}

func main() {
	t := NewRedBlackTree()

	// Insert some nodes
	t.Insert(5)
	t.Insert(3)
	t.Insert(7)
	t.Insert(1)
	t.Insert(9)

	// Search for some nodes
	fmt.Println(t.Search(5)) // true
	fmt.Println(t.Search(4)) // false
}

解释

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

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

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

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

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

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

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

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

红黑树go语言实现 ​

红黑树的定义 ​