红黑树图解与可视化

红黑树(Red-Black Tree)

介绍

红黑树是一种自平衡二叉搜索树，最初被称为"对称二叉B树"，后来改名为红黑树。因为在每个节点上都增加了一个表示颜色的属性，可以是红色或黑色。红黑树通过着色规则和特定的重新平衡操作（旋转和重新着色）来保持树的平衡。

红黑树中的几个关键概念：

节点（Node）：包含数据、左右子节点指针、父节点指针及颜色标记（红/黑）

着色规则：每个节点被标记为红色或黑色，以满足特定的平衡条件

黑高（Black Height）：从任一节点到其后代叶节点的路径上黑色节点的数量

旋转（Rotation）：与AVL树类似的结构调整操作

重新着色（Recoloring）：改变节点颜色，配合旋转实现平衡

核心特性

红黑树必须满足以下五个性质：

每个节点或是红色，或是黑色

根节点必须是黑色

所有叶子节点（NIL节点）都是黑色

如果一个节点是红色，则其两个子节点都是黑色（不能有连续的红色节点）

对于每个节点，从该节点到其所有后代叶子节点的路径上，包含相同数量的黑色节点

这些规则保证了红黑树的关键特性：

高度平衡：从根到叶子的最长路径不会超过最短路径的两倍

O(log n)性能：查找、插入和删除操作都保证O(log n)时间复杂度

自平衡：通过颜色变换和旋转操作自动调整结构

相对宽松的平衡：比AVL树允许更多的不平衡，减少重新平衡操作

基本操作

1. 查找元素

时间复杂度：O(log n)

方法：与普通二叉搜索树相同

2. 插入元素

时间复杂度：O(log n)

步骤：

执行标准二叉搜索树插入

将新插入的节点着色为红色

如违反了红黑树性质，进行修复操作

重新着色

旋转（左旋、右旋）

3. 删除元素

时间复杂度：O(log n)

步骤：

执行标准二叉搜索树删除

如被删除节点的替代节点违反红黑树性质，进行修复操作

重新着色

旋转（左旋、右旋）

4. 修复操作

颜色翻转：更改节点和其子节点的颜色

左旋：右子树过重时使用

右旋：左子树过重时使用

基础实现

代码实现

Java

▼Java复制代码/**

* 红黑树的Java实现

*/

