How to implement red-black tree algorithm using java

How to use Java to implement the red-black tree algorithm

The red-black tree is a self-balancing binary search tree that is used in many high-performance data structures and algorithms. being widely used. This article will introduce in detail how to implement the red-black tree algorithm using Java language and give specific code examples.

1. The definition of red-black tree

The red-black tree is a binary search tree, which has the following characteristics:

1. Each node has a Color, either red or black;
2. The root node is black;
3. Each leaf node (NIL node, that is, an empty node) is black;
4. If a node is red, then its two child nodes are black;
5. For each node, the simple path from the node to all its descendant leaf nodes contains the same number of black node.

These features ensure the balance of the red-black tree, keeping the height of the tree at the O(log n) level.

2. Basic operations of red-black tree

Red-black tree mainly includes the following basic operations:

1. Insertion: Insert a node into the red-black tree , the characteristics of the red-black tree need to be maintained;
2. Delete: Delete a node from the red-black tree, the characteristics of the red-black tree need to be maintained;
3. Search: Find a specified node in the red-black tree node;
4. Insertion repair: The characteristics of the red-black tree may be damaged due to insertion, and need to be repaired through a series of operations;
5. Delete repair: The characteristics of the red-black tree may be damaged due to deletion, It needs to be repaired through a series of operations.

The following is a code example of using Java language to implement a red-black tree:

// 定义红黑树节点类
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("没有找到节点");
        }
    }
}

The output result of running the test code is: "Node found: 50", indicating that the red-black tree Both insert and search operations work fine.

Compile and run the above code as a Java class file to realize the insertion and search operations of the red-black tree. We can also add deletion operations and deletion repair code as needed.

Summary:

This article introduces the definition and basic operations of red-black trees, and gives code examples for using Java to implement red-black trees. As a self-balancing binary search tree, the red-black tree plays an important role in processing large amounts of data and high-performance algorithms. Mastering the principles and implementation of red-black trees will help us better understand the design and application of data structures and algorithms. Hope this article is helpful to readers.

The above is the detailed content of How to implement red-black tree algorithm using java. For more information, please follow other related articles on the PHP Chinese website!