我正在实现一个具有插入、搜索和删除功能的红黑树，时间复杂度为O(log n)。插入和搜索都正常工作。但是在删除方面卡住了。我在网上找到了这张ppt幻灯片，展示了RBT删除的算法：http://www.slideshare.net/piotrszymanski/red-black-trees#btnNext ，从第56页开始。我知道我要求有些过高，但我已经卡了两个多星期，找不到问题所在。按照我理解的自顶向下删除方式，您需要旋转和重新着色节点，直到找到要删除的节点的前驱。当您找到此节点时（可能是叶子节点或仅有右子节点的节点），将要删除节点的数据替换为该节点的数据，并像普通的BST删除一样删除此节点，对吗？
这是我基于那张幻灯片学到的内容编写的代码。如果有人能够检查一下，我将不胜感激！或者，如果您认为有比我使用的更好的算法，请告诉我！
节点正在被删除，但删除后的树将违反黑色平衡，这是非常错误的。
这是我基于那张幻灯片学到的内容编写的代码。如果有人能够检查一下，我将不胜感激！或者，如果您认为有比我使用的更好的算法，请告诉我！
public void delete(int element){
if (root == null){
System.out.println("Red Black Tree is Empty!");
} else {
Node X = root;
parent = null;
grandParent = null;
sibling = null;
if (isLeaf(X)){
if (X.getElement() == element){
emptyRBT();
}
} else {
if (checkIfBlack(root.getLeftChild()) && checkIfBlack(root.getRightChild())){
root.setIsBlack(false);
if (X.getElement() > element && X.getLeftChild() != null){
X = moveLeft(X);
} else if (X.getElement() < element && X.getRightChild() != null){
X = moveRight(X);
}
Step2(X, element);
} else {
Step2B(X, element);
}
}
}
root.setIsBlack(true);
}
public void Step2(Node X, int element)
{
int dir = -1;
while (!isLeaf(X)){
if (predecessor == null){ // still didn't find Node to delete
if (X.getElement() > element && X.getLeftChild() != null){
X = moveLeft(X);
dir = 0;
} else if (X.getElement() < element && X.getRightChild() != null){
X = moveRight(X);
dir = 1;
} else if (X.getElement() == element){
toDelete = X;
predecessor = inorderPredecessor(X.getRightChild());
X = moveRight(X);
}
} else { // if node to delete is already found and X is equal to right node of to delete
// move always to the left until you find predecessor
if (X != predecessor){
X = moveLeft(X);
dir = 0;
}
}
if (!isLeaf(X)){
if (!hasOneNullNode(X)){
if (checkIfBlack(X.getLeftChild()) && checkIfBlack(X.getRightChild())){
Step2A(X, element, dir);
} else {
Step2B(X, element);
}
}
}
}
removeNode(X);
if (predecessor != null){
toDelete.setElement(X.getElement());
}
}
public Node Step2A(Node X, int element, int dir) {
if (checkIfBlack(sibling.getLeftChild()) && checkIfBlack(sibling.getRightChild())) {
X = Step2A1(X);
} else if ((checkIfBlack(sibling.getLeftChild()) == false) && checkIfBlack(sibling.getRightChild())) {
X = Step2A2(X);
} else if ((checkIfBlack(sibling.getLeftChild()) && (checkIfBlack(sibling.getRightChild()) == false))) {
X = Step2A3(X);
} else if ((checkIfBlack(sibling.getLeftChild()) == false) && (checkIfBlack(sibling.getRightChild()) == false)) {
X = Step2A3(X);
}
return X;
}
public Node Step2A1(Node X) {
X.setIsBlack(!X.IsBlack());
parent.setIsBlack(!parent.IsBlack());
sibling.setIsBlack(!sibling.IsBlack());
return X;
}
public Node Step2A2(Node X) {
if (parent.getLeftChild() == sibling){
LeftRightRotation(sibling.getLeftChild(), sibling, parent);
} else RightLeftRotation(sibling.getRightChild(), sibling, parent);
X.setIsBlack(!X.IsBlack());
parent.setIsBlack(!parent.IsBlack());
return X;
}
public Node Step2A3(Node X) {
if (parent.getLeftChild() == sibling){
leftRotate(sibling);
} else if (parent.getRightChild() == sibling){
rightRotate(sibling);
}
X.setIsBlack(!X.IsBlack());
parent.setIsBlack(!parent.IsBlack());
sibling.setIsBlack(!sibling.IsBlack());
sibling.getRightChild().setIsBlack(!sibling.getRightChild().IsBlack());
return X;
}
public void Step2B(Node X, int element){
if (predecessor == null){
if (X.getElement() > element && X.getLeftChild() != null){
X = moveLeft(X);
} else if (X.getElement() < element && X.getRightChild() != null){
X = moveRight(X);
} else if (X.getElement() == element){
Step2(X, element);
}
} else {
if (X != predecessor)
X = moveLeft(X);
else Step2(X, element);
}
if (X.IsBlack()){
if (parent.getLeftChild() == sibling){
leftRotate(sibling);
} else if (parent.getRightChild() == sibling){
rightRotate(sibling);
}
parent.setIsBlack(!parent.IsBlack());
sibling.setIsBlack(!sibling.IsBlack());
Step2(X, element);
} else {
Step2B(X, element);
}
}
public void removeNode(Node X) {
if (isLeaf(X)) {
adjustParentPointer(null, X);
count--;
} else if (X.getLeftChild() != null && X.getRightChild() == null) {
adjustParentPointer(X.getLeftChild(), X);
count--;
} else if (X.getRightChild() != null && X.getLeftChild() == null) {
adjustParentPointer(X.getRightChild(), X);
count--;
}
}
public Node inorderPredecessor(Node node){
while (node.getLeftChild() != null){
node = node.getLeftChild();
}
return node;
}
public void adjustParentPointer(Node node, Node current) {
if (parent != null) {
if (parent.getElement() < current.getElement()) {
parent.setRightChild(node);
} else if (parent.getElement() > current.getElement()) {
parent.setLeftChild(node);
}
} else {
root = node;
}
}
public boolean checkIfBlack(Node n){
if (n == null || n.IsBlack() == true){
return true;
} else return false;
}
public Node leftRotate(Node n)
{
parent.setLeftChild(n.getRightChild());
n.setRightChild(parent);
Node gp = grandParent;
if (gp != null){
if (gp.getElement() > n.getElement()){
gp.setLeftChild(n);
} else if (gp.getElement() < n.getElement()){
gp.setRightChild(n);
}
} else root = n;
return n;
}
public Node rightRotate(Node n)
{
parent.setRightChild(n.getLeftChild());
n.setLeftChild(parent);
Node gp = grandParent;
if (gp != null){
if (gp.getElement() > n.getElement()){
gp.setLeftChild(n);
} else if (gp.getElement() < n.getElement()){
gp.setRightChild(n);
}
} else root = n;
return n;
}
节点正在被删除，但删除后的树将违反黑色平衡，这是非常错误的。