public class RedBlackTree {

// 颜色常量

private static final boolean RED = true;

private static final boolean BLACK = false;

// 树节点定义

class Node {

int key; // 节点值

Node left; // 左子节点

Node right; // 右子节点

Node parent; // 父节点

boolean color; // 节点颜色（true为红，false为黑）

Node(int key) {

this.key = key;

this.color = RED; // 新节点默认为红色

}

}

private Node root; // 根节点

private Node NIL; // 哨兵节点（表示叶子节点）

// 构造函数

public RedBlackTree() {

NIL = new Node(0);

NIL.color = BLACK;

NIL.left = null;

NIL.right = null;

root = NIL;

}

// 获取节点颜色，空节点视为黑色

private boolean colorOf(Node node) {

return node == NIL ? BLACK : node.color;

}

// 判断节点是否为红色

private boolean isRed(Node node) {

return colorOf(node) == RED;

}

// 判断节点是否为黑色

private boolean isBlack(Node node) {

return colorOf(node) == BLACK;

}

// 设置节点颜色

private void setColor(Node node, boolean color) {

if (node != NIL) {

node.color = color;

}

}

// 左旋操作

private void leftRotate(Node x) {

Node y = x.right; // 设置y为x的右子节点

// 将y的左子树设为x的右子树

x.right = y.left;

if (y.left != NIL) {

y.left.parent = x;

}

// 设置y的父节点

y.parent = x.parent;

// 设置x的父节点关系

if (x.parent == null) {

root = y;

} else if (x == x.parent.left) {

x.parent.left = y;

} else {

x.parent.right = y;

}

// 完成旋转

y.left = x;

x.parent = y;

}

// 右旋操作

private void rightRotate(Node y) {

Node x = y.left; // 设置x为y的左子节点

// 将x的右子树设为y的左子树

y.left = x.right;

if (x.right != NIL) {

x.right.parent = y;

}

// 设置x的父节点

x.parent = y.parent;

// 设置y的父节点关系

if (y.parent == null) {

root = x;

} else if (y == y.parent.left) {

y.parent.left = x;

} else {

y.parent.right = x;

}

// 完成旋转

x.right = y;

y.parent = x;

}

// 插入节点

public void insert(int key) {

Node node = new Node(key);

node.left = NIL;

node.right = NIL;

Node y = null;

Node x = this.root;

// 找到插入位置

while (x != NIL) {

y = x;

if (node.key < x.key) {

x = x.left;

} else {

x = x.right;

}

}

// 设置node的父节点

node.parent = y;

// 设置node为根节点或者是父节点的左/右孩子

if (y == null) {

root = node;

} else if (node.key < y.key) {

y.left = node;

} else {

y.right = node;

}

// 如果新节点是根节点，则将其设为黑色

if (node.parent == null) {

node.color = BLACK;

return;

}

// 如果新节点的祖父节点为空，则不需要修复

if (node.parent.parent == null) {

return;

}

// 修复红黑树性质

fixInsert(node);

}

// 修复插入后的红黑树性质

private void fixInsert(Node k) {

Node u;

while (isRed(k.parent)) {

// 父节点是祖父节点的右子节点

if (k.parent == k.parent.parent.right) {

u = k.parent.parent.left; // 叔叔节点

// 情况1：叔叔节点是红色

if (isRed(u)) {

u.color = BLACK;

k.parent.color = BLACK;

k.parent.parent.color = RED;

k = k.parent.parent;

} else {

// 情况2：叔叔节点是黑色，当前节点是左子节点

if (k == k.parent.left) {

k = k.parent;

rightRotate(k);

}

// 情况3：叔叔节点是黑色，当前节点是右子节点

k.parent.color = BLACK;

k.parent.parent.color = RED;

leftRotate(k.parent.parent);

}

} else { // 父节点是祖父节点的左子节点

u = k.parent.parent.right; // 叔叔节点

// 情况1：叔叔节点是红色

if (isRed(u)) {

u.color = BLACK;

k.parent.color = BLACK;

k.parent.parent.color = RED;

k = k.parent.parent;

} else {

// 情况2：叔叔节点是黑色，当前节点是右子节点

if (k == k.parent.right) {

k = k.parent;

leftRotate(k);

}

// 情况3：叔叔节点是黑色，当前节点是左子节点

k.parent.color = BLACK;

k.parent.parent.color = RED;

rightRotate(k.parent.parent);

}

}

// 如果k是根节点，退出循环

if (k == root) {

break;

}

}

// 确保根节点是黑色

root.color = BLACK;

}

// 查找最小值节点

private Node minimum(Node node) {

while (node.left != NIL) {

node = node.left;

}

return node;

}

// 用v替换u

private void transplant(Node u, Node v) {

if (u.parent == null) {

root = v;

} else if (u === u.parent.left) {

u.parent.left = v;

} else {

u.parent.right = v;

}

v.parent = u.parent;

}

// 删除节点

public void delete(int key) {

Node z = search(root, key);

if (z == NIL) {

System.out.println("Key " + key + " not found in the tree");

return;

}

Node y = z;

Node x;

boolean yOriginalColor = y.color;

if (z.left == NIL) {

x = z.right;

transplant(z, z.right);

} else if (z.right == NIL) {

x = z.left;

transplant(z, z.left);

} else {

y = minimum(z.right);

yOriginalColor = y.color;

x = y.right;

if (y.parent === z) {

x.parent = y;

} else {

transplant(y, y.right);

y.right = z.right;

y.right.parent = y;

}

transplant(z, y);

y.left = z.left;

y.left.parent = y;

y.color = z.color;

}

// 如果原始颜色是黑色，需要修复

if (yOriginalColor == BLACK) {

fixDelete(x);

}

}

// 修复删除后的红黑树性质

private void fixDelete(Node x) {

while (x != root && isBlack(x)) {

if (x == x.parent.left) {

Node w = x.parent.right;

// 情况1：兄弟节点是红色

if (isRed(w)) {

w.color = BLACK;

x.parent.color = RED;

leftRotate(x.parent);

w = x.parent.right;

}

// 情况2：兄弟节点是黑色，且两个子节点都是黑色

if (isBlack(w.left) && isBlack(w.right)) {

w.color = RED;

x = x.parent;

} else {

// 情况3：兄弟节点是黑色，左子节点是红色，右子节点是黑色

if (isBlack(w.right)) {

w.left.color = BLACK;

w.color = RED;

rightRotate(w);

w = x.parent.right;

}

// 情况4：兄弟节点是黑色，右子节点是红色

w.color = x.parent.color;

x.parent.color = BLACK;

w.right.color = BLACK;

leftRotate(x.parent);

x = root;

}

} else { // x是右子节点

Node w = x.parent.left;

// 情况1：兄弟节点是红色

if (isRed(w)) {

w.color = BLACK;

x.parent.color = RED;

rightRotate(x.parent);

w = x.parent.left;

}

// 情况2：兄弟节点是黑色，且两个子节点都是黑色

if (isBlack(w.right) && isBlack(w.left)) {

w.color = RED;

x = x.parent;

} else {

// 情况3：兄弟节点是黑色，右子节点是红色，左子节点是黑色

if (isBlack(w.left)) {

w.right.color = BLACK;

w.color = RED;

leftRotate(w);

w = x.parent.left;

}

// 情况4：兄弟节点是黑色，左子节点是红色

w.color = x.parent.color;

x.parent.color = BLACK;

w.left.color = BLACK;

rightRotate(x.parent);

x = root;

}

}

}

// 将x设为黑色

x.color = BLACK;

}

// 查找节点

private Node search(Node root, int key) {

if (root == NIL || key == root.key) {

return root;

}

if (key < root.key) {

return search(root.left, key);

} else {

return search(root.right, key);

}

}

// 公开的查找方法

public boolean contains(int key) {

return search(root, key) != NIL;

}

// 中序遍历

public void inorderTraversal() {

inorder(root);

System.out.println();

}

private void inorder(Node node) {

if (node != NIL) {

inorder(node.left);

System.out.print(node.key +

(node.color == RED ? "(R) " : "(B) "));

inorder(node.right);

}

}

// 获取树的黑高

public int blackHeight() {

return calculateBlackHeight(root);

}

private int calculateBlackHeight(Node node) {

if (node == NIL) {

return 0;

}

int leftHeight = calculateBlackHeight(node.left);

int rightHeight = calculateBlackHeight(node.right);

// 验证左右子树黑高是否相同

if (leftHeight != rightHeight) {

throw new RuntimeException("Red-Black Tree property violation: Unequal black heights");

}

// 计算当前节点到叶子节点的黑色节点数

return isBlack(node) ? leftHeight + 1 : leftHeight;

}

}

