java红黑树实现代码怎么写

以下是一个简单的红黑树实现代码示例：

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);}}

以上是一个简单的红黑树实现，包含了插入和修正操作。您可以根据需要进行进一步扩展和优化。

上一篇：Delphi中怎么创建一个新项目

下一篇：Postman中怎么使用集合来组织请求