ARTS （第10周）

最近在理解红黑树。
但红黑树的各种资料给我的感觉更多的是一个个的公式去套用。

我感觉是作者先设计出红黑树的基础结构，然后根据因为树形的结构，所以只要每次发生新增/删除只需要逐级向上处理修改的话效率就极高，然后红黑树作者根据这种思路，就开始统计做计算了。
红黑树的作者在设计这种结构的时候，这些的计算应该都是一个个情况的罗列、推导和测试出来.
因此，我感觉红黑树新增删除给我的感觉更多像一套套公式。

（个人的一点理解,可能有误）我感觉红黑树的调整公式可以有非常多种，只不过现有的公式比较完善。

本周：

红黑树

Algorithm 算法

红黑树（补全删除部分）

参考自JDK8 TreeMap源码

package jdk8test;

/**
 * @description
 * 
 * @author lfy
 */
public class RedBlackTree {

	
	public static void main(String[] args) {
		RedBlackTree rb = new RedBlackTree();
		// rb.adds(10, 40, 30, 60, 90, 70, 20, 50, 80);
		rb.adds(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);// 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
		System.out.println(rb.root);
		rb.remove(1);
		rb.remove(2);
		rb.remove(3);
		System.out.println(rb.root);
	}

	public void adds(int... vs) {
		for (int i : vs) {
			add(i);
		}
	}

	// 红黑色
	private enum Color {
		Red, Black
	}

	// 节点
	private class Node {
		// 颜色 ：默认红色
		private Color color;
		// 值
		private int val;
		// 父节点
		private Node parent;
		// 左节点
		private Node left;
		// 右节点
		private Node right;

		private Node() {
			// 默认红
			color = RED;
		}

		@Override
		public String toString() {
			return "{'color':'" + color + "', 'val':'" + val + "', 'left':" + left + ", 'right':" + right + "}";
		}

	}

	// 静态常量 红色和黑色
	private static final Color RED = Color.Red;
	private static final Color BLACK = Color.Black;
	// 根节点
	private Node root;
	// 大小
	private int size;

	/**
	 * 新增
	 * 
	 * @author lfy
	 * @param v
	 */
	public void add(int v) {
		Node n = new Node();
		n.val = v;
		// 根节点
		if (root == null) {
			root = n;
			root.color = BLACK;
			return;
		}
		// 重复不考虑
		if (exists(v)) {
			return;
		}
		// 非根节点
		// 根节点开始查找
		Node target = root;
		// 应该插入的是左节点还是右节点 true为左 right为右
		boolean isLeft = true;
		// 应该插入的节点的父节点
		Node p = null;
		// 查找节点
		while (target != null) {
			p = target;
			isLeft = v < target.val;
			if (isLeft) {
				target = target.left;
			} else {
				target = target.right;
			}
		}
		// 判断是左节点还是右节点
		if (isLeft) {
			p.left = n;
			n.parent = p;
		} else {
			p.right = n;
			n.parent = p;
		}
		// 调整
		fix1(n);
		size++;
	}

	/**
	 * 调整 第一版
	 * 
	 * @author lfy
	 * @param n
	 */
	private void fix1(Node n) {
		// 父节点是黑的 什么都不用做
		if (n.parent == null) {
			root = n;
			root.color = BLACK;
			return;
		}
		if (getColor(n.parent) == BLACK) {
			return;
		}
		Node p = n.parent;
		// 如果父节点是红的 祖父节点必定是黑的且非空的
		// 父节点是左节点还是右节点
		boolean isLeft = p.parent.left == p;
		// 叔叔节点
		Node u = isLeft ? p.parent.right : p.parent.left;
		// 叔叔节点是红的时候
		if (getColor(u) == RED) {
			// 叔叔节点也是红的时候
			changeColor(p, u, p.parent);
			// 祖父节点是红的时候 重新调整
			if (getColor(p.parent) == RED) {
				fix1(p.parent);
			}

			// 叔叔节点是黑色的 父节点是左节点
		} else if (isLeft) {
			// 当前节点是右节点 转成三点一线的形式（当前节点、父节点、祖父节点）
			if (n.parent.right == n) {
				// 关注节点改成原本的父节点 即现在的三点一线的三点里最下面的一点
				n = n.parent;
				rotateLeft(n);
			}
			if (n.parent.parent == null) {
				changeColor(n.parent);
			} else {
				Node pp = n.parent.parent;
				// 三点一线的情况下
				// 转变父节点和祖父节点颜色
				changeColor(n.parent, pp);
				// 右旋祖父节点 调整平衡性
				rotateRight(n.parent.parent);

				// 因为祖父节点变成了了红色 所以重新走一次
				fix1(pp);
			}
			// 叔叔节点是黑色的 父节点是右节点
		} else {
			// 当前节点是左节点 转成三点一线的形式（当前节点、父节点、祖父节点）
			if (n.parent.left == n) {
				n = n.parent;
				// 关注节点改成原本的父节点 即现在的三点一线的三点里最下面的一点
				rotateRight(n);
			}
			if (n.parent.parent == null) {
				changeColor(n.parent);
			} else {
				Node pp = n.parent.parent;
				// 转变父节点和祖父节点颜色
				changeColor(n.parent, pp);

				// 左旋祖父节点 调整平衡性
				rotateLeft(pp);
				// 因为祖父节点变成了了红色 所以重新走一次
				fix1(pp);
			}
		}

	}

