Javaを使用して赤黒ツリーアルゴリズムを実装する方法

// 定义红黑树节点类 class Node { int key; Node parent; Node left; Node right; boolean isRed; // 红色节点为true，黑色节点为false public Node(int key) { this.key = key; this.parent = null; this.left = null; this.right = null; this.isRed = true; // 默认插入的节点为红色节点 } } // 定义红黑树类 class RedBlackTree { private Node root; private final Node NIL; public RedBlackTree() { NIL = new Node(-1); // 定义一个表示NIL节点的对象 NIL.isRed = false; // NIL节点为黑色节点 root = NIL; } // 插入节点 public void insert(int key) { Node node = new Node(key); Node current = root; Node parent = null; while (current != NIL) { parent = current; if (key < current.key) { current = current.left; } else { current = current.right; } } node.parent = parent; if (parent == null) { root = node; } else if (key < parent.key) { parent.left = node; } else { parent.right = node; } node.left = NIL; node.right = NIL; node.isRed = true; insertFixup(node); } // 插入修复 private void insertFixup(Node node) { while (node.parent.isRed) { if (node.parent == node.parent.parent.left) { Node uncle = node.parent.parent.right; if (uncle.isRed) { // Case 1: 叔节点为红色 node.parent.isRed = false; uncle.isRed = false; node.parent.parent.isRed = true; node = node.parent.parent; } else { if (node == node.parent.right) { node = node.parent; leftRotate(node); } node.parent.isRed = false; node.parent.parent.isRed = true; rightRotate(node.parent.parent); } } else { Node uncle = node.parent.parent.left; if (uncle.isRed) { // Case 1: 叔节点为红色 node.parent.isRed = false; uncle.isRed = false; node.parent.parent.isRed = true; node = node.parent.parent; } else { if (node == node.parent.left) { node = node.parent; rightRotate(node); } node.parent.isRed = false; node.parent.parent.isRed = true; leftRotate(node.parent.parent); } } } root.isRed = false; } // 左旋转 private void leftRotate(Node node) { Node child = node.right; node.right = child.left; if (child.left != NIL) { child.left.parent = node; } child.parent = node.parent; if (node.parent == NIL) { root = child; } else if (node == node.parent.left) { node.parent.left = child; } else { node.parent.right = child; } child.left = node; node.parent = child; } // 右旋转 private void rightRotate(Node node) { Node child = node.left; node.left = child.right; if (child.right != NIL) { child.right.parent = node; } child.parent = node.parent; if (node.parent == NIL) { root = child; } else if (node == node.parent.right) { node.parent.right = child; } else { node.parent.left = child; } child.right = node; node.parent = child; } // 查找节点 public Node search(int key) { Node current = root; while (current != NIL && key != current.key) { if (key < current.key) { current = current.left; } else { current = current.right; } } return current; } } // 测试红黑树的代码 public class Main { public static void main(String[] args) { RedBlackTree tree = new RedBlackTree(); tree.insert(10); tree.insert(20); tree.insert(30); tree.insert(40); tree.insert(50); tree.insert(60); tree.insert(70); Node node = tree.search(50); if (node != tree.NIL) { System.out.println("找到了节点：" + node.key); } else { System.out.println("没有找到节点"); } } }