JavaScript 实现

▼Javascript复制代码class RedBlackTree {

static RED = true;

static BLACK = false;

constructor() {

this.NIL = { key: null, color: RedBlackTree.BLACK, left: null, right: null, parent: null };

this.root = this.NIL;

}

// 左旋转

leftRotate(x) {

const y = x.right;

x.right = y.left;

if (y.left !== this.NIL) {

y.left.parent = x;

}

y.parent = x.parent;

if (x.parent === null) {

this.root = y;

} else if (x === x.parent.left) {

x.parent.left = y;

} else {

x.parent.right = y;

}

y.left = x;

x.parent = y;

}

// 右旋转

rightRotate(y) {

const x = y.left;

y.left = x.right;

if (x.right !== this.NIL) {

x.right.parent = y;

}

x.parent = y.parent;

if (y.parent === null) {

this.root = x;

} else if (y === y.parent.left) {

y.parent.left = x;

} else {

y.parent.right = x;

}

x.right = y;

y.parent = x;

}

// 插入

insert(key) {

const node = {

key: key,

color: RedBlackTree.RED,

left: this.NIL,

right: this.NIL,

parent: null

};

let y = null;

let x = this.root;

// 找到要插入的位置

while (x !== this.NIL) {

y = x;

if (node.key < x.key) {

x = x.left;

} else {

x = x.right;

}

}

node.parent = y;

if (y === null) {

this.root = node;

} else if (node.key < y.key) {

y.left = node;

} else {

y.right = node;

}

// 如果新节点是根节点，只需要设为黑色

if (node.parent === null) {

node.color = RedBlackTree.BLACK;

return;

}

// 如果祖父节点为空，则直接返回

if (node.parent.parent === null) {

return;

}

// 修复红黑树的性质

this.fixInsert(node);

}

// 修复插入后的红黑树性质

fixInsert(k) {

let u;

while (k.parent && k.parent.color === RedBlackTree.RED) {

if (k.parent === k.parent.parent.right) {

u = k.parent.parent.left;

// 情况1：叔叔是红色

if (u && u.color === RedBlackTree.RED) {

u.color = RedBlackTree.BLACK;

k.parent.color = RedBlackTree.BLACK;

k.parent.parent.color = RedBlackTree.RED;

k = k.parent.parent;

} else {

// 情况2：k是左子节点

if (k === k.parent.left) {

k = k.parent;

this.rightRotate(k);

}

// 情况3：k是右子节点

k.parent.color = RedBlackTree.BLACK;

k.parent.parent.color = RedBlackTree.RED;

this.leftRotate(k.parent.parent);

}

} else {

u = k.parent.parent.right;

// 情况1：叔叔是红色

if (u && u.color === RedBlackTree.RED) {

u.color = RedBlackTree.BLACK;

k.parent.color = RedBlackTree.BLACK;

k.parent.parent.color = RedBlackTree.RED;

k = k.parent.parent;

} else {

// 情况2：k是右子节点

if (k === k.parent.right) {

k = k.parent;

this.leftRotate(k);

}

// 情况3：k是左子节点

k.parent.color = RedBlackTree.BLACK;

k.parent.parent.color = RedBlackTree.RED;

this.rightRotate(k.parent.parent);

}

}

if (k === this.root) {

break;

}

}

this.root.color = RedBlackTree.BLACK;

}

// 中序遍历

inorder() {

const result = [];

this.inorderHelper(this.root, result);

return result;

}

inorderHelper(node, result) {

if (node !== this.NIL) {

this.inorderHelper(node.left, result);

result.push({

key: node.key,

color: node.color ? 'RED' : 'BLACK'

});

this.inorderHelper(node.right, result);

}

}

// 查找

search(key) {

return this.searchHelper(this.root, key);

}

searchHelper(node, key) {

if (node === this.NIL || key === node.key) {

return node;

}

if (key < node.key) {

return this.searchHelper(node.left, key);

}

return this.searchHelper(node.right, key);

}

}

// 使用示例

// const tree = new RedBlackTree();

// tree.insert(10);

// tree.insert(20);

// tree.insert(30);

// console.log(tree.inorder());

// console.log(tree.search(20) !== tree.NIL ? "找到" : "未找到");

Python 实现

▼Python复制代码class Node:

RED = True

BLACK = False

def __init__(self, key, color=RED):

self.key = key

self.left = None

self.right = None

self.parent = None

self.color = color

class RedBlackTree:

def __init__(self):

self.NIL = Node(key=None, color=Node.BLACK)

self.NIL.left = None

self.NIL.right = None

self.NIL.parent = None

self.root = self.NIL

def left_rotate(self, x):

y = x.right

x.right = y.left

if y.left != self.NIL:

y.left.parent = x

y.parent = x.parent

if x.parent is None:

self.root = y

elif x == x.parent.left:

x.parent.left = y

else:

x.parent.right = y

y.left = x

x.parent = y

def right_rotate(self, y):

x = y.left

y.left = x.right