	/**
	 * 左旋
	 * 
	 * @author lfy
	 * @param v
	 */
	private void rotateLeft(Node n) {

		if (n != null) {
			///////////////////////
			// 写完之后看了网络上的写法
			// 这里其实可以不写父属性了 可以少创建一个变量
			// 在右旋中做了这个更改
			//////////////////////
			// 父节点
			Node p = n.parent;
			// 右节点的左节点 即要左旋的另一个对象
			Node s = n.right;
			// 将子节点的左节点 赋值为关注节点的右节点
			n.right = s.left;
			if (s.left != null) {
				s.left.parent = n;
			}
			// 将子节点的左节点赋值为关注节点
			s.left = n;
			// 子节点的父节点修改为关注节点的父节点
			s.parent = p;
			// 关注节点的父节点修改为子节点
			n.parent = s;// --
			// 重新整理父节点的和子节点的关系
			if (p == null) {
				// 没有父节点 重设根节点
				root = s;
			} else if (p.left == n) {
				p.left = s;
			} else {
				p.right = s;
			}
		}
	};

	/**
	 * 右旋
	 * 
	 * @author lfy
	 * @param v
	 */
	private void rotateRight(Node n) {
		if (n != null) {
			// ps：写完之后看了网络上的写法 这里就不写父属性了 可以少创建一个变量
			// 父节点
			// Node p = n.parent;
			// 子节点
			Node s = n.left;
			// 将子节点的右节点给关注节点 改为关注节点的左节点
			n.left = s.right;
			if (s.right != null) {
				s.right.parent = n;
			}
			// 设置子节点的右节点为父节点
			s.right = n;
			// 重设子节点的父节点 修改为关注节点的父节点
			s.parent = n.parent;
			// 重设父节点的子节点属性
			if (n.parent == null) {
				root = s;
			} else if (n.parent.left == n) {
				n.parent.left = s;
			} else {
				n.parent.right = s;
			}
			// 重设关注节点的父节点
			n.parent = s;
		}
	};

	/**
	 * 获取节点颜色
	 * 
	 * @author lfy
	 * @param v
	 */
	private Color getColor(Node n) {
		if (n == null)
			return BLACK;
		return n.color;
	};

	/**
	 * 转换颜色
	 * 
	 * @author lfy
	 * @param n
	 */
	private void changeColor(Node... n) {
		// 遍历
		for (int i = 0; i < n.length; i++) {
			if (n[i].color == RED) {
				n[i].color = BLACK;
			} else {
				n[i].color = RED;
			}
		}
	};

	/**
	 * 二分查找 是否存在
	 * 
	 * @author lfy
	 * @return
	 */
	public boolean exists(int v) {
		Node n = root;
		while (n != null) {
			if (v < n.val) {
				n = n.left;
			} else if (v > n.val) {
				n = n.right;
			} else {
				return true;
			}

		}
		return false;
	}

	public void remove(int v) {
		Node target = root;
		// 查找节点
		while (target != null) {
			if (v < target.val) {
				target = target.left;
			} else if (v > target.val) {
				target = target.right;
			} else {
				break;
			}
		}
		// 没有
		if (target == null) {
			return;
		}
		// 删除节点
		removeNode(target);
		size--;
	}

