理解标准的二叉搜索树及其操作是相当容易的。正因为理解了这一点，我甚至不需要记住插入、删除和搜索操作的实现。
我现在正在学习红黑树，并且理解了它保持平衡的属性。然而，我感觉很难理解它的插入和删除过程。
我知道，在插入新节点时，我们将节点标记为红色（因为红色是我们可以做到的最好的方法，以避免破坏更少的红黑树定律）。新的红色节点可能仍然会破坏“无连续红色节点法则”。然后我们通过以下方式进行修复：
检查其叔节点的颜色。如果是红色，则将其父节点和叔节点标记为黑色，然后转到祖父节点。
如果它是右子节点，则左旋其父节点。
将其父节点标记为黑色，将其祖父节点标记为红色，然后右旋其祖父节点。
完成（基本上如上所述）。
许多地方描述红黑树的插入方式就像以上所述。他们只告诉你如何做。但是为什么这些步骤可以修复树？为什么首先左旋，然后右旋？
有人能够更清楚地解释一下吗，甚至比CLRS更清楚？旋转的魔力是什么？
我真的希望理解，这样在1年后，我就可以自己实现红黑树，而不需要查看书籍。
谢谢
2）对于红黑树：http://www.youtube.com/watch?v=JRsN4Oz36QU&list=PLBF3763AF2E1C572F&index=14。
虽然每个视频都长达一小时，但我觉得值得仔细学习。
这是我的实现：
import java.util.Optional;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReference;
/**
*
* @author Gaurav Ratnawat
* <p>
* Red Black Tree
* <p>
* Time complexity
* Insert - O(logn)
* Delete - O(logn)
* Search - O(logn)
* <p>
* Does not work for duplicates.
* <p>
* References
* http://pages.cs.wisc.edu/~skrentny/cs367-common/readings/Red-Black-Trees/
* https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
*/
public class RedBlackTree {
public enum Color {
RED,
BLACK
}
public static class Node {
int data;
Color color;
Node left;
Node right;
Node parent;
boolean isNullLeaf;
}
private static Node createBlackNode(int data) {
Node node = new Node();
node.data = data;
node.color = Color.BLACK;
node.left = createNullLeafNode(node);
node.right = createNullLeafNode(node);
return node;
}
private static Node createNullLeafNode(Node parent) {
Node leaf = new Node();
leaf.color = Color.BLACK;
leaf.isNullLeaf = true;
leaf.parent = parent;
return leaf;
}
private static Node createRedNode(Node parent, int data) {
Node node = new Node();
node.data = data;
node.color = Color.RED;
node.parent = parent;
node.left = createNullLeafNode(node);
node.right = createNullLeafNode(node);
return node;
}
/**
* Main insert method of red black tree.
*/
public Node insert(Node root, int data) {
return insert(null, root, data);
}
/**
* Main delete method of red black tree.
*/
public Node delete(Node root, int data) {
AtomicReference<Node> rootReference = new AtomicReference<>();
delete(root, data, rootReference);
if (rootReference.get() == null) {
return root;
} else {
return rootReference.get();
}
}
/**
* Main print method of red black tree.
*/
public void printRedBlackTree(Node root) {
printRedBlackTree(root, 0);
}
/**
* Main validate method of red black tree.
*/
public boolean validateRedBlackTree(Node root) {
if (root == null) {
return true;
}
//check if root is black
if (root.color != Color.BLACK) {
System.out.print("Root is not black");
return false;
}
//Use of AtomicInteger solely because java does not provide any other mutable int wrapper.
AtomicInteger blackCount = new AtomicInteger(0);
//make sure black count is same on all path and there is no red red relationship
return checkBlackNodesCount(root, blackCount, 0) && noRedRedParentChild(root, Color.BLACK);
}
private void rightRotate(Node root, boolean changeColor) {
Node parent = root.parent;
root.parent = parent.parent;
if (parent.parent != null) {
if (parent.parent.right == parent) {
parent.parent.right = root;
} else {
parent.parent.left = root;
}
}
Node right = root.right;
root.right = parent;
parent.parent = root;
parent.left = right;
if (right != null) {
right.parent = parent;
}
if (changeColor) {
root.color = Color.BLACK;
parent.color = Color.RED;
}
}
private void leftRotate(Node root, boolean changeColor) {
Node parent = root.parent;
root.parent = parent.parent;
if (parent.parent != null) {
if (parent.parent.right == parent) {
parent.parent.right = root;
} else {
parent.parent.left = root;
}
}
Node left = root.left;
root.left = parent;
parent.parent = root;
parent.right = left;
if (left != null) {
left.parent = parent;
}
if (changeColor) {
root.color = Color.BLACK;
parent.color = Color.RED;
}
}
private Optional<Node> findSiblingNode(Node root) {
Node parent = root.parent;
if (isLeftChild(root)) {
return Optional.ofNullable(parent.right.isNullLeaf ? null : parent.right);
} else {
return Optional.ofNullable(parent.left.isNullLeaf ? null : parent.left);
}
}
private boolean isLeftChild(Node root) {
Node parent = root.parent;
return parent.left == root;
}
private Node insert(Node parent, Node root, int data) {
if (root == null || root.isNullLeaf) {
//if parent is not null means tree is not empty
//so create a red leaf node
if (parent != null) {
return createRedNode(parent, data);
} else { //otherwise create a black root node if tree is empty
return createBlackNode(data);
}
}
//duplicate insertion is not allowed for this tree.
if (root.data == data) {
throw new IllegalArgumentException("Duplicate date " + data);
}
//if we go on left side then isLeft will be true
//if we go on right side then isLeft will be false.
boolean isLeft;
if (root.data > data) {
Node left = insert(root, root.left, data);
//if left becomes root parent means rotation
//happened at lower level. So just return left
//so that nodes at upper level can set their
//child correctly
if (left == root.parent) {
return left;
}
//set the left child returned to be left of root node
root.left = left;
//set isLeft to be true
isLeft = true;
} else {
Node right = insert(root, root.right, data);
//if right becomes root parent means rotation
//happened at lower level. So just return right
//so that nodes at upper level can set their
//child correctly
if (right == root.parent) {
return right;
}
//set the right child returned to be right of root node
root.right = right;
//set isRight to be true
isLeft = false;
}
if (isLeft) {
//if we went to left side check to see Red-Red conflict
//between root and its left child
if (root.color == Color.RED && root.left.color == Color.RED) {
//get the sibling of root. It is returning optional means
//sibling could be empty
Optional<Node> sibling = findSiblingNode(root);
//if sibling is empty or of BLACK color
if (sibling.isEmpty() || sibling.get().color == Color.BLACK) {
//check if root is left child of its parent
if (isLeftChild(root)) {
//this creates left left situation. So do one right rotate
rightRotate(root, true);
} else {
//this creates left-right situation so do one right rotate followed
//by left rotate
//do right rotation without change in color. So sending false.
//when right rotation is done root becomes right child of its left
//child. So make root = root.parent because its left child before rotation
//is new root of this subtree.
rightRotate(root.left, false);
//after rotation root should be root's parent
root = root.parent;
//then do left rotate with change of color
leftRotate(root, true);
}
} else {
//we have sibling color as RED. So change color of root
//and its sibling to Black. And then change color of their
//parent to red if their parent is not a root.
root.color = Color.BLACK;
sibling.get().color = Color.BLACK;
//if parent's parent is not null means parent is not root.
//so change its color to RED.
if (root.parent.parent != null) {
root.parent.color = Color.RED;
}
}
}
} else {
//this is mirror case of above. So same comments as above.
if (root.color == Color.RED && root.right.color == Color.RED) {
Optional<Node> sibling = findSiblingNode(root);
if (!sibling.isPresent() || sibling.get().color == Color.BLACK) {
if (!isLeftChild(root)) {
leftRotate(root, true);
} else {
leftRotate(root.right, false);
root = root.parent;
rightRotate(root, true);
}
} else {
root.color = Color.BLACK;
sibling.get().color = Color.BLACK;
if (root.parent.parent != null) {
root.parent.color = Color.RED;
}
}
}
}
return root;
}
/**
* Using atomicreference because java does not provide mutable wrapper. Its like
* double pointer in C.
*/
private void delete(Node root, int data, AtomicReference<Node> rootReference) {
if (root == null || root.isNullLeaf) {
return;
}
if (root.data == data) {
//if node to be deleted has 0 or 1 null children then we have
//deleteOneChild use case as discussed in video.
if (root.right.isNullLeaf || root.left.isNullLeaf) {
deleteOneChild(root, rootReference);
} else {
//otherwise look for the inorder successor in right subtree.
//replace inorder successor data at root data.
//then delete inorder successor which should have 0 or 1 not null child.
Node inorderSuccessor = findSmallest(root.right);
root.data = inorderSuccessor.data;
delete(root.right, inorderSuccessor.data, rootReference);
}
}
//search for the node to be deleted.
if (root.data < data) {
delete(root.right, data, rootReference);
} else {
delete(root.left, data, rootReference);
}
}
private Node findSmallest(Node root) {
Node prev = null;
while (root != null && !root.isNullLeaf) {
prev = root;
root = root.left;
}
return prev != null ? prev : root;
}
/**
* Assumption that node to be deleted has either 0 or 1 non leaf child
*/
private void deleteOneChild(Node nodeToBeDelete, AtomicReference<Node> rootReference) {
Node child = nodeToBeDelete.right.isNullLeaf ? nodeToBeDelete.left : nodeToBeDelete.right;
//replace node with either one not null child if it exists or null child.
replaceNode(nodeToBeDelete, child, rootReference);
//if the node to be deleted is BLACK. See if it has one red child.
if (nodeToBeDelete.color == Color.BLACK) {
//if it has one red child then change color of that child to be Black.
if (child.color == Color.RED) {
child.color = Color.BLACK;
} else {
//otherwise we have double black situation.
deleteCase1(child, rootReference);
}
}
}
/**
* If double black node becomes root then we are done. Turning it into
* single black node just reduces one black in every path.
*/
private void deleteCase1(Node doubleBlackNode, AtomicReference<Node> rootReference) {
if (doubleBlackNode.parent == null) {
rootReference.set(doubleBlackNode);
return;
}
deleteCase2(doubleBlackNode, rootReference);
}
/**
* If sibling is red and parent and sibling's children are black then rotate it
* so that sibling becomes black. Double black node is still double black so we need
* further processing.
*/
private void deleteCase2(Node doubleBlackNode, AtomicReference<Node> rootReference) {
Node siblingNode = findSiblingNode(doubleBlackNode).get();
if (siblingNode.color == Color.RED) {
if (isLeftChild(siblingNode)) {
rightRotate(siblingNode, true);
} else {
leftRotate(siblingNode, true);
}
if (siblingNode.parent == null) {
rootReference.set(siblingNode);
}
}
deleteCase3(doubleBlackNode, rootReference);
}
/**
* If sibling, sibling's children and parent are all black then turn sibling into red.
* This reduces black node for both the paths from parent. Now parent is new double black
* node which needs further processing by going back to case1.
*/
private void deleteCase3(Node doubleBlackNode, AtomicReference<Node> rootReference) {
Node siblingNode = findSiblingNode(doubleBlackNode).get();
if (doubleBlackNode.parent.color == Color.BLACK && siblingNode.color == Color.BLACK && siblingNode.left.color == Color.BLACK
&& siblingNode.right.color == Color.BLACK) {
siblingNode.color = Color.RED;
deleteCase1(doubleBlackNode.parent, rootReference);
} else {
deleteCase4(doubleBlackNode, rootReference);
}
}
/**
* If sibling color is black, parent color is red and sibling's children color is black then swap color b/w sibling
* and parent. This increases one black node on double black node path but does not affect black node count on
* sibling path. We are done if we hit this situation.
*/
private void deleteCase4(Node doubleBlackNode, AtomicReference<Node> rootReference) {
Node siblingNode = findSiblingNode(doubleBlackNode).get();
if (doubleBlackNode.parent.color == Color.RED && siblingNode.color == Color.BLACK && siblingNode.left.color == Color.BLACK
&& siblingNode.right.color == Color.BLACK) {
siblingNode.color = Color.RED;
doubleBlackNode.parent.color = Color.BLACK;
return;
} else {
deleteCase5(doubleBlackNode, rootReference);
}
}
/**
* If sibling is black, double black node is left child of its parent, siblings right child is black
* and sibling's left child is red then do a right rotation at siblings left child and swap colors.
* This converts it to delete case6. It will also have a mirror case.
*/
private void deleteCase5(Node doubleBlackNode, AtomicReference<Node> rootReference) {
Node siblingNode = findSiblingNode(doubleBlackNode).get();
if (siblingNode.color == Color.BLACK) {
if (isLeftChild(doubleBlackNode) && siblingNode.right.color == Color.BLACK && siblingNode.left.color == Color.RED) {
rightRotate(siblingNode.left, true);
} else if (!isLeftChild(doubleBlackNode) && siblingNode.left.color == Color.BLACK && siblingNode.right.color == Color.RED) {
leftRotate(siblingNode.right, true);
}
}
deleteCase6(doubleBlackNode, rootReference);
}
/**
* If sibling is black, double black node is left child of its parent, sibling left child is black and sibling's right child is
* red, sibling takes its parent color, parent color becomes black, sibling's right child becomes black and then do
* left rotation at sibling without any further change in color. This removes double black and we are done. This
* also has a mirror condition.
*/
private void deleteCase6(Node doubleBlackNode, AtomicReference<Node> rootReference) {
Node siblingNode = findSiblingNode(doubleBlackNode).get();
siblingNode.color = siblingNode.parent.color;
siblingNode.parent.color = Color.BLACK;
if (isLeftChild(doubleBlackNode)) {
siblingNode.right.color = Color.BLACK;
leftRotate(siblingNode, false);
} else {
siblingNode.left.color = Color.BLACK;
rightRotate(siblingNode, false);
}
if (siblingNode.parent == null) {
rootReference.set(siblingNode);
}
}
private void replaceNode(Node root, Node child, AtomicReference<Node> rootReference) {
child.parent = root.parent;
if (root.parent == null) {
rootReference.set(child);
} else {
if (isLeftChild(root)) {
root.parent.left = child;
} else {
root.parent.right = child;
}
}
}
private void printRedBlackTree(Node root, int space) {
if (root == null || root.isNullLeaf) {
return;
}
printRedBlackTree(root.right, space + 5);
for (int i = 0; i < space; i++) {
System.out.print(" ");
}
System.out.println(root.data + " " + (root.color == Color.BLACK ? "B" : "R"));
printRedBlackTree(root.left, space + 5);
}
private boolean noRedRedParentChild(Node root, Color parentColor) {
if (root == null) {
return true;
}
if (root.color == Color.RED && parentColor == Color.RED) {
return false;
}
return noRedRedParentChild(root.left, root.color) && noRedRedParentChild(root.right, root.color);
}
private boolean checkBlackNodesCount(Node root, AtomicInteger blackCount, int currentCount) {
if (root.color == Color.BLACK) {
currentCount++;
}
if (root.left == null && root.right == null) {
if (blackCount.get() == 0) {
blackCount.set(currentCount);
return true;
} else {
return currentCount == blackCount.get();
}
}
return checkBlackNodesCount(root.left, blackCount, currentCount) && checkBlackNodesCount(root.right, blackCount, currentCount);
}
public static void main(String[] args) {
Node root = null;
RedBlackTree redBlackTree = new RedBlackTree();
root = redBlackTree.insert(root, 10);
root = redBlackTree.insert(root, 15);
root = redBlackTree.insert(root, -10);
root = redBlackTree.insert(root, 20);
root = redBlackTree.insert(root, 30);
root = redBlackTree.insert(root, 40);
root = redBlackTree.insert(root, 50);
root = redBlackTree.insert(root, -15);
root = redBlackTree.insert(root, 25);
root = redBlackTree.insert(root, 17);
root = redBlackTree.insert(root, 21);
root = redBlackTree.insert(root, 24);
root = redBlackTree.insert(root, 28);
root = redBlackTree.insert(root, 34);
root = redBlackTree.insert(root, 32);
root = redBlackTree.insert(root, 26);
root = redBlackTree.insert(root, 35);
root = redBlackTree.insert(root, 19);
redBlackTree.printRedBlackTree(root);
root = redBlackTree.delete(root, 50);
System.out.println(redBlackTree.validateRedBlackTree(root));
root = redBlackTree.delete(root, 40);
System.out.println(redBlackTree.validateRedBlackTree(root));
root = redBlackTree.delete(root, -10);
System.out.println(redBlackTree.validateRedBlackTree(root));
root = redBlackTree.delete(root, 15);
System.out.println(redBlackTree.validateRedBlackTree(root));
root = redBlackTree.delete(root, 17);
System.out.println(redBlackTree.validateRedBlackTree(root));
root = redBlackTree.delete(root, 24);
System.out.println(redBlackTree.validateRedBlackTree(root));
root = redBlackTree.delete(root, 21);
System.out.println(redBlackTree.validateRedBlackTree(root));
root = redBlackTree.delete(root, 32);
System.out.println(redBlackTree.validateRedBlackTree(root));
root = redBlackTree.delete(root, 26);
System.out.println(redBlackTree.validateRedBlackTree(root));
root = redBlackTree.delete(root, 19);
System.out.println(redBlackTree.validateRedBlackTree(root));
root = redBlackTree.delete(root, 25);
System.out.println(redBlackTree.validateRedBlackTree(root));
root = redBlackTree.delete(root, 17);
System.out.println(redBlackTree.validateRedBlackTree(root));
root = redBlackTree.delete(root, -15);
System.out.println(redBlackTree.validateRedBlackTree(root));
root = redBlackTree.delete(root, 20);
System.out.println(redBlackTree.validateRedBlackTree(root));
root = redBlackTree.delete(root, 35);
System.out.println(redBlackTree.validateRedBlackTree(root));
root = redBlackTree.delete(root, 34);
System.out.println(redBlackTree.validateRedBlackTree(root));
root = redBlackTree.delete(root, 30);
System.out.println(redBlackTree.validateRedBlackTree(root));
root = redBlackTree.delete(root, 28);
System.out.println(redBlackTree.validateRedBlackTree(root));
root = redBlackTree.delete(root, 10);
System.out.println(redBlackTree.validateRedBlackTree(root));
}
}
你真的很好地总结了这三种情况。
在RB-Tree中插入后，如果存在两个连续的红色节点，那么就会出现一个主要问题需要解决。 我们如何使这两个连续的红色节点消失而不违反规则（每条路径具有相同数量的黑色节点）？ 因此，我们看到这两个节点，只存在3种情况...
对不起，你可以查看《算法导论》的教材。
没有人能帮助你理清rb-tree。他们只能在某些关键点上指导你。