if x.right != self.NIL:

x.right.parent = y

x.parent = y.parent

if y.parent is None:

self.root = x

elif y == y.parent.left:

y.parent.left = x

else:

y.parent.right = x

x.right = y

y.parent = x

def insert(self, key):

# 创建新节点

node = Node(key)

node.left = self.NIL

node.right = self.NIL

# 找到插入位置

y = None

x = self.root

while x != self.NIL:

y = x

if node.key < x.key:

x = x.left

else:

x = x.right

node.parent = y

if y is None:

self.root = node

elif node.key < y.key:

y.left = node

else:

y.right = node

# 如果新节点是根节点，将其设置为黑色

if node.parent is None:

node.color = Node.BLACK

return

# 如果祖父节点为空，不需要修复

if node.parent.parent is None:

return

# 修复红黑树性质

self.fix_insert(node)

def fix_insert(self, k):

while k.parent and k.parent.color == Node.RED:

if k.parent == k.parent.parent.right:

u = k.parent.parent.left

# 情况1：叔叔是红色

if u.color == Node.RED:

u.color = Node.BLACK

k.parent.color = Node.BLACK

k.parent.parent.color = Node.RED

k = k.parent.parent

else:

# 情况2：k是左子节点

if k == k.parent.left:

k = k.parent

self.right_rotate(k)

# 情况3：k是右子节点

k.parent.color = Node.BLACK

k.parent.parent.color = Node.RED

self.left_rotate(k.parent.parent)

else:

u = k.parent.parent.right

# 情况1：叔叔是红色

if u.color == Node.RED:

u.color = Node.BLACK

k.parent.color = Node.BLACK

k.parent.parent.color = Node.RED

k = k.parent.parent

else:

# 情况2：k是右子节点

if k == k.parent.right:

k = k.parent

self.left_rotate(k)

# 情况3：k是左子节点

k.parent.color = Node.BLACK

k.parent.parent.color = Node.RED

self.right_rotate(k.parent.parent)

if k == self.root:

break

self.root.color = Node.BLACK

def inorder(self):

result = []

self._inorder_helper(self.root, result)

return result

def _inorder_helper(self, node, result):

if node != self.NIL:

self._inorder_helper(node.left, result)

result.append({

'key': node.key,

'color': 'RED' if node.color == Node.RED else 'BLACK'

})

self._inorder_helper(node.right, result)

def search(self, key):

return self._search_helper(self.root, key)

def _search_helper(self, node, key):

if node == self.NIL or key == node.key:

return node

if key < node.key:

return self._search_helper(node.left, key)

return self._search_helper(node.right, key)

# 使用示例

# tree = RedBlackTree()

# tree.insert(10)

# tree.insert(20)

# tree.insert(30)

# print(tree.inorder())

# found = tree.search(20)

# print("找到" if found != tree.NIL else "未找到")

Go 实现

▼Go复制代码package rbtree

// RedBlackTree 红黑树的Go实现

type RedBlackTree struct {

root *Node

nil *Node // 哨兵节点

}

// 颜色常量

const (

RED = true

BLACK = false

)

// Node 树节点定义

type Node struct {

key int

left *Node

right *Node

parent *Node

color bool // true为红，false为黑

}

// NewRedBlackTree 创建新的红黑树

func NewRedBlackTree() *RedBlackTree {

nilNode := &Node{color: BLACK}

return &RedBlackTree{

nil: nilNode,

root: nilNode,

}

}

// colorOf 获取节点颜色，空节点视为黑色

func (t *RedBlackTree) colorOf(node *Node) bool {

if node == t.nil {

return BLACK

}

return node.color

}

// isRed 判断节点是否为红色

func (t *RedBlackTree) isRed(node *Node) bool {

return t.colorOf(node) == RED

}

// isBlack 判断节点是否为黑色

func (t *RedBlackTree) isBlack(node *Node) bool {

return t.colorOf(node) == BLACK

}

// setColor 设置节点颜色

func (t *RedBlackTree) setColor(node *Node, color bool) {

if node != t.nil {

node.color = color

}

}

// leftRotate 左旋操作

func (t *RedBlackTree) leftRotate(x *Node) {

y := x.right // 设置y为x的右子节点

// 将y的左子树设为x的右子树

x.right = y.left

if y.left != t.nil {

y.left.parent = x

}

// 设置y的父节点

y.parent = x.parent

// 设置x的父节点关系

if x.parent == nil {

t.root = y

} else if x == x.parent.left {

x.parent.left = y

} else {

x.parent.right = y

}

// 完成旋转

y.left = x

x.parent = y

}

// rightRotate 右旋操作

func (t *RedBlackTree) rightRotate(y *Node) {

x := y.left // 设置x为y的左子节点

// 将x的右子树设为y的左子树

y.left = x.right

if x.right != t.nil {

x.right.parent = y

}

// 设置x的父节点

x.parent = y.parent

// 设置y的父节点关系

if y.parent == nil {

t.root = x

} else if y == y.parent.left {

y.parent.left = x

} else {

y.parent.right = x

}

// 完成旋转

x.right = y

y.parent = x

}

// Insert 插入节点

