前言

紅黑樹是一種自平衡二叉搜索樹，確保在插入和刪除操作后，樹的高度保持平衡，從而保證基本操作（插入、刪除、查找）的時(shí)間復(fù)雜度為O(log n)。

實(shí)現(xiàn)原理

紅黑樹具有以下性質(zhì)：

1. 每個(gè)節(jié)點(diǎn)要么是紅色，要么是黑色。
2. 根節(jié)點(diǎn)是黑色的。
3. 每個(gè)葉子節(jié)點(diǎn)（NIL節(jié)點(diǎn)，通常是空節(jié)點(diǎn)）是黑色的。
4. 如果一個(gè)節(jié)點(diǎn)是紅色的，則它的兩個(gè)子節(jié)點(diǎn)都是黑色的。
5. 從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。

動(dòng)畫過程

Red/Black Tree Visualization

具體代碼實(shí)現(xiàn)

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:待定