Java数据结构与算法(红黑树)

前言

红黑树是一种自平衡二叉搜索树，确保在插入和删除操作后，树的高度保持平衡，从而保证基本操作（插入、删除、查找）的时间复杂度为O(log n)。

实现原理

红黑树具有以下性质：

1. 每个节点要么是红色，要么是黑色。
2. 根节点是黑色的。
3. 每个叶子节点（NIL节点，通常是空节点）是黑色的。
4. 如果一个节点是红色的，则它的两个子节点都是黑色的。
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

动画过程

Red/Black Tree Visualization

具体代码实现

public class RedBlackTree {private static final boolean RED = false;private static final boolean BLACK = true;private class Node {int key;Node left, right, parent;boolean color;Node(int key, boolean color, Node parent) {this.key = key;this.color = color;this.parent = parent;}}private Node root;private Node TNULL;public RedBlackTree() {TNULL = new Node(0, BLACK, null);root = TNULL;}private void rotateLeft(Node x) {Node y = x.right;x.right = y.left;if (y.left != TNULL) {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;}private void rotateRight(Node x) {Node y = x.left;x.left = y.right;if (y.right != TNULL) {y.right.parent = x;}y.parent = x.parent;if (x.parent == null) {this.root = y;} else if (x == x.parent.right) {x.parent.right = y;}y.right = x;x.parent = y;}private void insertFix(Node k) {Node u;while (k.parent.color == RED) {if (k.parent == k.parent.parent.left) {u = k.parent.parent.right;if (u.color == RED) {u.color = BLACK;k.parent.color = BLACK;k.parent.parent.color = RED;k = k.parent.parent;} else {if (k == k.parent.right) {k = k.parent;rotateLeft(k);}k.parent.color = BLACK;k.parent.parent.color = RED;rotateRight(k.parent.parent);}} else {u = k.parent.parent.left;if (u.color == RED) {u.color = BLACK;k.parent.color = BLACK;k.parent.parent.color = RED;k = k.parent.parent;} else {if (k == k.parent.left) {k = k.parent;rotateRight(k);}k.parent.color = BLACK;k.parent.parent.color = RED;rotateLeft(k.parent.parent);}}if (k == root) {break;}}root.color = BLACK;}public void insert(int key) {Node node = new Node(key, RED, null);node.left = TNULL;node.right = TNULL;Node y = null;Node x = this.root;while (x != TNULL) {y = x;if (node.key < x.key) {x = x.left;} else {x = x.right;}}node.parent = y;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;}insertFix(node);}public Node search(int key) {return searchTreeHelper(this.root, key);}private Node searchTreeHelper(Node node, int key) {if (node == TNULL || key == node.key) {return node;}if (key < node.key) {return searchTreeHelper(node.left, key);}return searchTreeHelper(node.right, key);}public void printTree() {printHelper(this.root, "", true);}private void printHelper(Node root, String indent, boolean last) {if (root != TNULL) {System.out.print(indent);if (last) {System.out.print("R----");indent += "   ";} else {System.out.print("L----");indent += "|  ";}String sColor = root.color == RED ? "RED" : "BLACK";System.out.println(root.key + "(" + sColor + ")");printHelper(root.left, indent, false);printHelper(root.right, indent, true);}}public static void main(String[] args) {RedBlackTree tree = new RedBlackTree();tree.insert(55);tree.insert(40);tree.insert(65);tree.insert(60);tree.insert(75);tree.insert(57);tree.printTree();}
}

QA:待定