Java红黑树实现：详解插入操作与代码示例

红黑树是一种自平衡二叉搜索树，在计算机科学中有着广泛的应用，例如用于实现关联数组、集合等数据结构。本文将介绍如何使用Java实现红黑树，并提供详细的代码示例，包括插入、左旋、右旋操作以及中序遍历等关键概念。

红黑树的性质

红黑树是满足以下性质的二叉搜索树：

每个节点要么是红色，要么是黑色。2. 根节点是黑色的。3. 所有叶子节点（NIL节点）都是黑色的。4. 如果一个节点是红色的，那么它的两个子节点都是黑色的。5. 对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点。

Java代码实现

以下是使用Java编写的红黑树的示例代码：java// 定义红黑树节点的颜色enum Color { RED, BLACK}

// 定义红黑树节点class Node { int data; Color color; Node left; Node right; Node parent; public Node(int data) { this.data = data; this.color = Color.RED; this.left = null; this.right = null; this.parent = null; }}

// 定义红黑树class RedBlackTree { private Node root; public RedBlackTree() { this.root = null; } // 左旋操作 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) { 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 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) { this.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 current = this.root; Node parent = null; while (current != null) { parent = current; if (data < current.data) { current = current.left; } else { current = current.right; } } newNode.parent = parent; if (parent == null) { this.root = newNode; } else if (data < parent.data) { parent.left = newNode; } else { parent.right = newNode; } fixInsert(newNode); } // 插入后修复红黑树性质 private void fixInsert(Node x) { while (x != root && x.parent.color == Color.RED) { if (x.parent == x.parent.parent.left) { Node y = x.parent.parent.right; if (y != null && y.color == Color.RED) { x.parent.color = Color.BLACK; y.color = Color.BLACK; x.parent.parent.color = Color.RED; x = x.parent.parent; } else { if (x == x.parent.right) { x = x.parent; leftRotate(x); } x.parent.color = Color.BLACK; x.parent.parent.color = Color.RED; rightRotate(x.parent.parent); } } else { Node y = x.parent.parent.left; if (y != null && y.color == Color.RED) { x.parent.color = Color.BLACK; y.color = Color.BLACK; x.parent.parent.color = Color.RED; x = x.parent.parent; } else { if (x == x.parent.left) { x = x.parent; rightRotate(x); } x.parent.color = Color.BLACK; x.parent.parent.color = Color.RED; leftRotate(x.parent.parent); } } } root.color = Color.BLACK; } // 中序遍历红黑树 private void inorderTraversal(Node node) { if (node != null) { inorderTraversal(node.left); System.out.print(node.data + ' '); inorderTraversal(node.right); } } public void inorderTraversal() { inorderTraversal(this.root); System.out.println(); }}

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); tree.inorderTraversal(); // 输出：10 20 30 40 50 60 70 }}

代码解析

节点定义javaclass Node { int data; // 节点数据 Color color; // 节点颜色 Node left; // 左子节点 Node right; // 右子节点 Node parent; // 父节点 // 构造函数 public Node(int data) { this.data = data; this.color = Color.RED; // 新插入的节点默认为红色 this.left = null; this.right = null; this.parent = null; }}

每个节点存储数据、颜色、左子节点、右子节点和父节点的引用。

左旋和右旋

左旋和右旋操作是维护红黑树平衡的关键操作。

左旋(leftRotate)：将一个节点向左旋转，使其右子节点成为新的父节点。- 右旋(rightRotate)：将一个节点向右旋转，使其左子节点成为新的父节点。

插入操作

插入操作包括以下步骤：

找到新节点的插入位置。2. 将新节点插入到树中，并将新节点的颜色设置为红色。3. 调用fixInsert方法修复红黑树的性质。

fixInsert方法

fixInsert方法用于在插入新节点后修复红黑树的性质。该方法通过以下几种情况进行处理：

**情况1：**新节点的父节点是黑色的，不需要进行任何操作。- **情况2：**新节点的父节点是红色的，且新节点的叔叔节点也是红色的。将父节点和叔叔节点的颜色设置为黑色，将祖父节点的颜色设置为红色，并将新节点指向祖父节点继续向上处理。- **情况3：**新节点的父节点是红色的，且新节点的叔叔节点是黑色的（或为空）。根据新节点与其父节点的相对位置进行左旋或右旋操作，并将相关节点的颜色进行调整，以维护红黑树的性质。

总结

本文介绍了如何使用Java实现红黑树，并提供了详细的代码示例，包括插入、左旋、右旋操作以及中序遍历等关键概念。希望本文能够帮助你理解和掌握红黑树的构建和使用。