java面试 –红黑树（插入删除过程详解）
目录
红黑树性质
红黑树是一种自平衡二叉树，在平衡二叉树的基础上每个节点又增加了一个颜色的属性，节点的颜色只能是红色或黑色。具有以下性质：
（1）节点要么是红色，要么是黑色，
（2）根节点只能是黑色；
（3）性质3.所有叶子都是黑色。（叶子是NUIL节点）
（4）红色节点的父节点和左右孩子节点都是黑色，及黑红相间；
（5）在任何一棵子树中，从根节点向下走到空节点的路径上所经过的黑节点的数目相同，从而保证了是一个平衡二叉树。
红黑树的操作
因为每一个红黑树也是一个特化的二叉查找树，因此红黑树上的查找操作与普通二叉查找树上的查找操作相同。然而，在红黑树上进行插入操作和删除操作会导致不 再符合红黑树的性质。恢复红黑树的属性需要少量(O(log n))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。 虽然插入和删除很复杂，但操作时间仍可以保持为 O(log n) 次 。
红黑树的优势
红黑树能够以O(log2(N))的时间复杂度进行搜索、插入、删除操作。此外,任何不平衡都会在3次旋转之内解决。这一点是AVL所不具备的。
而且实际应用中，很多语言都实现了红黑树的数据结构。比如 TreeMap, TreeSet(Java )、 STL(C++)等。
左旋右旋
插入过程
默认插入的结点为红色。为何？
因为红黑树中黑节点至少是红节点的两倍，因此插入节点的父节点为黑色的概率较大，而此时并不需要作任何调整，因此效率较高。
1. 父为黑
插入后无需任何操作。由于黑节点个数至少为红节点的两倍，因此父为黑的情况较多，而这种情况在插入后无需任何调整，这就是红黑树比AVL树插入效率高的原因！
2. 父为红
父为红的情况破坏了红黑树的性质，此时需要根据叔叔的颜色来做不同的处理。
叔叔为红
此时很简单，只需交换爸爸、叔叔和爷爷的颜色即可。
此时若爷爷节点和太爷爷节点颜色相同，再以爷爷节点为起始节点，进行刚才相同的操作，即：根据爷爷的兄弟颜色做相应的操作。
叔叔为黑
- 爸爸在左、叔叔在右、我在左
以爸爸为根节点，进行一次R旋转。
- 爸爸在左、叔叔在右、我在右
先以我为根节点，进行一次L旋转；
再以我为根节点，进行一次R旋转。
- 叔叔在左、爸爸在右、我在左
先以我为根节点，进行一次R旋转；
再以我为根节点，进行一次L旋转。
- 叔叔在左、爸爸在右、我在右
以爸爸为根节点，进行一次L旋转。
删除过程
二叉搜索树的删除
若删除二叉搜索树的节点A，实际上删除的是二叉搜索树中序遍历的前驱节点，注意：
1. 这个被删除节点要么就是一个叶子节点，
2. 要么有且仅有一个左孩子
然后将孩子顶替它原来的位置，最后将被删的节点值覆盖待删除的那个节点A。
红黑树按照二叉搜索树的方式删除节点，之后再进行相应的旋转操作，使得删除后的树仍然是一棵红黑树。
定义
- 待删除节点：要删除的那个节点
- 实际删除节点：待删除节点的中序遍历前驱
红黑树实际删除节点的性质
- 实际删除节点要么是叶子节点，要么有且仅有一个左孩子；
- 若为叶子节点，必为红色；
- 若实际删除节点还有孩子，则该必为左孩子；
a）若左孩子为红色，则实际删除节点必为黑色；
b）若左孩子为黑色，则实际删除节点红黑均可以。
A. 删除的是叶子节点且该叶子节点是红色的 ---> 无需修复，因为它不会破坏红黑树的5个特性
B. 删除的是叶子节点且该叶子节点是黑色的 ---> 很明显会破坏特性5，需要修复。
C. 删除的节点（为了便于叙述我们将其称为P）下面有一个子节点 S，对于这种情况我们通过 将P和S的值交换的方式，巧妙的将删除P变为删除S，S是叶子节点，这样C这种情况就会转 换为A, B这两种情况：
C1： P为黑色，S为红色 ---> 对应 A 这种情况
C2: P为黑色或红色，S为黑色 --- > 对应 B 这种情况
D. 删除的节点有两个子节点，对于这种情况，我们通过将P和它的后继节点N的值交换的方 式，将删除节点P转换为删除后继节点N，而后继节点只可能是以下两种情况：
D1: N是叶子节点 --- > 对应情况 A 或 B
D2: N有一个子节点 ---- > 对应情况 C
所以通过上面的分析我们发现，红黑树节点删除后的修复操作都可以转换为 A 或 B这两种情况，而A不需要修复，所以我们只需要研究B这种情况如何修复就行了。
下面我们讨论如何修复B中情况：
插入代码
第一步 判读有没有根结点
第二步 如果父为黑 直接插入
第三步 如果父为红 如果叔叔为红 父叔进行变色（函数），递归
第四步 如果叔叔为黑 继续判断 父左叔右我左 R （函数）
父左叔右我右 LR（函数）
叔左父右我左 RL（函数）
叔左父右我右 L （函数）
public class RBTree<T extends Comparable<T>> {
public static void main(String[] args) {
///*
int[] testNum = new int[]{15, 1, 3, 6, 8, 20, 22, 43, 67};
RBTree<Integer> *** = new RBTree<Integer>();
for (int i = 0; i < testNum.length; i++) {
***.insertNode(testNum[i]);
}
System.out.println(***.root.data);
//*/
/*
RBTree<Character> *** = new RBTree<Character>();
***.insertNode('F');
***.insertNode('G');
***.insertNode('D');
***.insertNode('B');
***.insertNode('C');
System.out.println(***.root.data);
*/
}
private static final boolean RED = true;
private static final boolean BLACK = false;
private TreeNode<T> root;
/**
* 插入一个新的节点，插入完毕后符合红黑树性质
*
* @param data 需要插入的数据
*/
public void insertNode(T data) {
TreeNode<T> curr;
TreeNode<T> parent = toTargetParent(data);
if (parent == null) {
curr = root = new TreeNode<T>(data);
} else {
if (data.compareTo(parent.data) < 0) {
curr = parent.left = new TreeNode<T>(data);
curr.parent = parent;
} else {
curr = parent.right = new TreeNode<T>(data);
curr.parent = parent;
}
}
fixupTree(curr);
}
/**
* 修复红黑树的不平衡状态
*
* @param node 新增节点
*/
private void fixupTree(TreeNode node) {
TreeNode parent = null, grandParent = null;
boolean parentColor = false, uncleColor = false;
if (node != root) {
parent = node.parent;
grandParent = parent.parent;
parentColor = parent.color;
uncleColor = getUncleColor(node);
}
//父节点为空表示其为根节点
if (parent == null && node.color == RED) {
node.color = BLACK;
} else if (parentColor == RED && uncleColor == RED) {
changeColor(grandParent);
//再次判断根节点是否满足要求
fixupTree(grandParent);
} else if (parentColor == RED && uncleColor == BLACK) {
dispatchRotation(grandParent, parent, node);
}
}
/**
* 判断属于哪种四种情况，LL、LR、RR、RL，使用正确的旋转
*
* @param grandParent 祖父节点
* @param parent 父节点
* @param child 新增节点
*/
private void dispatchRotation(TreeNode grandParent, TreeNode parent, TreeNode child) {
if (grandParent.left == parent) {
if (parent.left == child) {
rightRotation(grandParent);
} else {
leftRotation(parent);
rightRotation(grandParent);
}
} else {
if (parent.left == child) {
rightRotation(parent);
leftRotation(grandParent);
} else {
leftRotation(grandParent);
}
}
}
/**
* 改变祖父节点以及两个子节点的颜色
*
* @param grandParent 传入新增节点的祖父
*/
private void changeColor(TreeNode grandParent) {
grandParent.color = RED;
if (grandParent.left != null) {
grandParent.left.color = BLACK;
}
if (grandParent.right != null) {
grandParent.right.color = BLACK;
}
}
/**
* 返回叔叔节点的颜色
*
* @param node 一个节点
* @return 其叔叔节点的颜色
*/
private boolean getUncleColor(TreeNode node) {
TreeNode parent = node.parent;
//如果当前结点的祖父是空的，说明是其父节点是根节点
return getBrotherColor(parent.parent == null ? node : parent);
}
/**
* 返回兄弟节点的颜色
*
* @param child 传入节点
* @return 返回兄弟节点的颜色
*/
private boolean getBrotherColor(TreeNode child) {
TreeNode parent = child.parent;
if (parent.left == child && parent.right != null) {
return parent.right.color;
} else if (parent.right == child && parent.left != null) {
return parent.left.color;
} else {
return BLACK;
}
}
/**
* 将传入的节点的右子节点提升为新的父节点，传入节点降为其右子节点
* 注意颜色、父节点需要处理，务必要清除传入节点的右子节点，因为其已经被提升了父节点了。
* @param curr 一个节点
*/
private void leftRotation(TreeNode curr) {
TreeNode tParent = curr.right;
tParent.parent = curr.parent;
tParent.color = BLACK;
//新父节点的左子节点,放在传入节点的右边
curr.right = tParent.left;
if (tParent.left != null) {
tParent.left.parent = curr;
}
//降为子节点前的数据整理
curr.color = RED;
curr.parent = tParent;
tParent.left = curr;
setChild(curr, tParent);
}
/**
* 将传入的节点的左子节点提升为新的父节点，传入节点降为其右子节点
* 注意颜色、父节点需要处理，务必要清除传入节点的左子节点，因为其已经被提升了父节点了。
* @param curr 一个节点
*/
private void rightRotation(TreeNode curr) {
//新的父节点
TreeNode tParent = curr.left;
tParent.parent = curr.parent;
tParent.color = BLACK;
//新父节点的右子节点,放在传入节点的左边
curr.left = tParent.right;
if (tParent.right != null) {
tParent.right.parent = curr;
}
//传入节点降为子节点前的数据整理
curr.color = RED;
curr.parent = tParent;
tParent.right = curr;
setChild(curr, tParent);
}
/**
* 使旋转在树中生效
*
* @param roNode 被旋转的节点
* @param newParent 被旋转之后的父节点
*/
private void setChild(TreeNode roNode, TreeNode newParent) {
TreeNode roNodeParent = newParent.parent;
if (roNodeParent == null) {
root = newParent;
} else if (roNodeParent.left == roNode) {
roNodeParent.left = newParent;
} else {
roNodeParent.right = newParent;
}
}
/**
* 调到data存放位置的父节点处
* @param data 用于对比的数据
* @return data可存放处的父节点
*/
private TreeNode<T> toTargetParent(T data) {
TreeNode<T> curr = root;
TreeNode<T> parent = root;
while (curr != null) {
parent = curr;
if (data.compareTo(curr.data) < 0) {
curr = curr.left;
} else {
curr = curr.right;
}
}
return parent;
}
/**
* 内部节点
*/
static class TreeNode<T extends Comparable<T>> {
T data;
boolean color;
//伪删除
boolean isDeleted;
TreeNode<T> left;
TreeNode<T> right;
TreeNode<T> parent;
TreeNode(T data, boolean color) {
this.data = data;
this.color = color;
}
TreeNode(T data) {
this.data = data;
this.color = RED;
}
}
}删除代码
/**
* 删除 叶子节点 后的修复过程
* @param deletedNode 被删除的节点
* @param deletedNodeParent 被删除节点的父节点
*/
private void deleteLeafFix(Node deletedNode){
while((deletedNode != root) && (BLACK == deletedNode.color)){
Node parent = deletedNode.parentNode;
Node brother = getBrother(deletedNode);
if(deletedNode.key.compareTo(parent.key) > 0){ // 删除的是右叶子节点
if(RED == brother.color){ // case5: 如果该兄弟节点是红色的，那么根据红黑树的特性可以得出它的一定有两个黑色的子节点
brother.color = BLACK;
brother.rightNode.color = RED;
rightRotation(parent);
break;
}else{
if((null == brother.leftNode) && (null == brother.rightNode)){ // case4: 兄弟节点是黑色的，且没有子节点
brother.color = RED; // 将兄弟节点设为红色，将父节点设为当前节点递归， 直到根节点，或遇到红色节点，
deletedNode = parent;
}else{
if((null != brother.leftNode) && (RED == brother.leftNode.color)){// case1: 兄弟节点是黑色的，且有一个左节点（可以断定 左节点是红色的）
//case3: 兄弟节点是黑色的，且有两个节点（可以断定 左右节点都是红色的） 这个和情况 1 是一样的
brother.color = parent.color;
parent.color = BLACK;
brother.leftNode.color = BLACK;
rightRotation(parent);
break;
}else{// case2: 兄弟节点是黑色的，且有一个右节点（可以断定 右节点是红色的）
brother.rightNode.color = BLACK;
brother.color = RED;
leftRotation(brother);
}
}
}
}else{// 删除的是左叶子节点
if(RED == brother.color){ // case5 : 如果该兄弟节点是红色的，那么根据红黑树的特性可以得出它的一定有两个黑色的子节点
brother.color = BLACK;
brother.leftNode.color = RED;
leftRotation(parent);
break;
}else{
if((null == brother.leftNode) && (null == brother.rightNode)){ // case4: 兄弟节点是黑色的，且没有子节点
brother.color = RED; // 将兄弟节点设为红色，将父节点设为当前节点递归， 直到根节点，或遇到红色节点，
deletedNode = parent;
}else{
if((null != brother.rightNode) && (RED == brother.rightNode.color)){ // case1 : 兄弟节点是黑色的，且有一个右节点（可以断定 右节点是红色的）
// case3 : 兄弟节点是黑色的，且有两个节点（可以断定 左右节点都是红色的） 这个和情况 1 是一样的
brother.color = parent.color;
parent.color = BLACK;
brother.rightNode.color = BLACK;
leftRotation(parent);
break;
}else{ // case2: 兄弟节点是黑色的，且有一个左节点（可以断定 左节点是红色的）
brother.leftNode.color = BLACK;
brother.color = RED;
rightRotation(brother);
}
}
}
}
}
deletedNode.color = BLACK;
}
private Node getBrother(Node node){
if(null == node){
return null;
}
Node parent = node.parentNode;
if(null == parent){
return null;
}
if(node.key.compareTo(parent.key) > 0){
return parent.leftNode;
}else{
return parent.rightNode;
}
}
public boolean delete(K key){
if(null != key){
if(null != root){
return deleteNode(key, root, null);
}
}
return false;
}
private boolean deleteNode(K key, Node current, Node parent){
if(null != current){
if(key.compareTo(current.key) > 0){
return deleteNode(key, current.rightNode, current);
}
if(key.compareTo(current.key) < 0){
return deleteNode(key, current.leftNode, current);
}
if(key.compareTo(current.key) == 0){
if((null != current.leftNode) && (null != current.rightNode)){ //将要删除的节点下有两个子节点
dleTwoChildrenNode(current);
return true;
}else{
if((null == current.leftNode) && (null == current.rightNode)){ //将要删除的节点没有子节点
deleteLeafFix(current);
if(current.key.compareTo(parent.key) > 0){
parent.rightNode = null;
}else{
parent.leftNode = null;
}
return true;
}else{ // 将要删除的节点下有一个子节点,
dleOneChildNode(current);
return true;
}
}
}
}
return false;
}
private void dleOneChildNode(Node delNode){
Node replaceNode = (null == delNode.leftNode) ? delNode.rightNode : delNode.leftNode;
deltetLeafNode(delNode, replaceNode);
}
/**
* 处理被删除节点有两个子节点的情况
* @param target 将要被删除的节点
*/
private void dleTwoChildrenNode(Node target){
Node replaceNode = successor(target);
if((null == replaceNode.rightNode) && (null == replaceNode.leftNode)){
deltetLeafNode(target, replaceNode);
}else{
target.key = replaceNode.key;
target.value = replaceNode.value;
dleOneChildNode(replaceNode);
}
}
private void deltetLeafNode(Node target, Node replaceNode){
target.key = replaceNode.key;
target.value = replaceNode.value;
deleteLeafFix(replaceNode);
if(replaceNode == replaceNode.parentNode.rightNode){
replaceNode.parentNode.rightNode = null;
}else{
replaceNode.parentNode.leftNode = null;
}
}
//找后继结点。即，查找"红黑树中数据值大于该结点"的"最小结点"
private Node successor(Node node) {
if (node == null){
return null;
}
if (null != node.rightNode) { // 获取 后继节点
Node p = node.rightNode;
while (null != p.leftNode){
p = p.leftNode;
}
return p;
} else {
Node p = node.parentNode;
Node ch = node;
while (p != null && ch == p.rightNode) {
ch = p;
p = p.parentNode;
}
return p;
}
}
public static void main(String[] args) {
RedBlackTree<Integer, String> bst = new RedBlackTree<Integer, String>();
bst.put(100, "v100");
bst.put(50, "v50");
bst.put(150, "v150");
bst.put(20, "v20");
bst.put(85, "v85");
bst.put(10, "v10");
bst.put(15, "a15");
bst.put(75, "v75");
bst.put(95, "v95");
bst.put(65, "v65");
bst.put(76, "v76");
bst.put(60, "v60");
bst.put(66, "v66");
bst.put(61, "v61");
// 当前节点是左节点 的 5中情况
//bst.delete(15); // 1. 兄弟节点是黑色的，且有一个右节点（可以断定 右节点是红色的）
// 2. 兄弟节点是黑色的，且有一个左节点（可以断定 左节点是红色的
//bst.put(140, "v140");
//bst.delete(95);
// 4. 兄弟节点是黑色的，且没有子节点
//bst.delete(66);
//5. 如果该兄弟节点是红色的，那么根据红黑树的特性可以得出它的一定有两个黑色的子节点
//bst.delete(95);
//bst.delete(15);
System.out.println(bst.getRoot());
}参考链接
https://www.cnblogs.com/LiaHon/p/11221634.html
京公网安备 11010502036488号