	private void removeNode(Node p) {
		size--;

		// 是否左右节点都有 有的话 直接替换
		if (p.left != null && p.right != null) {
			Node s = findSuccessor(p);
			p.val = s.val;
			p = s;
		} // p has 2 children
			// 如果删除节点 是单节点的 replacement就是删除节点的非空节点
			// 否则 这个属性为空
		Node replacement = (p.left != null ? p.left : p.right);
		// 删除节点是单子节点的情况 这个时候 还没有用后继节点替代删除节点
		if (replacement != null) {
			// 如果单节点 直接替换关注节点P
			replacement.parent = p.parent;

			// 如果关注节点是根节点 直接重置root属性为继承节点
			if (p.parent == null)
				root = replacement;
			else if (p == p.parent.left)// 关注节点是左节点
				p.parent.left = replacement;// 直接替换左节点
			else// 关注节点是右节点
				p.parent.right = replacement;// 直接替换右节点
			// 全部清空
			p.left = p.right = p.parent = null;
			// 替换完成后 如果关注节点的颜色是黑色的 则开始调整
			if (p.color == BLACK)
				// 这里调用了第一次fixAfterDeletion，就是关注节点黑色，有孩子的情况
				fixAfterDeletion(replacement);
		} else if (p.parent == null) {
			// 关注节点无父节点也无子节点
			// P无父节点的时候 就代表了P也无无子节点 因为最初的判断会重设P属性
			// 如果P没有父节点 就代表了当前的树只有一个节点 所以直接删除根节点
			root = null;
		} else {
			// 关注节点有2个子节点的时候
			if (p.color == BLACK)
				// 这里调用了第二次fixAfterDeletion，就是情况关注节点黑色，没有孩子的情况 111
				fixAfterDeletion(p);

			// 如果还有节点指向删除节点 就去掉这些指向
			if (p.parent != null) {

				if (p == p.parent.left)
					p.parent.left = null;
				else if (p == p.parent.right)
					p.parent.right = null;
				p.parent = null;
			}
		}
	}

	/** From CLR */
	private void fixAfterDeletion(Node x) {
		while (x != root && getColor(x) == BLACK) {
			// 关注节点是左节点的时候
			if (x == x.parent.left) {
				// 获取兄弟节点
				Node sib = x.parent.right;
				// 兄弟节点是红色的时候
				if (getColor(sib) == RED) {
					// 兄弟节点和父节点 互换颜色 然后父节点左旋
					sib.color = BLACK;
					x.parent.color = RED;
					rotateLeft(x.parent);
					// 重新设置sib节点为当前的兄弟节点
					// 即原本的关注节点的近侄子节点
					sib = x.parent.right;
				}
				// 如果关注兄弟节点的后代都是黑色的
				if (getColor(sib.left) == BLACK && getColor(sib.right) == BLACK) {
					// 重设兄弟节点为红色
					sib.color = RED;
					// 关注节点 更改为关注节点的父节点
					x = x.parent;
				} else {// 如果兄弟节点的后代有红节点
					// 远侄子节点是黑色的时候
					if (getColor(sib.right) == BLACK) {
						// 设置近侄子节点为黑色
						sib.left.color = BLACK;
						// 设置兄弟节点为红色
						sib.color = RED;
						// 左旋
						rotateRight(sib);
						// 重新设置sib属性 也就是原本的的近侄子属性
						sib = x.parent.right;
					}
					// 重新设置sib颜色为原本关注节点的父节点颜色
					// 如果红就设置为红 黑就设置为红，保证正确性
					sib.color = getColor(x.parent);
					// 设置关注节点的父节点位黑
					x.parent.color = BLACK;
					// 设置远侄子属性为黑
					sib.right.color = BLACK;
					// 左旋关注节点
					rotateLeft(x.parent);
					x = root;
				}
			} else { // 这里就是完全镜像处理，就不做详细注释了
				// 获取兄弟节点（左节点）
				Node sib = x.parent.left;
				// 如果兄弟节点红色的 右旋 并互换父节点和兄弟节点的属性
				if (getColor(sib) == RED) {
					sib.color= BLACK;
					x.parent.color= RED;
					rotateRight(x.parent);
					sib = x.parent.left;
				}
				// 如果兄弟节点是黑色的 他的左节点也是黑色的（近侄子节点）
				// 设置兄弟为红色 将关注节点更改为 父节点
				if (getColor(sib.right) == BLACK && getColor(sib.left) == BLACK) {
					sib.color= RED;
					x = x.parent;
				} else {
					// 近侄子节点是红或者父节点是黑的

					// 近侄子节点是黑色的时候
					if (getColor(sib.left) == BLACK) {
						// 设置远侄子也为黑色
						sib.right.color= BLACK;
						// 设置兄弟节点为红色
						sib.color= RED;
						// 左旋
						rotateLeft(sib);
						// 重新设置兄弟节点为 原本的关注节点
						sib = x.parent.left;
					}
					sib.color= getColor(x.parent);
					x.parent.color= BLACK;
					sib.left.color= BLACK;
					rotateRight(x.parent);
					x = root;
				}
			}
		}
		x.color= BLACK;
	}

