当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

红黑树

发表于: 2014-07-24   作者:不懂事的小屁孩   来源:转载   浏览:
摘要: 红黑树 红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。它是在1972年由鲁道夫·贝尔发明的,他称之为"对称二叉B树",它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的: 它
红黑树

红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。它是在1972年由鲁道夫·贝尔发明的,他称之为"对称二叉B树",它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n是树中元素的数目。

性质:
红黑树是每个节点都带有颜色属性的二叉查找树,颜色为红色或黑色。在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求:

性质1. 节点是红色或黑色。

性质2. 根是黑色。

性质3. 所有叶子都是黑色(叶子是NIL节点)。

性质4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)

性质5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。


红黑树是一种经典的数据结构,在linux内存管理、nginx 等很多地方用到它。主要操作包括插入、删除,其中插入6种情况,删除8种情况,详细的思路就不说了,如果不太明白的请参考算法导论13章,看的时候一定要把每一种插入、删除的情况在纸上自己画出来,这样会节省你很多时间。下面是java实现的代码:





public class RBTree {

	private final Node NIL = new Node(null,null,null,Color.BLACK,-1);
	private Node root;

	public RBTree() {
		root = NIL;
	}

	public RBTree(Node  root) {
		this.root = root;
	}

	//插入节点
	public void rbInsert(Node node) {

		Node previous = NIL;
		Node temp = root;

		while (temp != NIL) {
			previous = temp;
			if (temp.getValue() < node.getValue()) {
				temp = temp.getRight();
			} else {
				temp = temp.getLeft();
			}
		}
		node.setParent(previous);

		if (previous == NIL) {
			root = node;
			root.setParent(NIL);
		} else  if (previous.getValue() > node.getValue()) {
			previous.setLeft(node);
		} else {
			previous.setRight(node);
		}

		node.setLeft(NIL);
		node.setRight(NIL);
		node.setColor(Color.RED);
		rb_Insert_Fixup(node);

	}

	//插入节点后的调整
	private void rb_Insert_Fixup(Node node) {

		while (node.getParent().getColor() == Color.RED) {

			if (node.getParent() == node.getParent().getParent().getLeft()) {

				Node rightNuncle = node.getParent().getParent().getRight();

				if (rightNuncle.getColor() == Color.RED) {         //Case 1

					rightNuncle.setColor(Color.BLACK);
					node.getParent().setColor(Color.BLACK);
					node.getParent().getParent().setColor(Color.RED);
					node = node.getParent().getParent();

				} else if (node == node.getParent().getRight()) {  //case 2

					node = node.getParent();
					leftRotate(node);

				} else {                                          //case 3

					node.getParent().setColor(Color.BLACK);
					node.getParent().getParent().setColor(Color.RED);

					rightRotate(node.getParent().getParent());

				}

			} else {

				Node leftNuncle = node.getParent().getParent().getLeft();

				if (leftNuncle.getColor() == Color.RED) {     //case 4

					leftNuncle.setColor(Color.BLACK);
					node.getParent().setColor(Color.BLACK);
					node.getParent().getParent().setColor(Color.RED);
					node = node.getParent().getParent();

				} else if (node == node.getParent().getLeft()) { //case 5

					node = node.getParent();
					rightRotate(node);

				} else {                                          // case 6

					node.getParent().setColor(Color.BLACK);
					node.getParent().getParent().setColor(Color.RED);
					leftRotate(node.getParent().getParent());

				}

			}


		}

		root.setColor(Color.BLACK);

	}


	//删除节点
	public Node rbDelete(int data) {

		Node node = search(data);
		Node temp = NIL;
		Node child = NIL;
		if (node == null) {
			return null;
		} else {
			if (node.getLeft() == NIL || node.getRight() == NIL) {
				temp = node;
			} else {
				temp = successor(node);
			}

			if (temp.getLeft() != NIL) {
				child = temp.getLeft();
			} else {
				child = temp.getRight();
			}

			child.setParent(temp.getParent());

			if (temp.getParent() == NIL) {
				root = child;
			} else if (temp == temp.getParent().getLeft()) {
				temp.getParent().setLeft(child);
			} else {
				temp.getParent().setRight(child);
			}

			if (temp != node) {
				node.setValue(temp.getValue());
			}

			if (temp.getColor() == Color.BLACK) {
				rb_Delete_Fixup(child);
			}
			return temp;
		}




	}

