教你透彻了解红黑树

 

 

二叉搜索树实现：

import java.util.Objects;

public class SimpleBinarySearchTree {
	
	private BSTreeNode root;
	
	public SimpleBinarySearchTree()
	{
		this.root = null;
	}

	public BSTreeNode getRoot() {
		return root;
	}

	public void insert(SimpleBinarySearchTree T, BSTreeNode x)
	{
		
	}
	
	public void leftRotate(SimpleBinarySearchTree T, BSTreeNode x)
	{
		// set y
		BSTreeNode y = x.right;
		// Turn y's left subtree into x's right subtree
		x.right = y.left;
		y.left.parent = x;
		// Link x's parent to y
		y.parent = x.parent;
		if (x.parent == null)
		{
			root = y;
		}
		else if (x == x.parent.left)
		{
			x.parent.left = y;
		}
		else
		{
			x.parent.right = y;
		}
		// Put x on y's left
		y.left = x;
		x.parent = y;
	}

	static final class BSTreeNode
	{
		private BSTreeNode left;
		private BSTreeNode right;
		private BSTreeNode parent;
		private int value;
		
		public BSTreeNode(BSTreeNode left, BSTreeNode right, BSTreeNode parent, int value)
		{
			this.left = left;
			this.right = right;
			this.parent = parent;
			this.value = value;
		}

		public int getValue() {
			return value;
		}

		public void setValue(int value) {
			this.value = value;
		}
		
		@Override
		public int hashCode()
		{
			return Objects.hashCode(value);
		}
		
		@Override
		public boolean equals(Object o)
		{
			if (o == this)
			{
				return true;
			}
			
			if (o == null)
			{
				return false;
			}
			if (!(o instanceof BSTreeNode))
			{
				return false;
			}
			
			return ((BSTreeNode)o).value == value;
		}
	}
	
	public static void main(String[] args) {
		SimpleBinarySearchTree bsTree = new SimpleBinarySearchTree();
	}
}

 

 红黑树实现：

package com.linus.test;

import java.util.Objects;
import java.util.Random;

public class SimpleRedBlackTree {

	/* ------------------------------------------------------------ */
	// Tree bins

	/**
	 * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn extends
	 * Node) so can be used as extension of either regular or linked node.
	 */
	static final class SimpleRBTreeNode {
		int value;
		SimpleRBTreeNode parent; // red-black tree links
		SimpleRBTreeNode left;
		SimpleRBTreeNode right;
		boolean red;

		public SimpleRBTreeNode(SimpleRBTreeNode left, SimpleRBTreeNode right,
				SimpleRBTreeNode parent, int value) {
			this.value = value;
			this.left = left;
			this.right = right;
			this.parent = parent;
		}

		public SimpleRBTreeNode(int value) {
			this(null, null, null, value);
		}

		public final int getValue() {
			return value;
		}

		public final String toString() {
			return "value = " + value;
		}

		public final int hashCode() {
			return Objects.hashCode(value);
		}

		public final int setValue(int newValue) {
			int oldValue = value;
			value = newValue;
			return oldValue;
		}

		public final boolean equals(Object o) {
			if (o == this)
				return true;
			if (o instanceof SimpleRBTreeNode) {
				SimpleRBTreeNode e = (SimpleRBTreeNode) o;
				if (value == e.getValue())
					return true;
			}
			return false;
		}

		/**
		 * Returns root of tree containing this node.
		 */
		final SimpleRBTreeNode root() {
			for (SimpleRBTreeNode r = this, p;;) {
				if ((p = r.parent) == null)
					return r;
				r = p;
			}
		}

		public void clear() {
			SimpleRBTreeNode root = this;
			SimpleRBTreeNode left = root.left;
			SimpleRBTreeNode right = root.right;
			if (null != left) {
				left.clear();
			}
			if (null != right) {
				right.clear();
			}
			root.left = null;
			root.right = null;
			root.parent = null;
		}

