红黑树
红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由鲁道夫·贝尔发明的，他称之为"对称二叉B树"，它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目。
性质：
红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
性质1. 节点是红色或黑色。
性质2. 根是黑色。
性质3. 所有叶子都是黑色（叶子是NIL节点）。
性质4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
性质5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
红黑树是一种经典的数据结构，在linux内存管理、nginx 等很多地方用到它。主要操作包括插入、删除，其中插入6种情况，删除8种情况，详细的思路就不说了，如果不太明白的请参考算法导论13章，看的时候一定要把每一种插入、删除的情况在纸上自己画出来，这样会节省你很多时间。下面是java实现的代码：
红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在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();
}
}
分享到：
发表评论
-
文件上传 下载 解析 相对路径
2014-12-16 16:29 2077有点坑吧，弄这么一个简单的东西弄了一天多，身边还有大神指导着， ... -
发送邮件
2014-10-15 11:29 651import org.apache.commons.m ... -
Enum用法
2014-08-06 10:27 776以前的时候知道enum，但 ... -
Java中的instanceof关键字
2014-07-21 11:14 426Java中的instanceof关键字 [size=larg ... -
Comparable接口
2014-07-21 11:01 479因为在学红黑树的时候用到了Comparable接口，故此学习一 ... -
二叉查找树
2014-07-15 10:57 584二叉排序树（Binary Sort Tree）又称二叉查找树（ ... -
二叉树的三种遍历
2014-07-10 11:28 594前序遍历（DLR） 前序 ... -
Java中如何写代码实现无标题无边框的窗体能够用鼠标拖动改变窗口大小
2014-01-23 17:16 1543import java.awt.*; import java ... -
Swing基础
2014-01-10 10:22 403JFrame: frame = new JFrame(); ... -
游戏音效素材大全下载 - 3000首高清无损-按分类整理
2014-01-09 18:03 464因为我看到国外很多素材，但是国内不多，我希望来做好这个事情。 ... -
Swing 键盘练习
2014-01-09 17:59 579在swing界面中写一个键盘，使用前记得放置背景图片 imp ... -
JAVA的Socket的聊天器
2014-01-09 11:06 452这是刚开始学习java网络编程的时候做的一个东东，，局域网聊天 ... -
驱动打印
2013-12-27 15:16 630java驱动打印代码： PrintTest.print(pr ... -
java程序打包
2013-12-27 15:17 509打包一般分为两种，一种是B/S架构打包，一种是C/S打包，大同 ... -
读取文件夹下的所有文件
2013-12-20 13:19 461文章来源:http://www.blogjava.net/ba ... -
实现天气预报功能
2013-12-02 10:30 553import java.io.BufferedReader; ... -
JMF播放AVI格式的视频
2013-12-02 10:26 727public class Conver { publ ... -
JMF视频播放器
2013-12-02 10:24 1111import java.awt.BorderLayout; ...
相关推荐
红黑树（Red-Black Tree）是一种自平衡二叉查找树，由计算机科学家鲁道夫·贝尔在1978年提出。它在保持二叉查找树特性的同时，通过引入颜色属性来确保树的平衡，从而提高了数据操作的效率。红黑树的主要目标是保证在...
红黑树（Red-Black Tree）是一种自平衡二叉查找树，它的每个节点都带有颜色属性，可以是红色或黑色。这种数据结构被广泛应用于计算机科学的许多领域，特别是操作系统、数据库系统以及编译器中，用于高效地执行插入、...
红黑树是一种自平衡二叉查找树，由Rudolf Bayer在1972年发明。它的名称来源于其节点颜色属性，即红色和黑色。红黑树的主要特性保证了其在插入、删除和查找操作中的高效性能，通常时间复杂度为O(log n)，其中n是树中...
红黑树是一种自平衡二叉查找树，由Rudolf Bayer于1972年提出。它的设计目标是在保持二叉查找树基本属性的同时，通过引入颜色（红色或黑色）来保证树的平衡，从而在插入和删除操作后能够快速恢复平衡状态，减少查找、...
红黑树和AVL树是两种自平衡二叉查找树，它们在计算机科学中的数据结构领域扮演着重要的角色，主要用于高效地存储和检索数据。这两种数据结构的主要目标是在插入和删除操作后保持树的平衡，从而确保搜索、插入和删除...
红黑树（Red-Black Tree）是一种自平衡二叉查找树，它在计算机科学中扮演着重要的角色，尤其是在实现高效的数据结构和算法时。在Java中，虽然标准库并未直接提供红黑树的类，但我们可以自定义实现，如提供的`Red...
红黑树是一种自平衡二叉查找树，由Rudolf Bayer在1972年提出。它的设计目标是在保持二叉查找树基本属性的同时，通过引入颜色（红色或黑色）来保证树的平衡，从而提高查找、插入和删除操作的效率。在红黑树中，每个...
红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树...
红黑树是一种自平衡二叉查找树，它的设计目的是为了在保持查找效率的同时，尽可能地减少插入和删除操作带来的性能损失。在计算机科学中，它是一种广泛应用的数据结构，特别是在动态排序和高效查找方面。 二叉搜索树...
通用红黑树 说明： 用Linux内核红黑树封装的一个通用型的红黑树 如何使用该红黑树： 见rbtest1.c和rbtest2.c 直接make生成rbtest1和rbtest2 作者：rcyh 日期：2011年7月21日 ---------------------------------...
红黑树是一种自平衡二叉查找树，由Rudolf Bayer在1972年提出。它的设计目标是在保持二叉查找树基本性质的同时，通过引入颜色属性来保证树的平衡，从而达到高效的插入、删除和查找操作。红黑树的关键特性是： 1. 每...
### 红黑树知识点详解 #### 一、红黑树定义与性质 红黑树是一种自平衡二叉查找树，其每个节点除了保存键值、左子节点、右子节点和父节点的信息外，还额外保存了一个表示颜色的属性（红色或黑色）。红黑树在进行...
红黑树和区间树是两种在计算机科学中广泛使用的数据结构，主要应用于高效的数据存储和检索。它们在算法和数据结构领域具有重要地位，尤其在处理动态集合或需要快速查找和更新操作的问题时。 首先，我们来详细了解...
红黑树是一种自平衡二叉查找树（self-balancing binary search tree），由计算机科学家Rudolf Bayer在1972年提出。它在保持二叉查找树特性的同时，通过引入颜色属性来确保树的平衡，从而提高数据操作的效率。在红黑...
红黑树（Red-Black Tree）是一种自平衡二叉查找树，它在计算机科学中扮演着重要的角色，尤其是在数据结构和算法领域。红黑树的名字来源于它的节点颜色属性：红色或黑色。这种颜色属性被用来确保树的某些关键性质，...
红黑树是一种自平衡二叉查找树，它的主要特点是在保持二叉查找树特性的同时，通过特定的颜色规则来确保树的平衡，以达到快速查找、插入和删除的目的。红黑树的每个节点都有一个颜色属性，可以是红色或黑色。在插入新...
红黑树是一种自平衡二叉查找树，由Rudolf Bayer在1972年提出。它的设计目标是在保持查询效率高的同时，尽可能地减少由于插入和删除操作引起的树的不平衡。红黑树的主要特点包括： 1. **颜色属性**：每个节点都有...
红黑树（Red-Black Tree）是一种自平衡二叉查找树，它在计算机科学中扮演着重要的角色，尤其是在数据结构和算法领域。红黑树的名字来源于它的节点颜色属性：红色或黑色。这种颜色属性用于确保树的平衡，使得在树中的...
红黑树（Red-Black Tree）是一种自平衡二叉查找树，由计算机科学家Rudolf Bayer在1972年提出。它在数据结构和算法领域具有重要地位，被广泛应用于各种系统和软件中，包括数据库索引、编译器、虚拟机等。在Delphi编程...