	/**
	 * 寻找继承节点
	 * 
	 * @author lfy
	 * @param n
	 * @return
	 */
	private Node findSuccessor(Node n) {
		if (n == null || n.right == null) {
			return null;
		}
		n = n.right;
		if (n.left != null) {
			n = n.left;
		}
		return n;
	}

	public int getSize() {
		return size;
	}
	
}

Review 英文文章

https://nodejs.org/en/docs/

node.js的文档，简略了解node.js

Tip 技巧

JDK源码treemap的红黑树的删除解析

其实就是各种情况的判断和解析，jdk源码里写的更精巧。

private void deleteEntry(Entry<K,V> p) {
       modCount++;
       size--;

      //是否左右节点都有 有的话 直接替换
       if (p.left != null && p.right != null) {
           Entry<K,V> s = successor(p);
           p.key = s.key;
           p.value = s.value;
           p = s;
       } // p has 2 children
	//如果删除节点 是单节点的 replacement就是删除节点的非空节点 
	//否则 这个属性为空
       Entry<K,V> replacement = (p.left != null ? p.left : p.right);
	//删除节点是单子节点的情况 这个时候 还没有用后继节点替代删除节点
       if (replacement != null) {	
		//如果单节点 直接替换关注节点P
		replacement.parent = p.parent;
		
           //如果关注节点是根节点 直接重置root属性为继承节点
           if (p.parent == null)
               root = replacement;
           else if (p == p.parent.left)//关注节点是左节点
               p.parent.left  = replacement;//直接替换左节点
           else//关注节点是右节点
               p.parent.right = replacement;//直接替换右节点
		//全部清空
             p.left = p.right = p.parent = null;
		  //替换完成后 如果关注节点的颜色是黑色的 则开始调整
           if (p.color == BLACK)
		//这里调用了第一次fixAfterDeletion，就是关注节点黑色，有孩子的情况
               fixAfterDeletion(replacement);
       } else if (p.parent == null) { 
		// 关注节点无父节点也无子节点
		//P无父节点的时候 就代表了P也无无子节点 因为最初的判断会重设P属性 
		//如果P没有父节点 就代表了当前的树只有一个节点 所以直接删除根节点
           root = null;
       } else { 
		//关注节点有2个子节点的时候 
           if (p.color == BLACK) 
			//这里调用了第二次fixAfterDeletion，就是情况关注节点黑色，没有孩子的情况 111
               fixAfterDeletion(p);
			
		//如果还有节点指向删除节点 就去掉这些指向
           if (p.parent != null) {
			
               if (p == p.parent.left)
                   p.parent.left = null;
               else if (p == p.parent.right)
                   p.parent.right = null;
               p.parent = null;
           }
       }
   }


   /** From CLR */
   private void fixAfterDeletion(Entry<K,V> x) {
       while (x != root && colorOf(x) == BLACK) {
		//关注节点是左节点的时候
           if (x == leftOf(parentOf(x))) {
			//获取兄弟节点 
               Entry<K,V> sib = rightOf(parentOf(x));
			//兄弟节点是红色的时候
               if (colorOf(sib) == RED) {
				//兄弟节点和父节点 互换颜色 然后父节点左旋
                   setColor(sib, BLACK);
                   setColor(parentOf(x), RED);
                   rotateLeft(parentOf(x));
				//重新设置sib节点为当前的兄弟节点 
				//即原本的关注节点的近侄子节点
                   sib = rightOf(parentOf(x));
               }
			//如果关注兄弟节点的后代都是黑色的
               if (colorOf(leftOf(sib))  == BLACK &&
                   colorOf(rightOf(sib)) == BLACK) {
				//重设兄弟节点为红色
                   setColor(sib, RED);
				//关注节点 更改为关注节点的父节点
                   x = parentOf(x);
               } else {//如果兄弟节点的后代有红节点
				//远侄子节点是黑色的时候
                   if (colorOf(rightOf(sib)) == BLACK) {
					//设置近侄子节点为黑色
                       setColor(leftOf(sib), BLACK);
					//设置兄弟节点为红色
                       setColor(sib, RED);
					//左旋
                       rotateRight(sib);
					//重新设置sib属性 也就是原本的的近侄子属性
                       sib = rightOf(parentOf(x));
                   }
				//重新设置sib颜色为原本关注节点的父节点颜色
                   //如果红就设置为红 黑就设置为红，保证正确性
				setColor(sib, colorOf(parentOf(x)));
				//设置关注节点的父节点位黑
                   setColor(parentOf(x), BLACK);
				//设置远侄子属性为黑
                   setColor(rightOf(sib), BLACK);
				//左旋关注节点
                   rotateLeft(parentOf(x));
                   x = root;
               }
           } else { // 这里就是完全镜像处理，就不做详细注释了
               //获取兄弟节点（左节点）
			Entry<K,V> sib = leftOf(parentOf(x));
			//如果兄弟节点红色的 右旋 并互换父节点和兄弟节点的属性
               if (colorOf(sib) == RED) {
                   setColor(sib, BLACK);
                   setColor(parentOf(x), RED);
                   rotateRight(parentOf(x));
                   sib = leftOf(parentOf(x));
               }
			//如果兄弟节点是黑色的 他的左节点也是黑色的（近侄子节点）
			//设置兄弟为红色 将关注节点更改为 父节点
               if (colorOf(rightOf(sib)) == BLACK &&
                   colorOf(leftOf(sib)) == BLACK) {
                   setColor(sib, RED);
                   x = parentOf(x);
               } else {
				//近侄子节点是红或者父节点是黑的
				
				//近侄子节点是黑色的时候
                   if (colorOf(leftOf(sib)) == BLACK) {
					//设置远侄子也为黑色
                       setColor(rightOf(sib), BLACK);
					//设置兄弟节点为红色
                       setColor(sib, RED);
					//左旋
                       rotateLeft(sib);
					//重新设置兄弟节点为 原本的关注节点
                       sib = leftOf(parentOf(x));
                   }
                   setColor(sib, colorOf(parentOf(x)));
                   setColor(parentOf(x), BLACK);
                   setColor(leftOf(sib), BLACK);
                   rotateRight(parentOf(x));
                   x = root;
               }
           }
       }

       setColor(x, BLACK);
   }