func (t *RedBlackTree) Insert(key int) {

node := &Node{

key: key,

color: RED,

left: t.nil,

right: t.nil,

}

var y *Node = nil

x := t.root

// 找到插入位置

for x != t.nil {

y = x

if node.key < x.key {

x = x.left

} else {

x = x.right

}

}

// 设置node的父节点

node.parent = y

// 设置node为根节点或者是父节点的左/右孩子

if y == nil {

t.root = node

} else if node.key < y.key {

y.left = node

} else {

y.right = node

}

// 如果新节点是根节点，则将其设为黑色

if node.parent == nil {

node.color = BLACK

return

}

// 如果新节点的祖父节点为空，则不需要修复

if node.parent.parent == nil {

return

}

// 修复红黑树性质

t.fixInsert(node)

}

// fixInsert 修复插入后的红黑树性质

func (t *RedBlackTree) fixInsert(k *Node) {

var u *Node

for t.isRed(k.parent) {

// 父节点是祖父节点的右子节点

if k.parent == k.parent.parent.right {

u = k.parent.parent.left // 叔叔节点

// 情况1：叔叔节点是红色

if t.isRed(u) {

u.color = BLACK

k.parent.color = BLACK

k.parent.parent.color = RED

k = k.parent.parent

} else {

// 情况2：叔叔节点是黑色，当前节点是左子节点

if k == k.parent.left {

k = k.parent

t.rightRotate(k)

}

// 情况3：叔叔节点是黑色，当前节点是右子节点

k.parent.color = BLACK

k.parent.parent.color = RED

t.leftRotate(k.parent.parent)

}

} else { // 父节点是祖父节点的左子节点

u = k.parent.parent.right // 叔叔节点

// 情况1：叔叔节点是红色

if t.isRed(u) {

u.color = BLACK

k.parent.color = BLACK

k.parent.parent.color = RED

k = k.parent.parent

} else {

// 情况2：叔叔节点是黑色，当前节点是右子节点

if k == k.parent.right {

k = k.parent

t.leftRotate(k)

}

// 情况3：叔叔节点是黑色，当前节点是左子节点

k.parent.color = BLACK

k.parent.parent.color = RED

t.rightRotate(k.parent.parent)

}

}

// 如果k是根节点，退出循环

if k == t.root {

break

}

}

// 确保根节点是黑色

t.root.color = BLACK

}

// minimum 查找最小值节点

func (t *RedBlackTree) minimum(node *Node) *Node {

for node.left != t.nil {

node = node.left

}

return node

}

// transplant 用v替换u

func (t *RedBlackTree) transplant(u, v *Node) {

if u.parent == nil {

t.root = v

} else if u == u.parent.left {

u.parent.left = v

} else {

u.parent.right = v

}

v.parent = u.parent

}

// Delete 删除节点

func (t *RedBlackTree) Delete(key int) {

z := t.search(t.root, key)

if z == t.nil {

return

}

y := z

yOriginalColor := y.color

var x *Node

if z.left == t.nil {

x = z.right

t.transplant(z, z.right)

} else if z.right == t.nil {

x = z.left

t.transplant(z, z.left)

} else {

y = t.minimum(z.right)

yOriginalColor = y.color

x = y.right

if y.parent == z {

x.parent = y

} else {

t.transplant(y, y.right)

y.right = z.right

y.right.parent = y

}

t.transplant(z, y)

y.left = z.left

y.left.parent = y

y.color = z.color

}

// 如果原始颜色是黑色，需要修复

if yOriginalColor == BLACK {

t.fixDelete(x)

}

}

// fixDelete 修复删除后的红黑树性质

func (t *RedBlackTree) fixDelete(x *Node) {

for x != t.root && t.isBlack(x) {

if x == x.parent.left {

w := x.parent.right

// 情况1：兄弟节点是红色

if t.isRed(w) {

w.color = BLACK

x.parent.color = RED

t.leftRotate(x.parent)

w = x.parent.right

}

// 情况2：兄弟节点是黑色，且两个子节点都是黑色

if t.isBlack(w.left) && t.isBlack(w.right) {

w.color = RED

x = x.parent

} else {

// 情况3：兄弟节点是黑色，左子节点是红色，右子节点是黑色

if t.isBlack(w.right) {

w.left.color = BLACK

w.color = RED

t.rightRotate(w)

w = x.parent.right

}

// 情况4：兄弟节点是黑色，右子节点是红色

w.color = x.parent.color

x.parent.color = BLACK

w.right.color = BLACK

t.leftRotate(x.parent)

x = t.root

}

} else { // x是右子节点

w := x.parent.left

// 情况1：兄弟节点是红色

if t.isRed(w) {

w.color = BLACK

x.parent.color = RED

t.rightRotate(x.parent)

w = x.parent.left

}

// 情况2：兄弟节点是黑色，且两个子节点都是黑色

if t.isBlack(w.right) && t.isBlack(w.left) {

w.color = RED

x = x.parent

} else {

// 情况3：兄弟节点是黑色，右子节点是红色，左子节点是黑色

if t.isBlack(w.left) {

w.right.color = BLACK

w.color = RED

t.leftRotate(w)

w = x.parent.left

}

// 情况4：兄弟节点是黑色，左子节点是红色

w.color = x.parent.color

x.parent.color = BLACK

w.left.color = BLACK

t.rightRotate(x.parent)

x = t.root

}

}

}

// 将x设为黑色

x.color = BLACK

}

// search 查找节点

