面试题：Java TreeMap红黑树结构的删除操作及对平衡性的维护

Question

详细描述Java TreeMap中红黑树结构执行删除操作的完整过程，包括如何处理节点删除后对红黑树平衡性的维护，以及这个过程中可能涉及到的旋转和颜色调整操作的具体逻辑。

Answer 1

1. 删除节点的查找：
   • TreeMap基于红黑树实现，首先像普通二叉搜索树一样查找要删除的节点。
   • 若待删除节点有两个子节点，找到其右子树中的最小节点（该节点无左子节点），用此节点的值替换待删除节点的值，然后将问题转化为删除这个右子树中的最小节点。
   • 若待删除节点只有一个子节点（或没有子节点，此时子节点视为null），直接删除该节点，并让其父节点指向其唯一的子节点（若存在）。
2. 红黑树平衡性维护 - 基本情况分析：
   • 删除节点后，红黑树的性质可能被破坏。主要关注被删除节点（或其替代节点，若值替换情况）的颜色。
   • 若删除的是红色节点，不会影响红黑树的黑高，无需进一步调整。因为删除红色节点不会破坏从根节点到叶子节点路径上的黑色节点数量。
   • 若删除的是黑色节点，会导致其所在路径的黑高减少，需要进行调整来恢复红黑树的性质。
3. 旋转操作：
   • 左旋：
     • 假设当前节点为x，其右子节点为y。左旋操作将y提升为新的父节点，x变为y的左子节点，y的左子节点变为x的右子节点。
     • 左旋操作通常用于将右边较高的子树向左旋转，以平衡树结构。例如，当右子树过高，且红黑树性质被破坏时，可能需要左旋操作。
   • 右旋：
     • 假设当前节点为x，其左子节点为y。右旋操作将y提升为新的父节点，x变为y的右子节点，y的右子节点变为x的左子节点。
     • 右旋操作通常用于将左边较高的子树向右旋转，以平衡树结构。
4. 颜色调整操作：
   • 当删除黑色节点后，从被删除节点的父节点开始向上调整。
   • 设被删除节点的父节点为p，兄弟节点为s。
   • 情况1：兄弟节点s是红色：
     • 父节点p设为红色，兄弟节点s设为黑色。
     • 对父节点p进行左旋，左旋后新的兄弟节点（原来是s的左子节点）变为黑色。这样调整后，进入其他情况继续处理。
   • 情况2：兄弟节点s是黑色，且s的两个子节点都是黑色：
     • 将s设为红色。
     • 如果父节点p是黑色，以p为新的当前节点继续向上调整；如果父节点p是红色，将p设为黑色，结束调整。
   • 情况3：兄弟节点s是黑色，s的左子节点是红色，右子节点是黑色：
     • 将s设为红色，s的左子节点设为黑色。
     • 对s进行右旋，右旋后进入情况4继续处理。
   • 情况4：兄弟节点s是黑色，s的右子节点是红色：
     • 将s的颜色设为父节点p的颜色，父节点p设为黑色，s的右子节点设为黑色。
     • 对父节点p进行左旋，结束调整，此时红黑树性质恢复。