我在编写红黑树删除函数（带有哨兵）时遇到了麻烦。
经过数小时的故障排除后，我得出的结论是，问题出现在以下步骤中：
插入 14、11、7 和 8，然后删除 11（即根）。
11 被替换为没有孩子的 14。然后，x（参见代码）获取 NULL 节点的值 - 这使得 x.parent 之类的函数变得毫无意义（对吗？）
然后程序在一个空异常中停止。
有什么想法有什么问题吗？
*我希望我已经把自己说清楚了——如果不是，我很乐意提供更多信息。
谢谢！
整个相关代码：
public class RBTree {
private RBNode DUMMYROOT;
private RBNode NULL;
private int numOfNodes;
public RBTree() {
this.numOfNodes=0;
this.NULL = new RBNode();
this.DUMMYROOT = new RBNode();
this.DUMMYROOT.setKey(Double.POSITIVE_INFINITY);
this.DUMMYROOT.setLeftChild(NULL);
this.DUMMYROOT.setColor("black");
this.NULL.setColor("black");
}
public RBNode getNULL() {
return this.NULL;
}
/**
* public boolean empty()
*
* returns true if and only if the tree is empty
*
*/
public boolean empty() {
if (this.numOfNodes==0)
return true;
return false;
}
/**
* public boolean search(int i)
*
* returns true if and only if the tree contains i
*
*/
public boolean search(double i) {
return (recursiveSearch(i, this.DUMMYROOT.getLeftChild())!=NULL);
}
public RBNode searchNode(double i) {
return recursiveSearch(i, this.DUMMYROOT.getLeftChild());
}
private RBNode recursiveSearch(double i, RBNode rbNode) {
if (rbNode==NULL)
return NULL;
else if (rbNode.getKey()==i)
return rbNode;
else if (rbNode.getKey()<i)
return recursiveSearch(i,rbNode.getRightChild());
else
return recursiveSearch(i,rbNode.getLeftChild());
}
/**
* public void insert(int i)
*
* inserts the integer i into the binary tree; the tree
* must remain valid (keep its invariants).
* the function returns the number of color flips, or 0 if i was already in the tree
*
*/
public int insert(int i) {
RBNode rb = new RBNode(i);
if (this.search((double)i)==false) {
this.numOfNodes++;
return RBTreeInsert(this,rb);
}
return 0;
}
private RBNode treePosition(RBNode x, double k) {
RBNode y=x;
while (x!=NULL) {
y=x;
if (x.getKey()==k)
return x;
else if (x.getKey()>k)
x=x.getLeftChild();
else
x=x.getRightChild();
}
return y;
}
private int RBTreeInsert(RBTree t, RBNode z) {
RBNode y;
y=treePosition(t.DUMMYROOT,z.getKey());
if (z.getKey()!=y.getKey()) {
z.setParent(y);
z.setLeftChild(NULL);
z.setRightChild(NULL);
z.setColor("red");
if (z.getKey()<y.getKey())
y.setLeftChild(z);
else
y.setRightChild(z);
}
return RBTreeInsertFixUp(z,t);
}
private int RBTreeInsertFixUp(RBNode node, RBTree t) {
int counter =0;
if(this.empty()==true)
return counter;
while(node.parent.color.equals("red")){
if(node.parent == node.parent.parent.leftChild){
RBNode y = node.parent.parent.rightChild;
//case 1
if(y.color.equals("red")){
counter+=3;
node.parent.setColor("black");
y.setColor("black");
node.parent.parent.setColor("red");
node = node.parent.parent;
}
//case 2
else {
if(node == node.parent.rightChild) {
node = node.parent;
leftRotate(node, t);
}
//case 3
counter+=2;
node.parent.setColor("black");
node.parent.parent.setColor("red");
rightRotate(node.parent.parent, t);
}
}
else {
RBNode y = node.parent.parent.leftChild;
//case 1
if(y.color.equals("red")){
counter+=3;
node.parent.setColor("black");
y.setColor("black");
node.parent.parent.setColor("red");
node = node.parent.parent;
}
//case 2
else {
if (node == node.parent.leftChild) {
node = node.parent;
rightRotate(node, t);
}
//case 3
counter+=2;
node.parent.setColor("black");
node.parent.parent.setColor("red");
leftRotate(node.parent.parent, t);
}
}
}
if(!(this.DUMMYROOT.leftChild.color.equals("black"))) {
this.DUMMYROOT.leftChild.setColor("black");
counter++;
}
return counter;
}
private void rightRotate(RBNode node, RBTree t) {
RBNode y = node.leftChild;
Transplant(node, y);
leftChild(node, y.rightChild);
rightChild(y, node);
}
private void leftRotate(RBNode node, RBTree t) {
RBNode y = node.rightChild;
Transplant(node,y);
rightChild(node, y.leftChild);
leftChild(y,node);
}
private void Transplant(RBNode node, RBNode y) {
if(node == node.parent.leftChild)
leftChild(node.parent, y);
else
rightChild(node.parent,y);
}
private void rightChild(RBNode node, RBNode y) {
node.rightChild =y;
y.parent = node;
}
private void leftChild(RBNode node, RBNode y) {
node.leftChild = y;
y.parent = node;
}
/**
* public void delete(int i)
*
* deletes the integer i from the binary tree, if it is there;
* the tree must remain valid (keep its invariants).
* the function returns the number of color flips, or 0 if i was not in the tree
*
*/
public int delete(int i)
{
if (this.search(i)==true) {
//deletion will be made, so we decrease numOfNodes by 1
this.numOfNodes--;
return RBTreeDelete(this.searchNode(i),this);
}
return 0;
}
public int RBTreeDelete(RBNode deleteNode, RBTree tree){
RBNode y;
RBNode x;
if(this.empty() == true)
return 0;
if(deleteNode.getLeftChild() == this.NULL || deleteNode.getRightChild() == this.NULL)
y = deleteNode;
else {
y = TreeSuccessor(deleteNode);
}
if(y.leftChild != NULL)
x = y.leftChild;
else
x = y.rightChild;
x.parent = y.parent;
if(y.parent == NULL)
DUMMYROOT.leftChild = x;
else if(y == y.parent.leftChild)
y.parent.leftChild = x;
else
y.parent.rightChild = x;
if(y != deleteNode)
deleteNode.key = y.key;
if (y.color.equals("black")==true)
return RBDeleteFixUp(tree, x);
return 0; //counter is 0, no color changes should be made. if me made any - they will be returned by "RBDleteFixUp"
}
private int RBDeleteFixUp(RBTree T, RBNode x) {
//counts color changes
int counter2= 0;
boolean b=true;
RBNode w = new RBNode();
if(this.empty()==true)
return counter2;
while(((x != DUMMYROOT.leftChild)) && x.color.equals("black") && b==true){
if(x == x.parent.leftChild){
w = x.parent.rightChild;
//case 1
if(w.color.equals("red")){
System.out.println("1");
w.setColor("black");
counter2++;
x.parent.setColor("red");
counter2++;
leftRotate(x.parent, T);
w = x.parent.rightChild;
}
//case2
if((w.rightChild.color.equals("black")) && (w.leftChild.color.equals("black"))){
System.out.println("2");
w.setColor("red");
counter2++;
x = x.parent;
}
//case 3
else {
if(w.rightChild.color.equals("black")){
System.out.println("3");
w.leftChild.setColor("black");
counter2++;
w.setColor("red");
counter2++;
rightRotate(w, T);
w = x.parent.rightChild;
}
//case 4
System.out.println("4");
w.color = x.parent.color;
counter2++;
x.parent.setColor("black");
counter2++;
w.rightChild.setColor("black");
counter2++;
leftRotate(x.parent, T);
x = DUMMYROOT.leftChild;
}
}
else{
w = x.parent.leftChild;
//case 1
if(w.color.equals("red")){
System.out.println("5");
w.setColor("black");
counter2++;
x.parent.setColor("red");
counter2++;
rightRotate(x.parent, T);
w = x.parent.leftChild;
}
//case2
if(w.rightChild.color.equals("black") && w.leftChild.color.equals("black")){
System.out.println("6");
w.setColor("red");
counter2++;
x = x.parent;
}
//case 3
else {
if(w.leftChild.color.equals("black")){
System.out.println("7");
w.rightChild.setColor("black");
counter2++;
w.setColor("red");
counter2++;
leftRotate(w, T);
w = x.parent.leftChild;
}
//case 4
/**
if(!(w.color == x.parent.color)){
w.color = x.parent.color;
counter2++;
}
**/
System.out.println("8");
w.color = x.parent.color;
counter2++;
x.parent.setColor("black");
counter2++;
w.leftChild.setColor("black"); //HERE THERES A NULL EXCEPTION
counter2++;
rightRotate(x.parent, T);
x = DUMMYROOT.leftChild;
}
}
}
x.setColor("black");
counter2++;
return counter2;
}
private RBNode TreeSuccessor(RBNode node) {
RBNode x = new RBNode();
RBNode y = new RBNode();
x=node;
if (x.getRightChild()!=this.NULL) {
return minNode(x.getRightChild());
}
y=x.getParent();
while ((y!=this.NULL) && (x==y.getRightChild())) {
x=y;
y=x.getParent();
}
return y;
}
public RBNode minNode(RBNode startNode) {
RBNode currNode= new RBNode();
currNode=startNode;
if (currNode==this.NULL) {
System.out.println("currNode==this.NULL");
return currNode;
}
else
{
while (currNode.leftChild!=this.NULL)
currNode=currNode.leftChild;
}
return currNode;
}
static class RBNode{
public RBNode(int key) {
this.key=key;
}
private double key;
private RBNode parent;
private RBNode rightChild;
private RBNode leftChild;
private String info;
private String color;
public RBNode() {
this.key=-1;
this.leftChild=null;
this.rightChild=null;
this.parent=null;
}
public RBNode(int key, String color) {
this.color=color;
this.key=key;
this.leftChild=null;
this.rightChild=null;
this.parent=null;
}
public RBNode(int key, String color, RBNode left, RBNode right) {
this.color=color;
this.key=key;
this.leftChild=left;
this.rightChild=right;
}
public double getKey() {
return this.key;
}
public String getColor() {
return this.color;
}
public RBNode getParent() {
return this.parent;
}
public RBNode getLeftChild() {
return this.leftChild;
}
public RBNode getRightChild() {
return this.rightChild;
}
public void setColor(String color) {
this.color=color;
}
public void setKey(double key) {
this.key=key;
}
public void setParent(RBNode parent) {
this.parent=parent;
}
public void setLeftChild(RBNode leftChild) {
this.leftChild=leftChild;
}
public void setRightChild(RBNode rightChild) {
this.rightChild=rightChild;
}
}
public static void main(String[] args) {
RBTree t = new RBTree();
t.insert(14);
t.insert(11);
t.insert(7);
t.insert(8);
t.delete(11);
}