func (t *RedBlackTree) search(root *Node, key int) *Node {

if root == t.nil || key == root.key {

return root

}

if key < root.key {

return t.search(root.left, key)

}

return t.search(root.right, key)

}

// Contains 公开的查找方法

func (t *RedBlackTree) Contains(key int) bool {

return t.search(t.root, key) != t.nil

}

// InorderTraversal 中序遍历

func (t *RedBlackTree) InorderTraversal() []int {

result := []int{}

t.inorder(t.root, &result)

return result

}

func (t *RedBlackTree) inorder(node *Node, result *[]int) {

if node != t.nil {

t.inorder(node.left, result)

*result = append(*result, node.key)

t.inorder(node.right, result)

}

}

// BlackHeight 获取树的黑高

func (t *RedBlackTree) BlackHeight() int {

return t.calculateBlackHeight(t.root)

}

func (t *RedBlackTree) calculateBlackHeight(node *Node) int {

if node == t.nil {

return 0

}

leftHeight := t.calculateBlackHeight(node.left)

rightHeight := t.calculateBlackHeight(node.right)

// 验证左右子树黑高是否相同

if leftHeight != rightHeight {

panic("红黑树属性违反：黑高不相等")

}

// 计算当前节点到叶子节点的黑色节点数

if t.isBlack(node) {

return leftHeight + 1

}

return leftHeight

}

C++ 实现

▼C++复制代码#include

#include

#include