	//删除节点后的调整
	private void rb_Delete_Fixup(Node node) {

		while (node != root && node.getColor() == Color.BLACK) {

			if (node == node.getParent().getLeft()) {

				Node rightBrother = node.getParent().getRight();
				if (rightBrother.getColor() == Color.RED) {          //case 1 node节点为左孩子,node节点的兄弟为RED
					rightBrother.setColor(Color.BLACK);
					node.getParent().setColor(Color.RED);
					leftRotate(node.getParent());
					rightBrother = node.getParent().getRight();
				}

				if (rightBrother.getLeft().getColor() == Color.BLACK && rightBrother.getRight().getColor() == Color.BLACK) {
					rightBrother.setColor(Color.RED);
					node = node.getParent();
				} else if (rightBrother.getRight().getColor() == Color.BLACK) {
					rightBrother.getLeft().setColor(Color.BLACK);
					rightBrother.setColor(Color.RED);
					rightRotate(rightBrother);
					rightBrother = node.getParent().getRight();
				} else {
					rightBrother.setColor(node.getParent().getColor());
					node.getParent().setColor(Color.BLACK);
					rightBrother.getRight().setColor(Color.BLACK);
					leftRotate(node.getParent());
					node = root;
				}


			} else {

				Node leftBrother = node.getParent().getLeft();
				if (leftBrother.getColor() == Color.RED) {
					leftBrother.setColor(Color.BLACK);
					node.getParent().setColor(Color.RED);
					rightRotate(node.getParent());
					leftBrother = node.getParent().getLeft();
				}

				if (leftBrother.getLeft().getColor() == Color.BLACK && leftBrother.getRight().getColor() == Color.BLACK) {
					leftBrother.setColor(Color.RED);
					node = node.getParent();

				} else if (leftBrother.getLeft().getColor() == Color.BLACK) {

					leftBrother.setColor(Color.RED);
					leftBrother.getRight().setColor(Color.BLACK);
					leftRotate(leftBrother);
					leftBrother = node.getParent().getLeft();

				} else {

					leftBrother.setColor(node.getParent().getColor());
					node.getParent().setColor(Color.BLACK);
					leftBrother.getLeft().setColor(Color.BLACK);
					rightRotate(node.getParent());
					node = root;

				}

			}

		}

		node.setColor(Color.BLACK);
	}


	//查找节点node的后继节点

	public Node successor(Node node) {

		Node rightChild = node.getRight();
		if  (rightChild != NIL) {
			Node previous = null;
			while (rightChild != NIL) {
				previous = rightChild;
				rightChild = rightChild.getLeft();
			}
			return previous;
		} else {

			Node parent = node.getParent();
			while (parent != NIL && node != parent.getLeft()) {
				node = parent;
				parent = parent.getParent();
			}

			return parent;

		}

	}


	//查找节点
	public Node search(int data) {
		Node temp = root;

		while (temp != NIL) {
			if (temp.getValue() == data) {
				return temp;
			} else  if (data < temp.getValue()) {
				temp = temp.getLeft();
			} else {
				temp = temp.getRight();
			}
		}
		return null;
	}




	//左转函数
	private void leftRotate(Node node) {

		Node rightNode = node.getRight();

		node.setRight(rightNode.getLeft());
		if (rightNode.getLeft() != NIL) {
			rightNode.getLeft().setParent(node);
		}
		rightNode.setParent(node.getParent());

		if (node.getParent() == NIL) {
			rightNode = root;
		} else if (node == node.getParent().getLeft()) {
			node.getParent().setLeft(rightNode);
		} else {
			node.getParent().setRight(rightNode);
		}

		rightNode.setLeft(node);
		node.setParent(rightNode);


	}

