Java中的RedBlackTree插入实现

发布时间：2020-12-15 02:10:40 所属栏目：Java 来源：网络整理

导读：我正在尝试实现红黑树的CLRS伪代码.当我尝试运行该程序时,抛出NullPointerException.请查看代码并找出其中的错误.欢迎任何进一步的建议. public class RedBlackTree {Node nil;Node root;String RED = "red";String BLACK = "black";public void left_rotate

我正在尝试实现红黑树的CLRS伪代码.当我尝试运行该程序时,抛出NullPointerException.请查看代码并找出其中的错误.欢迎任何进一步的建议.

public class RedBlackTree {

Node nil;
Node root;
String RED = "red";
String BLACK = "black";

public void left_rotate(RedBlackTree T,Node x) {
    Node y = x.right;
    x.right = y.left;
    if (y.left != T.nil)
        y.left.parent = x;
    y.parent = x.parent;
    if (x.parent == T.nil)
        T.root = y;
    else if (x == x.parent.left)
        x.parent.left = y;
    else
        x.parent.right = y;
    y.left = x;
    x.parent = y;
}

public void right_rotate(RedBlackTree T,Node x) {
    Node y = x.left;
    x.left = y.right;
    if (y.right != T.nil)
        y.right.parent = x;
    y.parent = x.parent;
    if (x.parent == T.nil)
        T.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 rb_insert_fixup(RedBlackTree T,Node z) {

    while (z.parent.color == RED) {
        if (z.parent == z.parent.parent.left) {
            Node y = z.parent.parent.right;
            if (y.color == RED) {
                z.parent.color = BLACK;
                y.color = BLACK;
                z.parent.parent.color = RED;
                z = z.parent.parent;
            } else {
                if (z == z.parent.right) {
                    z = z.parent;
                    left_rotate(T,z);
                }
                z.parent.color = BLACK;
                z.parent.parent.color = RED;
                right_rotate(T,z.parent.parent);
            }
        } else {
            Node y = z.parent.parent.left;
            if (y.color == RED) {
                z.parent.color = BLACK;
                y.color = BLACK;
                z.parent.parent.color = RED;
                z = z.parent.parent;
            } else {
                if (z == z.parent.left) {

                    z = z.parent;
                    right_rotate(T,z);
                }
                z.parent.color = BLACK;
                z.parent.parent.color = RED;
                left_rotate(T,z.parent.parent);
            }
        }

    }
    T.root.color = BLACK;
}

public void insert(RedBlackTree T,Node z) {
    Node y = T.nil;
    Node x = T.root;
    while (x != T.nil) {
        y = x;
        if (z.key < x.key)
            x = x.left;
        else
            x = x.right;
    }
    z.parent = y;
    if (y == T.nil)
        T.root = z;
    else if (z.key < y.key)
        y.left = z;
    else
        y.right = z;
    z.left = T.nil;
    z.right = T.nil;
    z.color = RED;
    rb_insert_fixup(T,z);
}

public void inorder_tree_walk(Node x) {
    if (x != null) {
        inorder_tree_walk(x.left);
        System.out.println(x.key + ":" + x.color + " ");
        inorder_tree_walk(x.right);
    }
}

public static void main(String[] args) {
    RedBlackTree rbt = new RedBlackTree();

    Node a = new Node(12,"a");
    rbt.insert(rbt,a);
    Node b = new Node(5,"b");
    rbt.insert(rbt,b);
    Node c = new Node(18,"c");
    rbt.insert(rbt,c);
    Node d = new Node(2,"d");
    rbt.insert(rbt,d);
    Node e = new Node(9,"e");
    rbt.insert(rbt,e);

    rbt.inorder_tree_walk(rbt.root);
    }

}

class Node {
int key;
String data;
String color;
Node left,right,parent;

public Node(int key,String data) {
    this.key = key;
    this.data = data;
    }
}

StackTrace是：

Exception in thread “main” java.lang.NullPointerException
at RedBlackTree.rb_insert_fixup(RedBlackTree.java:42)
at RedBlackTree.insert(RedBlackTree.java:102)
at RedBlackTree.main(RedBlackTree.java:117)

解决方法

你必须初始化nil和root：

public class RedBlackTree {

Node nil;  <-- is null
Node root; <-- is null

否则,这也是null：

while (z.parent.color == RED) { <-- z.parent is null

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!