爱威尔-java红黑树原理与实现

首先大家要思考一个问题树为什么要平衡？也许是废话但是平衡的含义却意义深远，如果不能保障树的平衡我们还研究运用树干嘛，计算机里面对树的应用基本都是平衡还得有序。 
 上一节我也说过树在计算机领域的应用主要体现在持久化存储方面，我想应该跟这个有关能持久化存储还能快速查询出来的数据结构在我们认知范围内也许树是最有效的选择。 
 但是树是没有什么特定的特性的树也是很随意的所以才有了各种各样的特性约束这个树，正好对这些约束我们还可以用数学语言来描述表达而数学正好可以被计算机解释，这似乎是一种不谋而合。 
 <img src="92/20180404200454_68.png" alt=""> 
 右旋----1,2,3 
 <img src="92/20180404200522_204.png" alt=""> 
 左旋 
 <img src="92/20180404200546_842.jpg" alt=""> 
 
 
<pre class="prettyprint lang-java">package weir.suanfa.rbtree;
/**
 * 红黑树
* @author weir 
* 2017年11月30日 上午11:00:05 
*
 */
public class RBNode {

private int id;
	private int data;
	
	private RBNode leftChild;
	private RBNode rightChild;
	/**
	 * 节点颜色
	 */
	private boolean red = true;
	/**
	 * 父节点
	 */
	private RBNode parent;
	
	public RBNode(int id, int data,boolean red) {
		super();
		this.id = id;
		this.data = data;
		this.red = red;
	}
	public int getId() {
		return id;
	}
	public void setId(int id) {
		this.id = id;
	}
	public int getData() {
		return data;
	}
	public void setData(int data) {
		this.data = data;
	}
	public RBNode getLeftChild() {
		return leftChild;
	}
	public void setLeftChild(RBNode leftChild) {
		this.leftChild = leftChild;
	}
	public RBNode getRightChild() {
		return rightChild;
	}
	public void setRightChild(RBNode rightChild) {
		this.rightChild = rightChild;
	}
	public boolean isRed() {
		return red;
	}
	public void setRed(boolean red) {
		this.red = red;
	}
	public RBNode getParent() {
		return parent;
	}
	public void setParent(RBNode parent) {
		this.parent = parent;
	}
	@Override
	public String toString() {
		return "RBNode [id=" + id + ", data=" + data + ", leftChild=" + leftChild + ", rightChild=" + rightChild
				+ ", red=" + red + ", parent=" + parent + "]";
	}
}
</pre> 
 
 
<pre class="prettyprint lang-java">package weir.suanfa.rbtree;

/**
 * 红黑树操作
 * 
 * @author weir 2017年11月30日 上午11:01:29
 *
 */