		/**
		 * Finds the node starting at root p with the given value.
		 */
		final SimpleRBTreeNode find(int value) {
			SimpleRBTreeNode p = this;
			SimpleRBTreeNode pl = p.left, pr = p.right;
			if (p.value == value) {
				return p;
			} else if ((p.value > value) && (null != pl)) {
				return pl.find(value);
			} else if (null != pr) {
				return pr.find(value);
			} else {
				return null;
			}
		}

		/**
		 * Calls find for root node.
		 */
		final SimpleRBTreeNode getTreeNode(int value) {
			return ((parent != null) ? root() : this).find(value);
		}

		/* ------------------------------------------------------------ */
		// Red-black tree methods, all adapted from CLR

		static SimpleRBTreeNode rotateLeft(SimpleRBTreeNode root,
				SimpleRBTreeNode p) {
			SimpleRBTreeNode r, pp, rl;
			if (p != null && (r = p.right) != null) {
				if ((rl = p.right = r.left) != null)
					rl.parent = p;
				if ((pp = r.parent = p.parent) == null)
					(root = r).red = false;
				else if (pp.left == p)
					pp.left = r;
				else
					pp.right = r;
				r.left = p;
				p.parent = r;
			}
			return root;
		}

		static SimpleRBTreeNode rotateRight(SimpleRBTreeNode root,
				SimpleRBTreeNode p) {
			SimpleRBTreeNode l, pp, lr;
			if (p != null && (l = p.left) != null) {
				if ((lr = p.left = l.right) != null)
					lr.parent = p;
				if ((pp = l.parent = p.parent) == null)
					(root = l).red = false;
				else if (pp.right == p)
					pp.right = l;
				else
					pp.left = l;
				l.right = p;
				p.parent = l;
			}
			return root;
		}

		static SimpleRBTreeNode balanceInsertion(SimpleRBTreeNode root,
				SimpleRBTreeNode x) {
			x.red = true;
			for (SimpleRBTreeNode xp, xpp, xppl, xppr;;) {
				if ((xp = x.parent) == null) {
					x.red = false;
					return x;
				} else if (!xp.red || (xpp = xp.parent) == null)
					return root;
				if (xp == (xppl = xpp.left)) {
					if ((xppr = xpp.right) != null && xppr.red) {
						xppr.red = false;
						xp.red = false;
						xpp.red = true;
						x = xpp;
					} else {
						if (x == xp.right) {
							root = rotateLeft(root, x = xp);
							xpp = (xp = x.parent) == null ? null : xp.parent;
						}
						if (xp != null) {
							xp.red = false;
							if (xpp != null) {
								xpp.red = true;
								root = rotateRight(root, xpp);
							}
						}
					}
				} else {
					if (xppl != null && xppl.red) {
						xppl.red = false;
						xp.red = false;
						xpp.red = true;
						x = xpp;
					} else {
						if (x == xp.left) {
							root = rotateRight(root, x = xp);
							xpp = (xp = x.parent) == null ? null : xp.parent;
						}
						if (xp != null) {
							xp.red = false;
							if (xpp != null) {
								xpp.red = true;
								root = rotateLeft(root, xpp);
							}
						}
					}
				}
			}
		}