class RedBlackTree {

private:

// 颜色常量

static const bool RED = true;

static const bool BLACK = false;

// 树节点定义

struct Node {

int key; // 节点值

Node* left; // 左子节点

Node* right; // 右子节点

Node* parent; // 父节点

bool color; // 节点颜色（true为红，false为黑）

Node(int key) : key(key), left(nullptr), right(nullptr), parent(nullptr), color(RED) {}

};

Node* root; // 根节点

Node* NIL; // 哨兵节点（表示叶子节点）

// 获取节点颜色，空节点视为黑色

bool colorOf(Node* node) {

return node == NIL ? BLACK : node->color;

}

// 判断节点是否为红色

bool isRed(Node* node) {

return colorOf(node) == RED;

}

// 判断节点是否为黑色

bool isBlack(Node* node) {

return colorOf(node) == BLACK;

}

// 设置节点颜色

void setColor(Node* node, bool color) {

if (node != NIL) {

node->color = color;

}

}

// 左旋操作

void leftRotate(Node* x) {

Node* y = x->right; // 设置y为x的右子节点

// 将y的左子树设为x的右子树

x->right = y->left;

if (y->left != NIL) {

y->left->parent = x;

}

// 设置y的父节点

y->parent = x->parent;

// 设置x的父节点关系

if (x->parent == nullptr) {

root = y;

} else if (x == x->parent->left) {

x->parent->left = y;

} else {

x->parent->right = y;

}

// 完成旋转

y->left = x;

x->parent = y;

}

// 右旋操作

void rightRotate(Node* y) {

Node* x = y->left; // 设置x为y的左子节点

// 将x的右子树设为y的左子树

y->left = x->right;

if (x->right != NIL) {

x->right->parent = y;

}

// 设置x的父节点

x->parent = y->parent;

// 设置y的父节点关系

if (y->parent == nullptr) {

root = x;

} else if (y == y->parent->left) {

y->parent->left = x;

} else {

y->parent->right = x;

}

// 完成旋转

x->right = y;

y->parent = x;

}

// 修复插入后的红黑树性质

void fixInsert(Node* k) {

Node* u;

while (isRed(k->parent)) {

// 父节点是祖父节点的右子节点

if (k->parent == k->parent->parent->right) {

u = k->parent->parent->left; // 叔叔节点

// 情况1：叔叔节点是红色

if (isRed(u)) {

u->color = BLACK;

k->parent->color = BLACK;

k->parent->parent->color = RED;

k = k->parent->parent;

} else {

// 情况2：叔叔节点是黑色，当前节点是左子节点

if (k == k->parent->left) {

k = k->parent;

rightRotate(k);

}

// 情况3：叔叔节点是黑色，当前节点是右子节点

k->parent->color = BLACK;

k->parent->parent->color = RED;

leftRotate(k->parent->parent);

}

} else { // 父节点是祖父节点的左子节点

u = k->parent->parent->right; // 叔叔节点

// 情况1：叔叔节点是红色

if (isRed(u)) {

u->color = BLACK;

k->parent->color = BLACK;

k->parent->parent->color = RED;

k = k->parent->parent;

} else {

// 情况2：叔叔节点是黑色，当前节点是右子节点

if (k == k->parent->right) {

k = k->parent;

leftRotate(k);

}

// 情况3：叔叔节点是黑色，当前节点是左子节点

k->parent->color = BLACK;

k->parent->parent->color = RED;

rightRotate(k->parent->parent);

}

}

// 如果k是根节点，退出循环

if (k == root) {

break;

}

}

// 确保根节点是黑色

root->color = BLACK;

}

// 查找最小值节点

Node* minimum(Node* node) {

while (node->left != NIL) {

node = node->left;

}

return node;

}

// 用v替换u

void transplant(Node* u, Node* v) {

if (u->parent == nullptr) {

root = v;

} else if (u == u->parent->left) {

u->parent->left = v;

} else {

u->parent->right = v;

}

v->parent = u->parent;

}

// 修复删除后的红黑树性质

void fixDelete(Node* x) {

while (x != root && isBlack(x)) {

if (x == x->parent->left) {

Node* w = x->parent->right;

// 情况1：兄弟节点是红色

if (isRed(w)) {

w->color = BLACK;

x->parent->color = RED;

leftRotate(x->parent);

w = x->parent->right;

}

// 情况2：兄弟节点是黑色，且两个子节点都是黑色

if (isBlack(w->left) && isBlack(w->right)) {

w->color = RED;

x = x->parent;

} else {

// 情况3：兄弟节点是黑色，左子节点是红色，右子节点是黑色

if (isBlack(w->right)) {

w->left->color = BLACK;

w->color = RED;

rightRotate(w);

w = x->parent->right;

}

// 情况4：兄弟节点是黑色，右子节点是红色

w->color = x->parent->color;

x->parent->color = BLACK;

w->right->color = BLACK;

leftRotate(x->parent);

x = root;

}

} else { // x是右子节点

Node* w = x->parent->left;

// 情况1：兄弟节点是红色

if (isRed(w)) {

w->color = BLACK;

x->parent->color = RED;

rightRotate(x->parent);

w = x->parent->left;

}

// 情况2：兄弟节点是黑色，且两个子节点都是黑色

if (isBlack(w->right) && isBlack(w->left)) {

w->color = RED;

x = x->parent;

} else {

// 情况3：兄弟节点是黑色，右子节点是红色，左子节点是黑色

if (isBlack(w->left)) {

w->right->color = BLACK;

w->color = RED;

leftRotate(w);

w = x->parent->left;

}

// 情况4：兄弟节点是黑色，左子节点是红色

w->color = x->parent->color;

x->parent->color = BLACK;

w->left->color = BLACK;

rightRotate(x->parent);

x = root;

}

}

}

// 将x设为黑色

x->color = BLACK;

}

// 查找节点

Node* search(Node* root, int key) {

if (root == NIL || key == root->key) {

return root;

}

if (key < root->key) {

return search(root->left, key);

} else {

return search(root->right, key);

}

}

// 中序遍历

void inorder(Node* node, std::vector& result) {

if (node != NIL) {

inorder(node->left, result);

result.push_back(node->key);

inorder(node->right, result);

}

}

// 计算黑高

int calculateBlackHeight(Node* node) {

if (node == NIL) {

return 0;

}

int leftHeight = calculateBlackHeight(node->left);

int rightHeight = calculateBlackHeight(node->right);

// 验证左右子树黑高是否相同

if (leftHeight != rightHeight) {

throw std::runtime_error("红黑树属性违反：黑高不相等");

}

// 计算当前节点到叶子节点的黑色节点数

return isBlack(node) ? leftHeight + 1 : leftHeight;

}

// 清理内存

void destroyTree(Node* node) {

if (node != NIL) {

destroyTree(node->left);

destroyTree(node->right);

delete node;

}

}

public:

// 构造函数

RedBlackTree() {

NIL = new Node(0);

NIL->color = BLACK;

NIL->left = nullptr;

NIL->right = nullptr;

root = NIL;

}

// 析构函数

~RedBlackTree() {

destroyTree(root);

delete NIL;

}

// 插入节点

void insert(int key) {

Node* node = new Node(key);

node->left = NIL;

node->right = NIL;

Node* y = nullptr;

Node* x = this->root;

// 找到插入位置

while (x != NIL) {

y = x;

if (node->key < x->key) {

x = x->left;

} else {

x = x->right;

}

}

// 设置node的父节点

node->parent = y;

// 设置node为根节点或者是父节点的左/右孩子

if (y == nullptr) {

root = node;

} else if (node->key < y->key) {

y->left = node;

} else {

y->right = node;

}

// 如果新节点是根节点，则将其设为黑色

if (node->parent == nullptr) {

node->color = BLACK;

return;

}

// 如果新节点的祖父节点为空，则不需要修复

if (node->parent->parent == nullptr) {

return;

}

// 修复红黑树性质

fixInsert(node);

}

// 删除节点

void remove(int key) {

Node* z = search(root, key);

if (z == NIL) {

std::cout << "Key " << key << " not found in the tree" << std::endl;

return;

}

Node* y = z;

Node* x;

bool yOriginalColor = y->color;

if (z->left == NIL) {

x = z->right;

transplant(z, z->right);

} else if (z->right == NIL) {

x = z->left;

transplant(z, z->left);

} else {

y = minimum(z->right);

yOriginalColor = y->color;

x = y->right;

if (y->parent == z) {

x->parent = y;

} else {

transplant(y, y->right);

y->right = z->right;

y->right->parent = y;

}

transplant(z, y);

y->left = z->left;

y->left->parent = y;

y->color = z->color;

}

delete z;

// 如果原始颜色是黑色，需要修复

if (yOriginalColor == BLACK) {

fixDelete(x);

}

}

// 查找是否包含某值

bool contains(int key) {

return search(root, key) != NIL;

}

// 中序遍历

std::vector inorderTraversal() {

std::vector result;

inorder(root, result);

return result;

}

// 获取树的黑高

int blackHeight() {

return calculateBlackHeight(root);

}

// 打印中序遍历结果（包含颜色信息）

void printInorder() {

printInorderWithColor(root);

std::cout << std::endl;

}

private:

void printInorderWithColor(Node* node) {

if (node != NIL) {

printInorderWithColor(node->left);

std::cout << node->key << (node->color == RED ? "(R) " : "(B) ");

printInorderWithColor(node->right);

}

}

};

