Implementation of redblacktree insertion in Java
•
Java
I am trying to implement the CLRs pseudo code of red black tree NullPointerException is thrown when I try to run the program Please look at the code and find the error Any further suggestions are welcome
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 is:
Solution
You must initialize nil and root:
public class RedBlackTree { Node nil; <-- is null Node root; <-- is null
Otherwise, this is also null:
while (z.parent.color == RED) { <-- z.parent is null
The content of this article comes from the network collection of netizens. It is used as a learning reference. The copyright belongs to the original author.
THE END
二维码