		static SimpleRBTreeNode balanceDeletion(SimpleRBTreeNode root,
				SimpleRBTreeNode x) {
			for (SimpleRBTreeNode xp, xpl, xpr;;) {
				if (x == null || x == root)
					return root;
				else if ((xp = x.parent) == null) {
					x.red = false;
					return x;
				} else if (x.red) {
					x.red = false;
					return root;
				} else if ((xpl = xp.left) == x) {
					if ((xpr = xp.right) != null && xpr.red) {
						xpr.red = false;
						xp.red = true;
						root = rotateLeft(root, xp);
						xpr = (xp = x.parent) == null ? null : xp.right;
					}
					if (xpr == null)
						x = xp;
					else {
						SimpleRBTreeNode sl = xpr.left, sr = xpr.right;
						if ((sr == null || !sr.red) && (sl == null || !sl.red)) {
							xpr.red = true;
							x = xp;
						} else {
							if (sr == null || !sr.red) {
								if (sl != null)
									sl.red = false;
								xpr.red = true;
								root = rotateRight(root, xpr);
								xpr = (xp = x.parent) == null ? null : xp.right;
							}
							if (xpr != null) {
								xpr.red = (xp == null) ? false : xp.red;
								if ((sr = xpr.right) != null)
									sr.red = false;
							}
							if (xp != null) {
								xp.red = false;
								root = rotateLeft(root, xp);
							}
							x = root;
						}
					}
				} else { // symmetric
					if (xpl != null && xpl.red) {
						xpl.red = false;
						xp.red = true;
						root = rotateRight(root, xp);
						xpl = (xp = x.parent) == null ? null : xp.left;
					}
					if (xpl == null)
						x = xp;
					else {
						SimpleRBTreeNode sl = xpl.left, sr = xpl.right;
						if ((sl == null || !sl.red) && (sr == null || !sr.red)) {
							xpl.red = true;
							x = xp;
						} else {
							if (sl == null || !sl.red) {
								if (sr != null)
									sr.red = false;
								xpl.red = true;
								root = rotateLeft(root, xpl);
								xpl = (xp = x.parent) == null ? null : xp.left;
							}
							if (xpl != null) {
								xpl.red = (xp == null) ? false : xp.red;
								if ((sl = xpl.left) != null)
									sl.red = false;
							}
							if (xp != null) {
								xp.red = false;
								root = rotateRight(root, xp);
							}
							x = root;
						}
					}
				}
			}
		}

		/**
		 * Recursive invariant check
		 */
		static boolean checkInvariants(SimpleRBTreeNode t) {
			SimpleRBTreeNode tp = t.parent, tl = t.left, tr = t.right;
			if (tp != null && t != tp.left && t != tp.right)
				return false;
			if (t.red && tl != null && tl.red && tr != null && tr.red)
				return false;
			if (tl != null && !checkInvariants(tl))
				return false;
			if (tr != null && !checkInvariants(tr))
				return false;
			return true;
		}
	}

	private SimpleRBTreeNode root;

	public void insert(int value) {
		SimpleRBTreeNode y = null;
		SimpleRBTreeNode parent = this.getRoot();

		while (parent != null) {
			y = parent;
			if (value < parent.getValue()) {
				parent = parent.left;
			} else if (value > parent.getValue()) {
				parent = parent.right;
			} else {
				System.out.println("Duplicate value: " + value);
				return;
			}
		}

		SimpleRBTreeNode node = new SimpleRBTreeNode(null, null, null, value);
		node.parent = y;
		if (y == null) {
			// Tree T is empty
			this.setRoot(node);
		} else if (node.getValue() < y.getValue()) {
			y.left = node;
		} else {
			y.right = node;
		}
		node.left = null;
		node.right = null;
		node.red = true;
		SimpleRBTreeNode.balanceInsertion(getRoot(), node);
	}

	public SimpleRBTreeNode delete(int value) {
		return SimpleRBTreeNode.balanceDeletion(root, new SimpleRBTreeNode(
				value));
	}

	public SimpleRBTreeNode getRoot() {
		return root;
	}

	public void setRoot(SimpleRBTreeNode root) {
		this.root = root;
	}

	public static void printTreeValue(SimpleRBTreeNode root) {
		if (null != root.left) {
			printTreeValue(root.left);
		}
		System.out.println("Value = " + root.value);
		if (null != root.right) {
			printTreeValue(root.right);
		}
	}

	public static void main(String[] args) {
		System.out.println("Test case 1");
		SimpleRedBlackTree tree = new SimpleRedBlackTree();
		Random rand = new Random(System.currentTimeMillis());
		int value;
		for (int i = 0; i < 5; i++) {
			value = rand.nextInt(100);
			System.out.println("Insert value: " + value);
			tree.insert(value);
		}
		SimpleRedBlackTree.printTreeValue(tree.getRoot());
		tree.getRoot().clear();

		System.out.println("Test case 2");
		SimpleRedBlackTree.printTreeValue(tree.getRoot());
		for (int i = 0; i < 5; i++) {
			tree.insert(i);
		}
		SimpleRedBlackTree.printTreeValue(tree.getRoot());
	}
}

 

 

网站地址：https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md