这两个实现与Java版本保持一致的功能：

均包含插入、删除、查找操作

插入和删除后的红黑树性质修复

左旋和右旋操作

中序遍历

黑高计算

Go版本使用了更符合Go语言习惯的结构，包括导出方法的大写命名和返回错误而非抛出异常。C++版本增加了内存管理（析构函数）以避免内存泄漏。两个实现都遵循了对应语言的代码风格和习惯。

优缺点

优点

查找效率高：O(log n)的查找、插入和删除操作时间复杂度

自平衡：通过颜色规则和旋转操作自动维持平衡

插入删除效率：比AVL树需要更少的旋转操作，平均性能更好

内存占用少：每个节点只需额外一个比特存储颜色信息

实际应用广泛：被广泛用于实际系统中，比如Java TreeMap、C++ STL中的map/set等

缺点

实现复杂：规则多，调整操作复杂，实现难度大

删除操作尤其复杂：需要处理多种情况的平衡修复

不严格平衡：虽然路径长度不会超过最短路径的两倍，但比AVL树的平衡性稍差

旋转操作开销：虽然比AVL树少，但仍有调整开销

应用场景

红黑树在众多系统和场景中有广泛应用，其平衡性能和实现效率使其成为许多高性能应用的首选数据结构。

在操作系统内核中，红黑树经常被用于实现各种调度器和资源管理器。例如，Linux内核使用红黑树来管理进程调度、内存管理和文件系统中的目录结构，它能在保持较好平衡的同时减少重新平衡操作的频率。

许多高级编程语言的标准库也选择红黑树作为有序映射和集合的底层实现。Java中的TreeMap和TreeSet，C++的std::map和std::set，以及C#的SortedDictionary等，都基于红黑树实现。这些数据结构需要保持元素的有序性，同时又要求高效的查找、插入和删除操作，这些需求红黑树都满足。

扩展：与AVL树的比较

平衡性：AVL树的平衡条件更严格，要求任何节点的左右子树高度差不超过1，而红黑树允许左右子树的"黑高度"相同，但整体高度可能相差两倍。

旋转频率：AVL树为了维持严格平衡，在插入和删除操作中可能需要更多的旋转操作，而红黑树由于平衡条件较为宽松，通常需要的旋转次数更少。

使用场景：

AVL树更适合读操作频繁、写操作较少的场景

红黑树更适合写操作频繁的场景，如频繁的插入、删除操作

实际应用：

大多数语言的标准库实现（如Java的TreeMap、C++的map）采用红黑树

数据库索引通常偏向使用B树或B+树，这些是AVL树和红黑树思想的多路扩展

测验

1）红黑树的五个基本性质是什么？哪一条保证了树的高度是O(log n)？

2）在红黑树中插入一个新节点后，可能会违反哪些红黑树性质？初始默认将新节点设置为什么颜色？

3）在红黑树中，如果一个节点的叔叔节点是红色，在插入修复过程中通常采取什么操作？

4）红黑树相比AVL树，在执行插入操作时平均需要的旋转次数更多还是更少？为什么？

测验答案

1）红黑树的五个基本性质是：

每个节点或是红色，或是黑色

根节点必须是黑色

所有叶子节点（NIL节点）都是黑色

如果一个节点是红色，则其两个子节点都是黑色

对于每个节点，从该节点到其所有后代叶子节点的路径上，包含相同数量的黑色节点

第五条性质结合第四条性质保证了树的高度是O(log n)，因为它限制了任何路径上黑色节点数量相同，且不能有连续的红色节点，因此最长路径不会超过最短路径的两倍。

2）插入新节点后可能违反的性质主要是：

性质2：如果新节点成为根，但它是红色

性质4：如果新节点是红色，且其父节点也是红色

在红黑树中，新插入的节点默认设置为红色，这样可以减少违反性质5的可能性。

3）当一个节点的叔叔节点是红色时，插入修复过程通常采取颜色翻转操作：

将父节点设为黑色

将叔叔节点设为黑色

将祖父节点设为红色（如果祖父是根节点，则最后重新设为黑色）

4）更少。AVL树要求更严格的平衡（左右子树高度差不超过1），因此在插入时可能需要多次旋转来维持平衡。而红黑树的平衡条件较为宽松，允许树有一定程度的不平衡，所以在插入和删除时需要的旋转操作通常更少，这也是红黑树在实际应用中更常用的原因之一。

相关LeetCode热门题目

虽然LeetCode上没有直接要求实现红黑树的题目，但以下题目涉及到平衡树和二叉搜索树的概念，可以帮助大家的深入理解：

1382. 将二叉搜索树变平衡 - 将一个不平衡的BST转换为平衡的BST

701. 二叉搜索树中的插入操作 - 实现BST的插入操作

450. 删除二叉搜索树中的节点 - 实现BST的删除操作

235. 二叉搜索树的最近公共祖先

红黑树是一种应用广泛的高效自平衡二叉搜索树，虽然实现较为复杂，但其在实际系统中的应用比较广泛。通过学习红黑树，可以更深入地理解数据结构的平衡性与性能之间的权衡，以及如何通过巧妙的规则设计来实现高效的数据结构。