我正在 O (log n) 时间内实现一个具有插入、搜索和删除功能的红黑树。插入和搜索工作正常。但是我坚持删除。我在网上找到了这张 ppt 幻灯片，它显示了 RBT 删除的算法:http://www.slideshare.net/piotrszymanski/red-black-trees#btnNext从第 56 页开始。我知道我问的有点太多了，但我已经坚持了 2 周多了，我找不到问题所在。我理解自上而下删除的方式是您必须相应地旋转和重新着色节点，直到找到要删除的节点的前身。当你确实找到这个节点时——它可能是一个叶子节点或一个有一个右 child 的节点，用这个节点的数据替换要删除的节点数据，然后像正常的 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;
}
节点正在被删除，但是删除后的树会被黑破坏，这是非常错误的。
最佳答案
eternally confuzzled blog具有红黑树插入和删除的自上而下的实现。它还逐个分析了它为何起作用。我不会在这里复制它(它相当冗长)。
我将该博客用作在 C++ 和 Java 中实现红黑树的引用。正如我在 earlier answer 中讨论的那样，我发现该实现比 std::map 的红黑树自下而上实现更快(无论当时 gcc 附带什么 STL)。
这是代码到 Java 的未经测试的直接翻译。我强烈建议您对其进行测试并根据您的风格进行变形。
private final static int LEFT = 0;
private final static int RIGHT = 1;
private static class Node {
private Node left,right;
private boolean red;
...
// any non-zero argument returns right
Node link(int direction) {
return (direction == LEFT) ? this.left : this.right;
}
// any non-zero argument sets right
Node setLink(int direction, Node n) {
if (direction == LEFT) this.left = n;
else this.right = n;
return n;
}
}
boolean remove(int data) {
if ( this.root != null ) {
final Node head = new Node(-1, null, null); /* False tree root */
Node cur, parent, grandpa; /* Helpers */
Node found = null; /* Found item */
int dir = RIGHT;
/* Set up helpers */
cur = head;
grandpa = parent = null;
cur.setLink(RIGHT, this.root);
/* Search and push a red down */
while ( cur.link(dir) != null ) {
int last = dir;
/* Update helpers */
grandpa = parent, parent = cur;
cur = cur.link(dir);
dir = cur.data < data ? RIGHT : LEFT;
/* Save found node */
if ( cur.data == data )
found = cur;
/* Push the red node down */
if ( !is_red(cur) && !is_red(cur.link(dir)) ) {
if ( is_red(cur.link(~dir)) )
parent = parent.setLink(last, singleRotate(cur, dir));
else if ( !is_red(cur.link(~dir)) ) {
Node s = parent.link(~last);
if ( s != null ) {
if (!is_red(s.link(~last)) && !is_red(s.link(last))) {
/* Color flip */
parent.red = false;
s.red = true;
cur.red = true;
}
else {
int dir2 = grandpa.link(RIGHT) == parent ? RIGHT : LEFT;
if ( is_red(s.link(last)) )
grandpa.setLink(dir2, doubleRotate(parent, last));
else if ( is_red(s.link(~last)) )
grandpa.setLink(dir2, singleRotate(parent, last));
/* Ensure correct coloring */
cur.red = grandpa.link(dir2).red = true;
grandpa.link(dir2).link(LEFT).red = false;
grandpa.link(dir2).link(RIGHT).red = false;
}
}
}
}
}
/* Replace and remove if found */
if ( found != null ) {
found.data = cur.data;
parent.setLink(
parent.link(RIGHT) == cur ? RIGHT : LEFT,
cur.link(cur.link(LEFT) == null ? RIGHT : LEFT));
}
/* Update root and make it black */
this.root = head.link(RIGHT);
if ( this.root != null )
this.root.red = false;
}
return true;
}
关于java - 红黑树自顶向下删除算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14119995/