阅读量:2
以下是一个简单的红黑树实现代码示例：
class Node { int data; Node left, right, parent; boolean color; // true表示红色，false表示黑色 public Node(int data) { this.data = data; this.color = true; // 新插入的节点默认为红色 this.left = this.right = this.parent = null; } } public class RedBlackTree { private Node root; // 红黑树左旋转 private void leftRotate(Node x) { Node y = x.right; x.right = y.left; if (y.left != null) { y.left.parent = x; } y.parent = x.parent; 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 x) { Node y = x.left; x.left = y.right; if (y.right != null) { y.right.parent = x; } y.parent = x.parent; if (x.parent == null) { root = y; } else if (x == x.parent.right) { x.parent.right = y; } else { x.parent.left = y; } y.right = x; x.parent = y; } // 红黑树插入 public void insert(int data) { Node newNode = new Node(data); Node parent = null; Node current = root; while (current != null) { parent = current; if (data < current.data) { current = current.left; } else { current = current.right; } } newNode.parent = parent; if (parent == null) { root = newNode; } else if (data < parent.data) { parent.left = newNode; } else { parent.right = newNode; } insertFixUp(newNode); } // 红黑树插入修正 private void insertFixUp(Node x) { while (x != root && x.parent.color == true) { if (x.parent == x.parent.parent.left) { Node y = x.parent.parent.right; if (y != null && y.color == true) { x.parent.color = false; y.color = false; x.parent.parent.color = true; x = x.parent.parent; } else { if (x == x.parent.right) { x = x.parent; leftRotate(x); } x.parent.color = false; x.parent.parent.color = true; rightRotate(x.parent.parent); } } else { Node y = x.parent.parent.left; if (y != null && y.color == true) { x.parent.color = false; y.color = false; x.parent.parent.color = true; x = x.parent.parent; } else { if (x == x.parent.left) { x = x.parent; rightRotate(x); } x.parent.color = false; x.parent.parent.color = true; leftRotate(x.parent.parent); } } } root.color = false; } // 中序遍历打印红黑树 public void inorderTraversal(Node node) { if (node != null) { inorderTraversal(node.left); System.out.print(node.data + " "); inorderTraversal(node.right); } } public static void main(String[] args) { RedBlackTree rbTree = new RedBlackTree(); rbTree.insert(7); rbTree.insert(3); rbTree.insert(18); rbTree.insert(10); rbTree.insert(22); rbTree.insert(8); rbTree.insert(11); rbTree.inorderTraversal(rbTree.root); } } 以上是一个简单的红黑树实现，包含了插入和修正操作。您可以根据需要进行进一步扩展和优化。