红黑树删除的个人总结

像JDK源码里，红黑树的删除分为了两部，第一步是替换或者删除，第二部分是调整

1、首先是替换/删除部分

这部分较容易理解，主体就是寻找后驱节点 替换或者删除，然后根据以下情况，判断是否需要进行调整

PS:删除的是红色节点的时候是不需要调整的。下面我就不再强调了。

可能1
删除节点有1个子节点
直接替换删除节点
如果删除节点是黑色的 将删除节点当作关注节点开始调整
可能2
删除节点是根节点 并且没有后代 直接清空
可能3
删除节点是有2个子节点
找到后驱节点 替换删除节点的属性
如果后驱节点是黑的 将后驱节点当作关注节点开始调整

2、调整部分

调整，其实就是一个一个情况的处理方案，或者说是公式。

调整操作 ，因为是存在2种可能，并且两种可能是呈现镜像的关系的
所以这里我只说一种 （删除节点是左节点，）
近侄子节点的概念为 兄弟节点有2个子节点
而关注节点如果是左节点
近侄子节点就为兄弟节点的左节点
远侄子节点就为兄弟节点的右节点
反之亦然
情况1 兄弟节点是红色的
兄弟和父节点互换颜色，然后父节点左旋
进入情况2、情况3判断
情况2 兄弟节点的后代都是黑的（空节点也算黑）
设置兄弟节点为红色
关注节点更改为关注节点的父节点 重新开始判断（因为父节点可能是红色）
如果关注节点不需要调整了，就将关注节点设置为黑色后结束。
情况3 兄弟节点的后代有红色的节点，并且远侄子节点是黑色节点（近侄子为红）
设置红色的近侄子节点为黑色后，兄弟节点为红，左旋兄弟节点
重置兄弟节点后进入判断4
情况4 兄弟节点的后代有红色的节点并且近侄子节点是红色节点
父节点的颜色复制给兄弟节点 将父节点改成黑色，左旋关注节点
然后将根节点设置为黑色。结束。

ps：如果发现我的总结有问题，欢迎联系下我！谢谢！

QQ：851127936

Share 分享

红黑树详细分析

https://segmentfault.com/a/1190000012728513#articleHeader6

其实最近看的红黑树文章很多很多个，我就把写的比较好的列出来了，但总感觉有差漏。

因此，最后我自己根据JDK的treemap源码做了一个小结。