红黑树是一种自平衡的二叉搜索树,通过节点颜色和旋转操作保持树的平衡。它通过确保没有一条路径会比其他路径长两倍来保证查找、插入和删除操作的时间复杂度为O(log n)。
红黑树是一种自平衡二叉搜索树,最初被称为"对称二叉B树",后来改名为红黑树。因为在每个节点上都增加了一个表示颜色的属性,可以是红色或黑色。红黑树通过着色规则和特定的重新平衡操作(旋转和重新着色)来保持树的平衡。
红黑树中的几个关键概念:
红黑树必须满足以下五个性质:
这些规则保证了红黑树的关键特性:
▼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复制代码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复制代码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复制代码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++复制代码#include <iostream> #include <stdexcept> #include <vector> 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<int>& 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<int> inorderTraversal() { std::vector<int> 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++版本增加了内存管理(析构函数)以避免内存泄漏。两个实现都遵循了对应语言的代码风格和习惯。
红黑树在众多系统和场景中有广泛应用,其平衡性能和实现效率使其成为许多高性能应用的首选数据结构。
在操作系统内核中,红黑树经常被用于实现各种调度器和资源管理器。例如,Linux内核使用红黑树来管理进程调度、内存管理和文件系统中的目录结构,它能在保持较好平衡的同时减少重新平衡操作的频率。
许多高级编程语言的标准库也选择红黑树作为有序映射和集合的底层实现。Java中的TreeMap和TreeSet,C++的std::map和std::set,以及C#的SortedDictionary等,都基于红黑树实现。这些数据结构需要保持元素的有序性,同时又要求高效的查找、插入和删除操作,这些需求红黑树都满足。
1)红黑树的五个基本性质是什么?哪一条保证了树的高度是O(log n)?
2)在红黑树中插入一个新节点后,可能会违反哪些红黑树性质?初始默认将新节点设置为什么颜色?
3)在红黑树中,如果一个节点的叔叔节点是红色,在插入修复过程中通常采取什么操作?
4)红黑树相比AVL树,在执行插入操作时平均需要的旋转次数更多还是更少?为什么?
测验答案
1)红黑树的五个基本性质是:
- 每个节点或是红色,或是黑色
- 根节点必须是黑色
- 所有叶子节点(NIL节点)都是黑色
- 如果一个节点是红色,则其两个子节点都是黑色
- 对于每个节点,从该节点到其所有后代叶子节点的路径上,包含相同数量的黑色节点
第五条性质结合第四条性质保证了树的高度是O(log n),因为它限制了任何路径上黑色节点数量相同,且不能有连续的红色节点,因此最长路径不会超过最短路径的两倍。
2)插入新节点后可能违反的性质主要是:
- 性质2:如果新节点成为根,但它是红色
- 性质4:如果新节点是红色,且其父节点也是红色
在红黑树中,新插入的节点默认设置为红色,这样可以减少违反性质5的可能性。
3)当一个节点的叔叔节点是红色时,插入修复过程通常采取颜色翻转操作:
- 将父节点设为黑色
- 将叔叔节点设为黑色
- 将祖父节点设为红色(如果祖父是根节点,则最后重新设为黑色)
4)更少。AVL树要求更严格的平衡(左右子树高度差不超过1),因此在插入时可能需要多次旋转来维持平衡。而红黑树的平衡条件较为宽松,允许树有一定程度的不平衡,所以在插入和删除时需要的旋转操作通常更少,这也是红黑树在实际应用中更常用的原因之一。
虽然LeetCode上没有直接要求实现红黑树的题目,但以下题目涉及到平衡树和二叉搜索树的概念,可以帮助大家的深入理解:
红黑树是一种应用广泛的高效自平衡二叉搜索树,虽然实现较为复杂,但其在实际系统中的应用比较广泛。通过学习红黑树,可以更深入地理解数据结构的平衡性与性能之间的权衡,以及如何通过巧妙的规则设计来实现高效的数据结构。