完全理解标准二叉搜索树及其操作非常容易。因为有了这样的理解，我什至不需要记住那些插入、删除、搜索操作的实现。
我现在正在学习红黑树，我了解它保持树平衡的属性。但是我觉得很难理解它的插入和删除过程。
我知道在插入新节点时，我们将节点标记为红色（因为红色是我们能做的最好的事情，以避免破坏较少的红黑树法则）。新的红色节点仍有可能打破“无连续红色节点定律”。然后我们通过以下方式修复它：
检查其叔叔的颜色，如果是红色，则将其父母和叔叔标记为黑色，然后去找祖父母。
如果它是右孩子，左旋转它的父母
将其父母标记为黑色，将其祖父母标记为红色，然后向右旋转其祖父母。
完成（基本上和上面一样）。
很多地方都像上面描述了红黑树的插入。他们只是告诉你如何去做。但是为什么这些步骤可以修复树呢？为什么先左旋，后右旋？
谁能比 CLRS 更清楚地向我解释为什么？旋转有什么魔力？
我真的很想明白，所以一年后，我可以自己实现红黑树，而无需复习一本书。
谢谢
为了其他阅读此线程但无法访问已接受答案中提到的书的人的利益，我希望这是一个可以接受的描述性答案。
旋转使树处于符合重新着色标准的状态（子节点有一个红色的叔叔）。有两个关键区别：
当子节点没有红色叔节点时，您必须旋转，因为如果叔节点已经是黑色，那么将父节点设为黑色只会在祖父节点的一侧将黑色高度增加 1。这将违反红黑树的高度不变性并使树不平衡。
现在让我们看看旋转如何变换树，以便我们有一个带有红色叔叔的子节点并且可以使用重新着色。我建议把它画出来以完全理解它。
在旋转和重新着色之前，您有一个黑色祖父母，在 A 侧（左侧或右侧）有 2 个红色节点和 0 个黑色节点，在 B 侧（与 A 面相反）有 0 个红色节点和 1 个黑色节点。在旋转和重新着色之后，你有一个黑色的祖父母，A 侧有 1 个红色节点和 0 个黑色节点，B 侧有 1 个红色节点和 1 个黑色节点。所以你基本上将一个红色节点移动到另一个子树不增加任一子树的黑色高度的祖父母。
这就是旋转的魔力。它允许您将额外的红色节点移动到另一个分支而不改变黑色高度，并且仍然保留二叉搜索树的排序遍历属性。
逻辑相当简单。假设 z 是红色并且 z 的父节点是红色：如果 z 的叔叔是红色的，则执行步骤 1 将有问题的节点向上推，直到 (1) 父节点成为根节点。然后简单地将根标记为黑色。完成或 (2) z 的叔叔是黑人。
如果 (2) (a) z 是其父级的左孩子，则步骤 3 将是最后一步，因为 BST 的所有属性都已满足。完毕。或 (b) z 是其父母的右孩子。步骤 2 将问题转换为情况 (a)。然后执行步骤 3。完毕。
因此，逻辑是尝试到达情况（1）和（2a），以先到者为准。这些是我们知道解决方案的情况。
任何 2-4 (2-3-4) 树都可以转换为红黑树。并且理解 2-4 棵树要容易得多。如果你只是在 2-4 棵树中进行插入和删除操作，你会觉得不需要记住任何规则来实现相同的操作。您将看到一个清晰简单的逻辑，使您能够提出解决方案来处理不同的插入和删除场景。
一旦你对2-4棵树有了清晰的认识，当你处理红黑树的时候，你可以在脑海中将这棵红黑树映射到2-4棵树，然后自己想出一个逻辑。
我发现以下几个视频对于理解 2-4 树、红黑树以及 2-4 树到红黑树的映射非常有用。我建议浏览这些视频。
1) 对于 2-4 棵树：http ://www.youtube.com/watch?v=JZhdUb5F7oY&list=PLBF3763AF2E1C572F&index=13
2) 对于红黑树：http ://www.youtube.com/watch?v=JRsN4Oz36QU&list=PLBF3763AF2E1C572F&index=14
尽管它们每个都是一小时长的视频，但我觉得值得通过它们。
忽略我（现已删除）的评论 - 我认为冈崎的代码会帮助你。如果您有这本书（“纯功能数据结构”），请查看第 26 页的文本和图 3.5（面向，第 27 页）。很难比这更清楚。
不幸的是，在线提供的论文没有那部分。
我不打算将它复制出来，因为该图很重要，但它表明所有不同的情况基本上是相同的，并且它提供了一些非常简单的 ML 代码，可以很好地证明这一点。
[更新] 看起来你可以在亚马逊上看到这个。转到书的页面，将鼠标悬停在图像上，然后在搜索框中输入“红黑”。这会为您提供包含第 25 页和第 26 页的结果，但您需要登录才能查看它们（显然 - 我还没有尝试登录查看）。
这是我的实现：
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 circurm ...
对不起，你可以看看算法教程的教科书
没有人可以帮助您通过 rb-tree 进行思考。他们只能在某个关键点指导您。