public class RBTree {

/**
	 * 根节点
	 */
	private RBNode root;
	/**
	 * 标识找到的节点是父节点的左子还是右子
	 */
	private boolean isLeftNode = true;

/**
	 * 查找一个节点
	 * 
	 * @param key
	 * ID值
	 * @return
	 */
	public RBNode find(int key) {
		RBNode current = root;
		while (current.getId() != key) {
			// 如果key小于当前节点，就去找左边比当前小的节点
			if (current.getId() > key) {
				current = current.getLeftChild();
				// 如果key大于当前节点，就去找右边比当前大的节点
			} else if (current.getId() < key) {
				current = current.getRightChild();
			}
			if (current == null) {
				return null;
			}
		}
		return current;
	}

/**
	 * 插入节点
	 * 
	 * @param id
	 * @param data
	 */
	public void insert(int id, int data) {
		RBNode newNode = new RBNode(id, data,true);
		if (root == null) {
			root = newNode;
		} else {
			RBNode current = root;
			RBNode parent = null;
			while (true) {
				parent = current;
				// 如果新节点小于当前节点，我们就去左子节点找
				if (id < current.getId()) {
					current = current.getLeftChild();
					// 如果没有左子节点，说明我们找到了，可以将新节点插入到此
					if (current == null) {
						parent.setLeftChild(newNode);
						//相对于二叉搜索树新加
						newNode.setParent(parent);
						break;
					}
				} else {// 右边
					current = current.getRightChild();
					// 如果没有右子节点，说明我们找到了，可以将新节点插入到此
					if (current == null) {
						parent.setRightChild(newNode);
						//相对于二叉搜索树新加
						newNode.setParent(parent);
						break;
					}
				}
			}

}
		//相对于二叉搜索树新加
		// 调整为红黑树
		afterInsert(newNode);

}

/**
	 * 加入新节点后，校验红黑树并调整
	 * @param node
	 */
	private void afterInsert(RBNode node) {
		// 1：如果插入的是根节点，那么违反规则2，就直接把节点修改为黑色
		if (node.getParent() == null) {
			node.setRed(false);
			root = node;
		}
		// 2：如果插入节点的父节点是黑色的，说明符合规则，什么都不做
		else if (!node.getParent().isRed()) {
		}
		else if (node.getParent().isRed()) {
			// 祖父
			RBNode g = node.getParent().getParent();
			// 叔父
			RBNode u = null;
			if (g != null) {
				u = (g.getLeftChild() == node.getParent()) ? g.getRightChild() : g.getLeftChild();
			}

if (u != null) {
				// 3：如果插入节点的父节点是红色的，且祖父结点的另一个子节点（叔叔节点）也是
				// 红色的，那么：将祖父节点变红，而父和叔节点变黑，然后设置祖父节点为当前
				// 节点，然后重新开始判断。
				g.setRed(true);
				u.setRed(false);
				node.getParent().setRed(false);
				node = g;
				this.afterInsert(node);
			} else if ((u == null || !u.isRed()) && node == node.getParent().getLeftChild()
					&& (g!=null && node.getParent() == g.getLeftChild())) {
				// 4：如果插入节点的父节点是红色，而叔节点是黑色，且插入节点是其父的左子节
				// 点，而父节点是祖父节点的左子节点，那么：把父节点变为黑色，祖父节点变为
				// 红色，然后对祖父节点进行右旋，然后重新开始判断。

node.getParent().setRed(false);
				g.setRed(true);
				this.rightRotate(g);
				this.afterInsert(node);

} else if ((u == null || !u.isRed()) && node == node.getParent().getRightChild()
					&& (g!=null && node.getParent() == g.getRightChild())) {
				// 5：如果插入节点的父节点是红色，而叔节点是黑色，且插入节点是其父的右子节点，而父节
				// 点是祖父节点的右子节点，那么：把父节点变为黑色，祖父节点变为红色，然后对祖父节
				// 点进行左旋，然后重新开始判断。

node.getParent().setRed(false);
				g.setRed(true);
				this.leftRotate(g);
				this.afterInsert(node);
			} else if ((u == null || !u.isRed()) && node == node.getParent().getRightChild()
					&& (g!=null && node.getParent() == g.getLeftChild())) {
				// 6：如果插入节点的父节点是红色，而叔节点是黑色，且插入节点是其父的右子节点，而父节
				// 点是祖父节点的左子节点，那么：把当前节点的父节点做为新的当前节点，对新的当前节
				// 点进行左旋，然后重新开始判断。

RBNode oldParent = node.getParent();
				this.leftRotate(oldParent);

this.afterInsert(oldParent);

} else if ((u == null || !u.isRed()) && node == node.getParent().getLeftChild()
					&& (g!=null && node.getParent() == g.getRightChild())) {
				// 7：如果插入节点的父节点是红色，而叔节点是黑色，且插入节点是其父的左子节点，而父节
				// 点是祖父节点的右子节点，那么：把当前节点的父节点做为新的当前节点，对新的当前节
				// 点进行右旋，然后重新开始判断。
				RBNode oldParent = node.getParent();
				this.rightRotate(oldParent);

this.afterInsert(oldParent);
			}

}

/**
	 * 右旋-梳理关系
	 * @param node
	 */
	private void rightRotate(RBNode node) {
		// 右旋节点 原始的左子节点
		RBNode oldLeftChild = node.getLeftChild();
		// 右旋节点 原始的左子节点的 右子节点
		RBNode oldLeftRightChild = null;
		if (oldLeftChild != null) {
			oldLeftRightChild = oldLeftChild.getRightChild();
		}
		// 关系1--是否有父节点
		if (node.getParent() != null) {
			// 判断是父节点的左子还是右子
			boolean isLeft = (node.getParent().getLeftChild() == node);
			if (isLeft) {
				node.getParent().setLeftChild(oldLeftChild);
			} else {
				node.getParent().setRightChild(oldLeftChild);
			}

if (oldLeftChild != null) {
				oldLeftChild.setParent(node.getParent());
			}

} else {
			oldLeftChild.setParent(null);
			oldLeftChild.setRed(false);
			root = oldLeftChild;
		}
		// 关系2
		if (oldLeftChild != null) {
			oldLeftChild.setRightChild(node);
		}
		node.setParent(oldLeftChild);
		// 关系3
		node.setLeftChild(oldLeftRightChild);
		if (oldLeftRightChild != null) {
			oldLeftRightChild.setParent(node);
		}

}

/**
	 * 左旋
	 * @param node
	 */
	private void leftRotate(RBNode node) {
		// 左旋节点 原始的右子节点
		RBNode oldRightChild = node.getRightChild();
		// 左旋节点 原始的右子节点的 左子节点
		RBNode oldRightLeftChild = null;
		if (oldRightChild != null) {
			oldRightLeftChild = oldRightChild.getLeftChild();
		}
		// 关系1
		if (node.getParent() != null) {
			// 判断是父节点的左子还是右子
			boolean isLeft = (node.getParent().getLeftChild() == node);
			if (isLeft) {
				node.getParent().setLeftChild(oldRightChild);
			} else {
				node.getParent().setRightChild(oldRightChild);
			}

if (oldRightChild != null) {
				oldRightChild.setParent(node.getParent());
			}

} else {
			oldRightChild.setParent(null);
			oldRightChild.setRed(false);
			root = oldRightChild;
		}
		// 关系2
		if (oldRightChild != null) {
			oldRightChild.setLeftChild(node);
		}
		node.setParent(oldRightChild);
		// 关系3
		node.setRightChild(oldRightLeftChild);
		if (oldRightLeftChild != null) {
			oldRightLeftChild.setParent(node);
		}
	}

//////////////
	/**
	 * 前序---获取节点数据
	 * 
	 * @param node
	 */
	public void preOrder(RBNode node) {
		if (node != null) {
			String pId = "";
			if (node.getParent() != null && node.getParent().getId()>0) {
				pId = ""+node.getParent().getId();
			}
			if (node.getId()>=0) {
				System.out.println(node.getId() +","+node.isRed()+","+pId +" ---- ");
			}
			
			preOrder(node.getLeftChild());
			preOrder(node.getRightChild());
		}
	}

/**
	 * 中序--获取节点数据
	 * 
	 * @param node
	 */
	public void inOrder(RBNode node) {
		if (node != null) {
			inOrder(node.getLeftChild());
			System.out.println(node.getId() + " - ");
			inOrder(node.getRightChild());
		}
	}

/**
	 * 后序--获取节点数据
	 * 
	 * @param node
	 */
	public void aftOrder(RBNode node) {
		if (node != null) {
			aftOrder(node.getLeftChild());
			aftOrder(node.getRightChild());
			System.out.println(node.getId() + " - ");
		}
	}

/**
	 * 获取最小节点数据
	 * 
	 * @param node
	 */
	public RBNode getMinNode() {
		RBNode current = root;
		RBNode minNode = null;
		while (current != null) {
			minNode = current;
			current = current.getLeftChild();
		}
		return minNode;
	}

/**
	 * 获取最大节点数据
	 * 
	 * @param node
	 */
	public RBNode getMaxNode() {
		RBNode current = root;
		RBNode maxNode = null;
		while (current != null) {
			maxNode = current;
			current = current.getRightChild();
		}
		return maxNode;
	}

/**
	 * 删除一个节点
	 * 
	 * @param key
	 * @return
	 */
	public boolean delete(int key) {
		// 找到需要删除的节点
		RBNode current = root;
		RBNode parent = root;
		//来记录顶替被删除节点的那个节点
		RBNode nowNode = null;
		current = this.findOneNode(root, key);
		if (current == null) {
			return true;
		}
		
		parent = current.getParent();
		
//		while (current.getId() != key) {
//			parent = current;
//			if (current.getId() > key) {
//				isLeftNode = true;
//				current = current.getLeftChild();
//			} else if (current.getId() < key) {
//				isLeftNode = false;
//				current = current.getRightChild();
//			}
//			if (current == null) {
//				return false;
//			}
//		}

// 1.没有子节点
		if ((current.getLeftChild() == null || current.getLeftChild().getId()<0) 
				&& (current.getRightChild() == null 
				|| current.getRightChild().getId() <0)) {
			this.noChild(parent, current, isLeftNode);
//			1：如果删除节点是叶子节点
//			（1）如果删除节点是红色的，那就直接删除，不做其它操作
//			（2）如果删除节点是黑色的，那么就创建一个空节点来顶替删除节点，然后按照后
//			面的调整步骤进行调整
			if (parent!=null) {
				if (!current.isRed()) {
					nowNode = new RBNode(-1, -1,false);
					nowNode.setParent(current.getParent());
					if (this.isLeftNode) {
						parent.setLeftChild(nowNode);
					}else {
						parent.setRightChild(nowNode);
					}
				}
			}
			
			
			current.setParent(null);
		}
		// 2.只有一个节点
//		2：如果删除节点有一个子节点，把后来顶替被删节点的那个节点成为顶替节点，如
//		果删除节点为黑，而且顶替节点也为黑，那么把顶替节点当作当前节点，然后按
//		照后面的调整步骤进行调整。
//		1：当前节点是红，那么：直接把当前节点变成黑色，结束
		else if (current.getRightChild() == null || current.getRightChild().getId()<0) {
			this.oneLeftNode(parent, current, isLeftNode);
			
			if (!current.isRed() && current.getLeftChild().isRed()) {
				current.getLeftChild().setRed(false);
			}else if (!current.isRed() && !current.getLeftChild().isRed()) {
				nowNode = current.getLeftChild();
			}
		} else if (current.getLeftChild() == null || current.getLeftChild().getId()<0) {
			this.oneRightNode(parent, current, isLeftNode);
			
			if (!current.isRed() && current.getLeftChild().isRed()) {
				current.getRightChild().setRed(false);
			}else {
				nowNode = current.getRightChild();
			}
		}
		// 3.有两个子节点
//		3：如果删除节点有两个子节点，那么，找到其中序后继节点，把这两个节点的数据
//		交换一下，不要复制颜色，也不改变其原有的父子等关系，然后重新进行删除。
//		由于其中序后继节点只可能是叶子节点或者只有一个子节点，因此回到前面两
//		种情况。
		else {
			// 找到中序后继节点
			RBNode successor = this.getSuccessor(current);
			
			//把这两个节点的数据 交换一下，不要复制颜色，也不改变其原有的父子等关系
			RBNode tempNode = new RBNode(successor.getId(), successor.getData(), successor.isRed());
			
			successor.setId(current.getId());
			successor.setData(current.getData());
			
			current.setId(tempNode.getId());
			current.setData(tempNode.getData());
			
 //然后重新进行删除
			this.delete(successor.getId());
		}
		
		if (nowNode!=null) {
			afterDel(nowNode);
		}
		return true;
	}
	//删除节点之后的调整
	private void afterDel(RBNode nowNode) {
//		1：当前节点是红，那么：直接把当前节点变成黑色，结束
		if (nowNode.isRed()) {
			nowNode.setRed(false);
		}
//		2：当前节点是黑且是根节点，那么：什么都不用做，结束
		else if (nowNode.getParent() == null) {
			nowNode.setRed(false);
		}else if (!nowNode.isRed()) {
			RBNode g = nowNode.getParent().getParent();
			//兄弟节点
			RBNode b = (nowNode==nowNode.getParent().getLeftChild()) ? 
					nowNode.getParent().getRightChild():
						nowNode.getParent().getLeftChild();
			
//			3：当前节点是黑且兄弟节点为红色，当前节点为父节点的左子节点，那么：把兄弟
//			结点变成父节点的颜色，把父节点变成红色，然后在父节点上做左旋，再重新开
//			始判断。
			if(b.isRed() && nowNode==nowNode.getParent().getLeftChild()) {
				b.setRed(nowNode.getParent().isRed());
				nowNode.getParent().setRed(true);
				this.leftRotate(nowNode.getParent());
				this.afterDel(nowNode);
			}
//			4：当前节点是黑且兄弟节点为红色，当前节点为父节点的右子节点，那么：把兄弟
//			结点变成父节点的颜色，把父节点变成红色，然后在父节点上做右旋，再重新开
//			始判断。
			else if (b.isRed() && nowNode==nowNode.getParent().getRightChild()) {
				b.setRed(nowNode.getParent().isRed());
				nowNode.getParent().setRed(true);
				this.rightRotate(nowNode.getParent());
				this.afterDel(nowNode);
			}
//			5：当前节点是黑且父节点和兄弟节点都为黑色，兄弟节点的两个子节点全为黑色，
//			那么：把兄弟节点变红，然后把父节点当成新的当前节点，再重新开始判断
			else if (!b.isRed() && !nowNode.getParent().isRed() 
					&& (b.getLeftChild()==null || !b.getLeftChild().isRed())
					&& (b.getRightChild()==null || !b.getRightChild().isRed())) {
				b.setRed(true);
				nowNode = nowNode.getParent();
				this.afterDel(nowNode);
			}
//			6：当前节点是黑且兄弟节点为黑色，兄弟节点的两个子节点都是黑色，但是父节点
//			是红色，那么：就把兄弟节点变红，父节点变黑，结束
			else if (!b.isRed() && nowNode.getParent().isRed() 
					&& (b.getLeftChild()==null || !b.getLeftChild().isRed())
					&& (b.getRightChild()==null || !b.getRightChild().isRed())) {
				b.setRed(true);
				nowNode.getParent().setRed(false);
			}
//			7：当前节点是黑且兄弟节点为黑色，兄弟节点的左子是红色，右子是黑色，而且当
//			前节点是父节点的左子节点，那么：把兄弟节点变红，兄弟左子节点变黑，然后
//			对兄弟节点进行右旋，再重新开始判断
			else if (!b.isRed() && nowNode == nowNode.getParent().getLeftChild()
					&& (b.getLeftChild()==null || b.getLeftChild().isRed())
					&& (b.getRightChild()==null || !b.getRightChild().isRed())) {
				b.setRed(true);
				b.getLeftChild().setRed(false);
				this.rightRotate(b);
				this.afterDel(nowNode);
			}
//			8：当前节点是黑且兄弟节点为黑色，兄弟节点的左子是黑色，右子是红色，而且当
//			前节点是父节点的右子节点，那么：把兄弟节点变红，兄弟右子节点变黑，然后
//			对兄弟节点左旋，再重新开始判断
			else if (!b.isRed() && nowNode == nowNode.getParent().getRightChild()
					&& (b.getRightChild()==null || b.getRightChild().isRed())
					&& (b.getLeftChild()==null || !b.getLeftChild().isRed())) {
				b.setRed(true);
				b.getRightChild().setRed(false);
				this.leftRotate(b);
				this.afterDel(nowNode);
			}
//			9：当前节点是黑且兄弟节点为黑色，兄弟节点的右子是红色，左子的颜色任意，而
//			且当前节点是父节点的左子节点，那么：把兄弟节点变成当前节点父节点的颜
//			色，把当前节点父节点变黑，兄弟节点右子变黑，然后以当前节点的父节点为支
//			点进行左旋，结束。
			else if (!b.isRed() && nowNode == nowNode.getParent().getLeftChild()
					&& (b.getRightChild()==null || b.getRightChild().isRed())) {
				b.setRed(nowNode.getParent().isRed());
				nowNode.getParent().setRed(false);
				b.getRightChild().setRed(false);
				this.leftRotate(nowNode.getParent());
			}
//			10：当前节点是黑且兄弟节点为黑色，兄弟节点的左子是红色，右子的颜色任意，
//			而且当前节点是父节点的右子节点，那么：把兄弟节点变成当前节点父节点的颜
//			色，把当前节点父节点变黑，兄弟节点左子变黑，然后以当前节点的父节点为支
//			点进行右旋，结束。
			else if (!b.isRed() && nowNode == nowNode.getParent().getRightChild()
					&& (b.getLeftChild()==null || b.getLeftChild().isRed())) {
				b.setRed(nowNode.getParent().isRed());
				nowNode.getParent().setRed(false);
				b.getLeftChild().setRed(false);
				this.rightRotate(nowNode.getParent());
			}
			
		}

}

/**
	 * 删除时，用来查找需要删除的节点
	 * @param node
	 * @param key
	 * @return
	 */
	private RBNode findOneNode(RBNode node,int key) {
		if (node != null) {
			if (node.getId() == key) {
				return node;
			}
			RBNode tempNode = findOneNode(node.getLeftChild(), key);
			if (tempNode!=null) {
				if (tempNode == tempNode.getParent().getLeftChild()) {
					this.isLeftNode = true;
				}else {
					this.isLeftNode = false;
				}
				return tempNode;
			}
			tempNode = findOneNode(node.getRightChild(), key);
			if (tempNode!=null) {
				if (tempNode == tempNode.getParent().getLeftChild()) {
					this.isLeftNode = true;
				}else {
					this.isLeftNode = false;
				}
				return tempNode;
			}
		}
		return null;
	}

/**
	 * 找到要删除节点的中序后继节点
	 * 
	 * @param current
	 * @return
	 */
	private RBNode getSuccessor(RBNode delNode) {
		RBNode successor = delNode;
		RBNode successorParent = delNode;
		RBNode current = delNode.getRightChild();
		while (current != null) {
			successorParent = successor;
			successor = current;
			//id=-1
			if (current.getLeftChild()!=null && current.getLeftChild().getId()>0) {
				current = current.getLeftChild();
			}else {
				current = null;
			}
			
		}
//		if (successor != delNode.getLeftChild()) {
//			successorParent.setLeftChild(successor.getRightChild());
//			
//			if (successor.getRightChild()!=null) {
//				successor.getRightChild().setParent(successorParent);
//			}
//			
//			successor.setRightChild(delNode.getRightChild());
//			
//			delNode.getRightChild().setParent(successor);
//		}
		return successor;
	}

private void oneRightNode(RBNode parent, RBNode current, boolean isLeftNode) {
		if (current == root) {
			root = current.getRightChild();
			
			current.getRightChild().setParent(null);
		} else {
			if (isLeftNode) {
				parent.setLeftChild(current.getRightChild());
			} else {
				parent.setRightChild(current.getRightChild());
			}
			current.getRightChild().setParent(parent);
		}
	}

private void oneLeftNode(RBNode parent, RBNode current, boolean isLeftNode) {
		if (current == root) {
			root = current.getLeftChild();
			
			current.getLeftChild().setParent(null);
		} else {
			if (isLeftNode) {
				parent.setLeftChild(current.getLeftChild());
			} else {
				parent.setRightChild(current.getLeftChild());
			}
			
			current.getLeftChild().setParent(parent);
		}
	}

private void noChild(RBNode parent, RBNode current, boolean isLeftNode) {
		if (current == root) {
			root = null;
		} else {
			if (isLeftNode) {
				parent.setLeftChild(null);
			} else {
				parent.setRightChild(null);
			}
		}
	}

public static void main(String[] args) {
		RBTree tree = new RBTree();
		tree.insert(6, 212);
		tree.insert(5, 211);
		tree.insert(8, 221);
		tree.insert(3, 321);
		tree.insert(7, 421);
		tree.insert(9, 521);

//		System.out.println(tree.root.toString());
//
//		tree.inOrder(tree.find(6));
//
//		System.out.println(tree.getMinNode());
//		System.out.println(tree.getMaxNode());
		
		tree.delete(6);
		
		tree.preOrder(tree.root);
	}
}
</pre> 红黑树有二叉搜索树基础而来，复杂度要比二叉搜索树大很多，但是应用却很大jdk1.8后的hashmap就加入了红黑树这个数据结构，大家看源码就知道。