ordinary
- 浏览: 77310 次
- 性别:
- 来自: 北京
-
文章分类
最新评论
自己写的红黑树，先保存下来，有时间写具体细节。
节点类：
package com.star;
public class RedBlack {
private RedBlack parent;
private RedBlack left;
private RedBlack right;
private RedBlackEnum redOrBlack;
private Integer value;
public Integer getValue() {
return value;
}
public void setValue(Integer value) {
this.value = value;
}
public RedBlack getParent() {
return parent;
}
public void setParent(RedBlack parent) {
this.parent = parent;
}
public RedBlack getLeft() {
return left;
}
public void setLeft(RedBlack left) {
this.left = left;
}
public RedBlack getRight() {
return right;
}
public void setRight(RedBlack right) {
this.right = right;
}
public RedBlackEnum getRedOrBlack() {
return redOrBlack;
}
public void setRedOrBlack(RedBlackEnum redOrBlack) {
this.redOrBlack = redOrBlack;
}
}
红黑枚举：
package com.star;
public enum RedBlackEnum {
red,
black;
}
红黑树：
package com.star;
import java.util.Scanner;
/**
* 红黑树性质如下： 性质1. 节点是红色或黑色。 性质2. 根是黑色。 性质3. 所有叶子都是黑色（叶子是NIL节点）。 性质4.
* 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点) 性质5.
* 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
*
* @author Administrator
*
* @param <v>
*/
public class RedBlackTree {
private RedBlack root;
public RedBlackTree() {
}
public RedBlack getRoot() {
return root;
}
public void setRoot(RedBlack root) {
this.root = root;
}
public void insert(int value) {
RedBlack redBlack = insertTree(value);
adjustInsert(redBlack);
}
private RedBlack insertTree(int value) {
RedBlack redBlack = new RedBlack();
redBlack.setValue(value);
redBlack.setRedOrBlack(RedBlackEnum.red);
RedBlack redBlackIndex = root;
while (redBlackIndex != null && redBlackIndex.getValue() != null) {
if (redBlackIndex.getValue().compareTo(redBlack.getValue()) > 0) {
if (redBlackIndex.getLeft() == null) {
redBlackIndex.setLeft(redBlack);
redBlack.setParent(redBlackIndex);
break;
}
redBlackIndex = redBlackIndex.getLeft();
} else {
if (redBlackIndex.getRight() == null) {
redBlackIndex.setRight(redBlack);
redBlack.setParent(redBlackIndex);
break;
}
redBlackIndex = redBlackIndex.getRight();
}
}
return redBlack;
}
private RedBlack getGrandParent(RedBlack redBlack) {
if (redBlack != null && redBlack.getParent() != null) {
return redBlack.getParent().getParent();
}
return null;
}
private RedBlack getUncle(RedBlack redBlack) {
if (redBlack != null) {
if (redBlack.getParent().equals(getGrandParent(redBlack).getLeft())) {
return getGrandParent(redBlack).getRight();
} else {
return getGrandParent(redBlack).getLeft();
}
}
return null;
}
/**
* 情形1:
* 新节点N位于树的根上，没有父节点。在这种情形下，我们把它重绘为黑色以满足性质2[5]。因为它在每个路径上对黑节点数目增加一，性质5[4]符合。
*
* @param redBlack
*/
private void adjustInsert(RedBlack redBlack) {
if (redBlack != null) {
if (redBlack.getParent() == null) {
redBlack.setRedOrBlack(RedBlackEnum.black);
root = redBlack;
} else {
adjustInsertParentBlack(redBlack);
}
}
}
/**
* 2 新节点的父节点P是黑色，所以性质4[3]没有失效（新节点是红色的）。在这种情形下，树仍是有效的。性质5[4]受到威胁，
* 因为新节点N有两个黑色叶子儿子
* ；但是由于新节点N是红色，通过它的每个子节点的路径就都有同通过它所取代的黑色的叶子的路径同样数目的黑色节点，所以这个性质依然满足。
*
* @param redBlack
*/
private void adjustInsertParentBlack(RedBlack redBlack) {
if (redBlack.getParent().getRedOrBlack() == RedBlackEnum.black) {
return;
} else {
adjustInsertParentAndUncleRed(redBlack);
}
}
/**
* 如果父节点P和叔父节点U二者都是红色，(此时新插入节点N做为P的左子节点或右子节点都属于情形3,这里右图仅显示N做为P左子的情形)
* 则我们可以将它们两个重绘为黑色并重绘祖父节点G为红色
* (用来保持性质5[4])。现在我们的新节点N有了一个黑色的父节点P。因为通过父节点P或叔父节点U的任何路径都必定通过祖父节点G
* ，在这些路径上的黑节点数目没有改变
* 。但是，红色的祖父节点G的父节点也有可能是红色的，这就违反了性质4[3]。为了解决这个问题，我们在祖父节点G上递归地进行情形1的整个过程
* 。（把G当成是新加入的节点进行各种情况的检查）
*
* @param redBlack
*/
private void adjustInsertParentAndUncleRed(RedBlack redBlack) {
if (getUncle(redBlack) != null
&& getUncle(redBlack).getRedOrBlack() == RedBlackEnum.red) {
redBlack.getParent().setRedOrBlack(RedBlackEnum.black);
getUncle(redBlack).setRedOrBlack(RedBlackEnum.black);
getGrandParent(redBlack).setRedOrBlack(RedBlackEnum.red);
adjustInsert(getGrandParent(redBlack));
} else {
adjustInsertParentRedAndUncleBlack(redBlack);
}
}
/**
* 父节点P是红色而叔父节点U是黑色或缺少;
* 还有，新节点N是其父节点P的右子节点，而父节点P又是其父节点的左子节点。在这种情形下，我们进行一次左旋转调换新节点和其父节点的角色;
* 接着，我们按情形5处理以前的父节点P
* 。这导致某些路径通过它们以前不通过的新节点N或父节点P中的一个，但是这两个节点都是红色的，所以性质5[4]没有失效。
*
* @param redBlack
*/
private void adjustInsertParentRedAndUncleBlack(RedBlack redBlack) {
if (redBlack == redBlack.getParent().getRight()
&& redBlack.getParent() == getGrandParent(redBlack).getLeft()) {
leftRotate(redBlack.getParent());
redBlack = redBlack.getLeft();
} else if (redBlack == redBlack.getParent().getLeft()
&& redBlack.getParent() == getGrandParent(redBlack).getRight()) {
rightRotate(redBlack.getParent());
redBlack = redBlack.getRight();
}
adjustInsertParentRedAndUncleBlackOther(redBlack);
}
/**
* 父节点P是红色而叔父节点U 是黑色或缺少，新节点N 是其父节点的左子节点，而父节点P又是其父节点G的左子节点。在这种情形下，我们进行针对祖父节点G
* 的一次右旋转; 在旋转产生的树中，以前的父节点P现在是新节点N和以前的祖父节点G
* 的父节点。我们知道以前的祖父节点G是黑色，否则父节点P就不可能是红色 (如果 P 和 G 都是紅色就違反了性質4，所以 G
* 必須是黑色)。我们切换以前的父节点P和祖父节点G的颜色
* ，结果的树满足性质4[3]。性质5[4]也仍然保持满足，因为通过这三个节点中任何一个的所有路径以前都通过祖父节点G
* ，现在它们都通过以前的父节点P。在各自的情形下，这都是三个节点中唯一的黑色节点。
*
* @param redBlack
*/
private void adjustInsertParentRedAndUncleBlackOther(RedBlack redBlack) {
redBlack.getParent().setRedOrBlack(RedBlackEnum.black);
getGrandParent(redBlack).setRedOrBlack(RedBlackEnum.red);
if (redBlack == redBlack.getParent().getLeft()
&& redBlack.getParent() == getGrandParent(redBlack).getLeft()) {
rightRotate(getGrandParent(redBlack));
} else {
/* Here, n == n->parent->right && n->parent == grandparent(n)->right */
leftRotate(getGrandParent(redBlack));
}
}
private RedBlack getSibling(RedBlack redBlack) {
if (redBlack == redBlack.getParent().getLeft()) {
return redBlack.getParent().getRight();
} else {
return redBlack.getParent().getLeft();
}
}
private RedBlack find(int value) {
return find(root, value);
}
private RedBlack find(RedBlack parentRedBlack, int value) {
if (parentRedBlack == null) {
return null;
}
if (parentRedBlack.getValue() > value) {
return find(parentRedBlack.getLeft(), value);
} else if (parentRedBlack.getValue() < value) {
return find(parentRedBlack.getRight(), value);
} else {
return parentRedBlack;
}
}
private boolean isLeaf(RedBlack redBlack) {
if (redBlack == null) {
return true;
} else {
return false;
}
}
private void replace(RedBlack redBlack, RedBlack newRedBlack) {
newRedBlack.setLeft(redBlack.getLeft());
newRedBlack.setRight(redBlack.getRight());
newRedBlack.setParent(redBlack.getParent());
}
public void delete(int value) {
RedBlack redBlack = find(value);
RedBlack childRedBlack = isLeaf(redBlack.getRight()) ? redBlack
.getLeft() : redBlack.getRight();
replace(redBlack, childRedBlack);
if (redBlack.getRedOrBlack() == RedBlackEnum.black) {
if (childRedBlack.getRedOrBlack() == RedBlackEnum.red) {
childRedBlack.setRedOrBlack(RedBlackEnum.black);
} else {
delete_case1(childRedBlack);
}
}
redBlack = null;
}
/**
* 情况 1: N 是新的根。在这种情况下，我们就做完了。我们从所有路径去除了一个黑色节点，而新根是黑色的，所以属性都保持着。
*
* @param childRedBlack
*/
private void delete_case1(RedBlack redBlack) {
if (redBlack.getParent() != null) {
delete_case2(redBlack);
}
}
/**
* 情况 2: S 是红色。在这种情况下我们在N的父亲上做左旋转，把红色兄弟转换成N的祖父。我们接着对调 N
* 的父亲和祖父的颜色。尽管所有的路径仍然有相同数目的黑色节点，现在 N 有了一个黑色的兄弟和一个红色的父亲，所以我们可以接下去按
* 4、5或6情况来处理。(它的新兄弟是黑色因为它是红色S的一个儿子。)
*
* @param redBlack
*/
private void delete_case2(RedBlack redBlack) {
RedBlack sibling = getSibling(redBlack);
if (sibling.getRedOrBlack() == RedBlackEnum.red) {
redBlack.getParent().setRedOrBlack(RedBlackEnum.red);
sibling.setRedOrBlack(RedBlackEnum.black);
if (redBlack == redBlack.getParent().getLeft()) {
leftRotate(redBlack.getParent());
} else {
rightRotate(redBlack.getParent());
}
}
delete_case3(redBlack);
}
/**
* 情况 3: N 的父亲、S 和 S 的儿子都是黑色的。在这种情况下，我们简单的重绘 S 为红色。结果是通过S的所有路径，它们就是以前不通过 N
* 的那些路径，都少了一个黑色节点。因为删除 N 的初始的父亲使通过 N 的所有路径少了一个黑色节点，这使事情都平衡了起来。但是，通过 P
* 的所有路径现在比不通过 P 的路径少了一个黑色节点，所以仍然违反属性4。要修正这个问题，我们要从情况 1 开始，在 P 上做重新平衡处理。
*
* @param redBlack
*/
private void delete_case3(RedBlack redBlack) {
RedBlack sibling = getSibling(redBlack);
if (redBlack.getParent().getRedOrBlack() == RedBlackEnum.black
&& sibling.getRedOrBlack() == RedBlackEnum.black
&& sibling.getLeft().getRedOrBlack() == RedBlackEnum.black
&& sibling.getRight().getRedOrBlack() == RedBlackEnum.black) {
sibling.setRedOrBlack(RedBlackEnum.red);
delete_case1(redBlack.getParent());
} else {
delete_case4(redBlack);
}
}
/**
* S 和 S 的儿子都是黑色，但是 N 的父亲是红色。在这种情况下，我们简单的交换 N 的兄弟和父亲的颜色。这不影响不通过 N
* 的路径的黑色节点的数目，但是它在通过 N 的路径上对黑色节点数目增加了一，添补了在这些路径上删除的黑色节点。
*
* @param redBlack
*/
private void delete_case4(RedBlack redBlack) {
RedBlack sibling = getSibling(redBlack);
if (redBlack.getParent().getRedOrBlack() == RedBlackEnum.red
&& sibling.getRedOrBlack() == RedBlackEnum.black
&& sibling.getLeft().getRedOrBlack() == RedBlackEnum.black
&& sibling.getRight().getRedOrBlack() == RedBlackEnum.black) {
sibling.setRedOrBlack(RedBlackEnum.red);
redBlack.getParent().setRedOrBlack(RedBlackEnum.black);
} else {
delete_case5(redBlack);
}
}
/**
* 情况 5: S 是黑色，S 的左儿子是红色，S 的右儿子是黑色，而 N 是它父亲的左儿子。在这种情况下我们在 S 上做右旋转，这样 S
* 的左儿子成为 S 的父亲和 N 的新兄弟。我们接着交换 S 和它的新父亲的颜色。所有路径仍有同样数目的黑色节点，但是现在 N
* 有了一个右儿子是红色的黑色兄弟，所以我们进入了情况 6。N 和它的父亲都不受这个变换的影响。
*
* @param redBlack
*/
private void delete_case5(RedBlack redBlack) {
RedBlack sibling = getSibling(redBlack);
if (sibling.getRedOrBlack() == RedBlackEnum.black) {
if (redBlack == redBlack.getParent().getLeft()
&& sibling.getRight().getRedOrBlack() == RedBlackEnum.black
&& sibling.getLeft().getRedOrBlack() == RedBlackEnum.red) {
sibling.setRedOrBlack(RedBlackEnum.red);
sibling.getLeft().setRedOrBlack(RedBlackEnum.black);
rightRotate(sibling);
} else if (redBlack == redBlack.getParent().getRight()
&& sibling.getLeft().getRedOrBlack() == RedBlackEnum.black
&& sibling.getRight().getRedOrBlack() == RedBlackEnum.red) {
sibling.setRedOrBlack(RedBlackEnum.red);
sibling.getRight().setRedOrBlack(RedBlackEnum.black);
leftRotate(sibling);
}
}
detete_case6(redBlack);
}
/**
* 情况 6: S 是黑色，S 的右儿子是红色，而 N 是它父亲的左儿子。在这种情况下我们在 N 的父亲上做左旋转，这样 S 成为 N 的父亲和 S
* 的右儿子的父亲。我们接着交换 N 的父亲和 S 的颜色，并使 S 的右儿子为黑色。子树在它的根上的仍是同样的颜色，所以属性 3
* 没有被违反。但是，N 现在增加了一个黑色祖先: 要么 N 的父亲变成黑色，要么它是黑色而 S 被增加为一个黑色祖父。所以，通过 N
* 的路径都增加了一个黑色节点。 此时，如果一个路径不通过 N，则有两种可能性: 它通过 N 的新兄弟。那么它以前和现在都必定通过 S 和 N
* 的父亲，而它们只是交换了颜色。所以路径保持了同样数目的黑色节点。 它通过 N 的新叔父，S 的右儿子。那么它以前通过 S、S 的父亲和 S
* 的右儿子，但是现在只通过 S，它被假定为它以前的父亲的颜色，和 S 的右儿子，它被从红色改变为黑色。合成效果是这个路径通过了同样数目的黑色节点。
*
* @param redBlack
*/
private void detete_case6(RedBlack redBlack) {
RedBlack sibling = getSibling(redBlack);
sibling.setRedOrBlack(redBlack.getParent().getRedOrBlack());
redBlack.getParent().setRedOrBlack(RedBlackEnum.black);
if (redBlack == redBlack.getParent().getLeft()) {
sibling.getRight().setRedOrBlack(RedBlackEnum.black);
leftRotate(redBlack.getParent());
} else {
sibling.getLeft().setRedOrBlack(RedBlackEnum.black);
rightRotate(redBlack.getParent());
}
}
public void print() {
print(root);
}
private void print(RedBlack redBlack) {
if (redBlack.getLeft() != null) {
print(redBlack.getLeft());
}
System.out.print(redBlack.getValue() + " ");
if (redBlack.getRight() != null) {
print(redBlack.getRight());
}
}
private void leftRotate(RedBlack redBlack) {
if (redBlack != null) {
RedBlack right = redBlack.getRight();
if (right != null) {
redBlack.setRight(right.getLeft());
if (right.getLeft() != null) {
right.getLeft().setParent(redBlack);
}
right.setLeft(redBlack);
right.setParent(redBlack.getParent());
if (right.getParent() == null) {
root = right;
}
redBlack.setParent(right);
if (right.getParent() != null) {
if (right.getParent().getLeft().getValue().equals(
redBlack.getValue())) {
right.getParent().setLeft(right);
} else {
right.getParent().setRight(right);
}
}
}
}
}
private void rightRotate(RedBlack redBlack) {
if (redBlack != null) {
RedBlack left = redBlack.getLeft();
if (left != null) {
redBlack.setLeft(left.getRight());
if (left.getRight() != null) {
left.getRight().setParent(redBlack);
}
left.setRight(redBlack);
left.setParent(redBlack.getParent());
if (left.getParent() == null) {
root = left;
}
if (left.getParent() != null) {
if (left.getParent().getLeft().getValue().equals(
redBlack.getValue())) {
left.getParent().setLeft(left);
} else {
left.getParent().setRight(left);
}
}
}
}
}
public static void main(String[] args) {
RedBlackTree tree = new RedBlackTree();
Scanner s = new Scanner(System.in);
int a = s.nextInt();
while (a != 0) {
tree.insert(a);
a = s.nextInt();
}
tree.print();
}
}
分享到：
发表评论
-
转分布式哈希与一致hash
2011-04-22 23:39 1524分布式哈希和一致性哈希是分布式存储和p2p网络中说的比较多 ... -
计算机程序设计艺术-----归并排序
2010-12-22 15:53 835合并排序：把两个或多个有序序列合并为一个有序的序列。 ... -
计算机程序设计艺术-----堆排序
2010-12-22 12:29 940堆排序：一种基于堆的排序算法； 一些基础概念 堆定义： 当且仅 ... -
计算机程序设计艺术-----选择排序
2010-12-22 10:19 878直接选择排序： 基本思想：每一趟从待排序的数据元素中选出最小（ ... -
计算机程序设计艺术-----基数排序
2010-12-22 09:40 1347箱排序：也称桶排序。 基本思想：设置多[k]个箱，依次把a[1 ... -
计算机程序设计艺术-----快速排序
2010-12-21 18:20 876快速排序:是冒泡排序的改进。 基本思想：通过一趟排序把整个序列 ... -
计算机程序设计艺术之shell编程
2010-12-21 15:06 802Shell排序：一种插入排序。 距离的概念：两个数之间的间隔i ... -
计算机程序设计艺术-----冒泡排序
2010-12-21 10:36 1372冒泡排序：一种最简单 ...
相关推荐
AVL树-红黑树-B树.ppt
C,C++,数据结构 亚嵌第七次在线课堂-红黑树-朱仲涛
1.红黑树 - 1 - 1.1需求分析 - 1 - 1.2算法设计 - 1 - 1.2.1旋转 - 1 - 1.2.2插入 - 2 - 1.2.3删除 - 4 - 1.3 数据结构设计 - 5 - 1.4 运行结果 - 6 - 1.5 结果分析 - 7 - 1.6 优化 - 8 - 1.7 心得体会 - 8 - 1.8...
红黑树算法，随机产生数字，动态生成红黑树，可用于演示。
红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树...
作者给出了一种新的二叉查找树———红黑树的定义和建树方法,并给出了它在最坏情况下的查找效率估计。
平衡二叉树-红黑树的实现
在学习c++的过程中实现的红黑树,功能比较完善,无优化..
红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
AVL_红黑树_前缀树.
红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
通用红黑树 说明： 用Linux内核红黑树封装的一个通用型的红黑树 如何使用该红黑树： 见rbtest1.c和rbtest2.c 直接make生成rbtest1和rbtest2 作者：rcyh 日期：2011年7月21日 ---------------------------------...
经典的红黑树讲解文籍，从2-3-4树讲起，逐步过渡到红黑树的底层原理，是学习算法的经典参考。
红黑树的 插入 删除 遍历 算法导论 数据结构
红黑树原理详解 红黑树原理详解 红黑树原理详解 红黑树原理详解
红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组
从2-3树理解红黑树的ppt，包括概念，原理，插入、删除、转换等。
NULL 博文链接：https://709002341.iteye.com/blog/2259560
红黑树的c实现源码与剖析 原作者：那谁 源码剖析作者：July ===================== July说明： 由于原来的程序没有任何一行注释，我把它深入剖析，并一行一行的添加了注释， 详情请参见此文： 教你彻底实现红黑树：...
封装了linux 内核 红黑树，纯C语言，外层已经封装好了，直接使用，有压力测试，很不错