java红黑树实现代码怎么写

46次阅读

共计 2166 个字符，预计需要花费 6 分钟才能阅读完成。

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

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