	//右转函数
	private void rightRotate(Node node) {

		Node leftNode = node.getLeft();
		node.setLeft(leftNode.getRight());

		if (leftNode.getRight() != null) {
			leftNode.getRight().setParent(node);
		}

		leftNode.setParent(node.getParent());

		if (node.getParent() == NIL) {
			root = leftNode;
		} else if (node == node.getParent().getLeft()) {
			node.getParent().setLeft(leftNode);
		} else {
			node.getParent().setRight(leftNode);
		}

		leftNode.setRight(node);
		node.setParent(leftNode);

	}

	//中序遍历红黑树
	public void printTree() {
		inOrderTraverse(root);
	}

	private void inOrderTraverse(Node node) {

		if (node != NIL) {
			inOrderTraverse(node.getLeft());
			System.out.print(" 节点:"+node.getValue());
			System.out.print("  左节点"+node.getLeft().getValue());
			System.out.print("  右节点"+node.getRight().getValue());
			System.out.print("    的颜色为:" + node.getColor());
			System.out.println();
			inOrderTraverse(node.getRight());
		}

	}


	public Node getNIL() {
		return NIL;
	}

}



class Node {
	private Node left;
	private Node right;
	private Node parent;
	private Color color;
	private int value;
	public Node(Node left, Node right, Node parent, Color color, int value) {
		super();
		this.left = left;
		this.right = right;
		this.parent = parent;
		this.color = color;
		this.value = value;
	}

	public Node() {
	}

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

	public Node getLeft() {
		return left;
	}

	public void setLeft(Node left) {
		this.left = left;
	}

	public Node getRight() {
		return right;
	}

	public void setRight(Node right) {
		this.right = right;
	}

	public Node getParent() {
		return parent;
	}

	public void setParent(Node parent) {
		this.parent = parent;
	}

	public Color getColor() {
		return color;
	}

	public void setColor(Color color) {
		this.color = color;
	}

	public int getValue() {
		return value;
	}

	public void setValue(int value) {
		this.value = value;
	}

}

enum Color {
	RED,BLACK
}




public class RBTreeTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		RBTree rbTree = new RBTree();
		
		rbTree.rbInsert(new Node(41));
		rbTree.rbInsert(new Node(38));
		rbTree.rbInsert(new Node(31));
		rbTree.rbInsert(new Node(12));
		rbTree.rbInsert(new Node(19));
		rbTree.rbInsert(new Node(8));
		
		//rbTree.printTree();
		
		
		rbTree.rbDelete(19);
		
		rbTree.printTree();
		

	}

}

红黑树

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
背景知识   通过上一篇文章的介绍,我们了解到,对二叉查找树的插入和删除会影响树整体的"平衡"性.
在算法导论中介绍的红黑树,引入了"内部节点","外部节点"的概念; 内部节点;含有有效键值的节点. 外部
红黑树是内核里面最常用的数据结构,红黑树本身也是一个非常复杂的数据结构。我自己为了详细的理解
红黑树是AVL树的变种,具体定义如下:红黑树也是一棵二叉查找树,要满足一下性质 (1)每个节点或者
转载http://hxraid.iteye.com/blog/611816 红黑树的性质与定义 红黑树(red-black tree) 是一棵满足
这篇文章http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html讲红黑树讲得非常好,直
LLRB——红黑树的现代实现 一、本文内容 以一种简明易懂的方式介绍红黑树背后的逻辑实现2-3-4树,以
红黑树 一.红黑树的背景: 1.红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,
一、定义 红黑树是一种特殊的二叉查找树,它的每一个结点都被标记为红色或者黑色。是在计算机科学中
之前看了很多写红黑树的博客,但是感觉都讲的不太清楚!没说这样操作如何使他保持平衡的,于是疑惑
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号