golang-cookbook

Appearance

红黑树 ​

红黑树（Red-Black Tree）是一种自平衡的二叉查找树，具有以下特性，使得它在最坏情况下也能保持较好的性能。红黑树主要用于实现具有高性能的查找、插入和删除操作的应用场景（例如，Java 的 TreeMap 和 C++ 的 std::map 都使用红黑树）。

红黑树的性质 ​

红黑树在二叉搜索树的基础上添加了颜色属性，每个节点都有一个颜色（红色或黑色），并且遵循以下规则：

  1. 每个节点要么是红色，要么是黑色。
  2. 根节点是黑色。
  3. 每个叶子节点（NIL 节点）是黑色。
  4. 如果一个节点是红色的，那么它的子节点必须是黑色的（即，不能有两个连续的红色节点）。
  5. 从任意节点到其所有后代叶子节点的路径中，必须有相同数量的黑色节点。
  6. 对于每个节点，左子树和右子树的路径黑色节点数必须相同。

这些性质保证了红黑树的平衡性，从而使得插入、删除和查找操作的时间复杂度都为 O(log n)。

红黑树的基本操作 ​

  1. 插入：插入新节点时，可能会违反红黑树的性质，需要通过颜色变换和旋转来恢复红黑树的性质。
  2. 删除：删除节点时，可能会破坏红黑树的平衡，同样需要通过颜色变换和旋转来恢复平衡。
  3. 查找：查找操作与普通的二叉搜索树相同，但是由于红黑树的平衡特性，查找操作的时间复杂度保持在 O(log n)。

红黑树的旋转操作 ​

旋转操作是维持红黑树平衡的重要工具，旋转可以分为左旋转和右旋转。

1. 左旋转 ​

左旋转操作是将一个节点右子树的根节点变为新的父节点，而原本的父节点变为新的左子节点。

go
func leftRotate(root *Node, x *Node) *Node {
    y := x.Right
    x.Right = y.Left
    if y.Left != nil {
        y.Left.Parent = x
    }
    y.Parent = x.Parent
    if x.Parent == nil {
        root = y
    } else if x == x.Parent.Left {
        x.Parent.Left = y
    } else {
        x.Parent.Right = y
    }
    y.Left = x
    x.Parent = y
    return root
}

2. 右旋转 ​

右旋转操作与左旋转操作类似，只是方向相反。

go
func rightRotate(root *Node, x *Node) *Node {
    y := x.Left
    x.Left = y.Right
    if y.Right != nil {
        y.Right.Parent = x
    }
    y.Parent = x.Parent
    if x.Parent == nil {
        root = y
    } else if x == x.Parent.Right {
        x.Parent.Right = y
    } else {
        x.Parent.Left = y
    }
    y.Right = x
    x.Parent = y
    return root
}

红黑树的插入 ​

插入新节点时，首先将新节点插入到树中的适当位置（按照二叉搜索树的规则）。然后，需要通过颜色变换和旋转来恢复红黑树的性质。

插入后的恢复步骤 ​

  1. 新插入的节点总是红色。
  2. 如果父节点是红色，则违反了红黑树的规则，需要进行调整。调整分为几种情况：
    • 情况 1：父节点是红色且叔叔节点是红色。在这种情况下，只需要改变父节点和叔叔节点的颜色，然后将祖父节点作为新的当前节点进行处理。
    • 情况 2：父节点是红色且叔叔节点是黑色，需要通过旋转来恢复平衡。

红黑树的完整插入代码 ​

go
package main

import "fmt"

const (
	RED   = true
	BLACK = false
)

type Node struct {
	Value  int
	Color  bool
	Left   *Node
	Right  *Node
	Parent *Node
}

type RedBlackTree struct {
	Root *Node
}

func (rbt *RedBlackTree) Insert(value int) {
	newNode := &Node{Value: value, Color: RED}
	if rbt.Root == nil {
		rbt.Root = newNode
		rbt.Root.Color = BLACK
		return
	}
	rbt.insertHelper(rbt.Root, newNode)
	rbt.fixInsert(newNode)
}

func (rbt *RedBlackTree) insertHelper(root, newNode *Node) {
	if newNode.Value < root.Value {
		if root.Left == nil {
			root.Left = newNode
			newNode.Parent = root
		} else {
			rbt.insertHelper(root.Left, newNode)
		}
	} else {
		if root.Right == nil {
			root.Right = newNode
			newNode.Parent = root
		} else {
			rbt.insertHelper(root.Right, newNode)
		}
	}
}

func (rbt *RedBlackTree) fixInsert(newNode *Node) {
	for newNode.Parent != nil && newNode.Parent.Color == RED {
		if newNode.Parent == newNode.Parent.Parent.Left {
			uncle := newNode.Parent.Parent.Right
			if uncle != nil && uncle.Color == RED {
				// Case 1: Uncle is RED
				newNode.Parent.Color = BLACK
				uncle.Color = BLACK
				newNode.Parent.Parent.Color = RED
				newNode = newNode.Parent.Parent
			} else {
				// Case 2: Uncle is BLACK
				if newNode == newNode.Parent.Right {
					newNode = newNode.Parent
					rbt.leftRotate(newNode)
				}
				newNode.Parent.Color = BLACK
				newNode.Parent.Parent.Color = RED
				rbt.rightRotate(newNode.Parent.Parent)
			}
		} else {
			uncle := newNode.Parent.Parent.Left
			if uncle != nil && uncle.Color == RED {
				// Case 1: Uncle is RED
				newNode.Parent.Color = BLACK
				uncle.Color = BLACK
				newNode.Parent.Parent.Color = RED
				newNode = newNode.Parent.Parent
			} else {
				// Case 2: Uncle is BLACK
				if newNode == newNode.Parent.Left {
					newNode = newNode.Parent
					rbt.rightRotate(newNode)
				}
				newNode.Parent.Color = BLACK
				newNode.Parent.Parent.Color = RED
				rbt.leftRotate(newNode.Parent.Parent)
			}
		}
	}
	rbt.Root.Color = BLACK
}

func (rbt *RedBlackTree) leftRotate(x *Node) {
	y := x.Right
	x.Right = y.Left
	if y.Left != nil {
		y.Left.Parent = x
	}
	y.Parent = x.Parent
	if x.Parent == nil {
		rbt.Root = y
	} else if x == x.Parent.Left {
		x.Parent.Left = y
	} else {
		x.Parent.Right = y
	}
	y.Left = x
	x.Parent = y
}

func (rbt *RedBlackTree) rightRotate(x *Node) {
	y := x.Left
	x.Left = y.Right
	if y.Right != nil {
		y.Right.Parent = x
	}
	y.Parent = x.Parent
	if x.Parent == nil {
		rbt.Root = y
	} else if x == x.Parent.Right {
		x.Parent.Right = y
	} else {
		x.Parent.Left = y
	}
	y.Right = x
	x.Parent = y
}

func main() {
	rbt := &RedBlackTree{}
	rbt.Insert(10)
	rbt.Insert(20)
	rbt.Insert(30)
	rbt.Insert(15)

	// 输出根节点的值
	fmt.Println("Root:", rbt.Root.Value)
}

总结 ​

红黑树通过保持平衡的性质，确保了在最坏情况下的查找、插入和删除操作的时间复杂度为 O(log n)。通过旋转操作和颜色变换，红黑树能够动态地调整其结构，避免树的高度过大，从而提供高效的操作性能。

红黑树的实现涉及到一些复杂的操作，包括旋转和颜色调整，因此理解和实现红黑树通常需要一些时间，但它在需要高效查找和动态插入、删除的应用中非常有用。