一、相关的
二、红黑树的疑惑 参考阅读
1.红黑树的目的
=》当然也是为了保证查找树的最坏情况也也有O(log N)的查找效率
2.那么这里还有个问题红黑树和AVL树的优缺点
=》因为他们的目的是相同的等看完这部分了再说吧
3.我自己的疑惑红黑树的颜色干什么用的
=》我很惊奇数据怎么分颜色了，作用是什么
4.这些查找的用途是什么那？
=》我只是知道有这么个数据结构，那么用于什么方面哪？
=》其实这个自问很白痴，肯定是查找，但是实际接触的应用场景哪？（知道了补充）
=》系统中的内存管理好象用的是红黑树
=》B树在数据库、搜索上用
三、红黑树 参考维基百科
1.约束
（1）节点是红色或黑色
（2）根是黑色
（3）所有叶子都是黑色（叶子是NIL节点=》结束标志）
（4）红色的两个子节点都是黑市（从每个叶子到根的所有路径上不能有两个连续的红色节点）
（5）从任一节点到其每个叶子节点所有的路径都包含相同数目的黑色节点
=》（4）（5）确定了路径只差在两倍的范围之内
2.实现
=》本质上红黑书还是查询树的性质
2.1插入
首先插入的节点是用红色的？
=》如果设置为黑色那么这棵树就该是满二叉树符合要求吧
//可能出现的情况 //插入过程中如果是根节点 =》那么把颜色改为黑色
//可能出现的情况2 //父节点时黑色的 =》因为插入的是红色的 =》路径黑色数目没有改变 =》黑色子节点是红色还是定的
//可能出现的情况3 //父节点出入的是红色的并且父节点的兄弟节点也是红色 =》处理办法把父节点和它的兄弟节点改为红色 =》祖父节点改为红色（因为路径上的黑色数目不改变） =》改变之后又和可能出现的问题是祖父的节点情况跟当前一样
//可能出现的情况4 //父节点时红色但是父节点的兄弟节点是黑色或者缺少 =》处理办法进行一次左旋转 //然后按照情形5处理
//可能出现情形5 //当前节点时父节点的左子树，父节点也是左子树 =》针对祖父节点G进行右旋转 =》然后改变下父节点和祖父节点的颜色
//综合上述，插入情况的1和2都是不要考虑情况的
//问题就变成如下：
//父节点是在左边还是在右边
//叔叔节点时红色，还是其他情况
/*
*参考：http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91
* http://blog.csdn.net/v_JULY_v/article/details/6114226
**/
enum Colors {
RED, BLACK
}
public class RedBlackTree {
public static void main(String[] args) {
Node head = null;
Scanner scanner = new Scanner(System.in);
while (true) {
int data = scanner.nextInt();
if (data == -1)
break;
head = insertNode(head, data);
}
inorderReserve(head);
}
/*
* Insert the nodeDefault the color is redReturn the
*/
public static Node insertNode(Node head, int num) {
Node temp = null;
Node node = searchNode(head, num);
if (node != null && node.getNum() == num)
return node; // if exist return this
temp = new Node(num);// insert node
if (node != null) {
temp.setParent(node);// set the insert node parent
if (node.getNum() > num)
node.setLeftChild(temp);
else
node.setRightChild(temp);
} else {// head is null
head = temp;
}
return insertReBalance(temp, head);// 传递head的目的是保证root一直可以得到
}
/*
* Accoding to the current satate of the node to detemine the change;
* 1.插入的是根节点
* 2.插入的父节点时黑色因为红色不影响路径里的黑色个数，所以不会破坏任何条件
* 3.父节点红色和叔父节点都是红色
* 4.父节点红色和叔叔节点不是红色是LR情况
* 5.父节点红色和叔叔节点不是红色是LL情况=》对于1，2两种情况不用处理的
* =》如果对于父节点时红色肯定有祖父节点
*/
public static Node insertReBalance(Node node, Node head) {
// avaliable variable
Node parent, uncle, grandParent,temp;
while ((parent = node.getParent()) != null
&& (parent.getColor() == Colors.RED)) { // parent is not null
// and color is red
grandParent = parent.getParent();
if (parent == grandParent.getLeftChild()) {
uncle = grandParent.getRightChild();
if (uncle != null && uncle.getColor() == Colors.RED) // 情景3
{
uncle.setColor(Colors.BLACK); // uncle and parent become black
parent.setColor(Colors.BLACK);
grandParent.setColor(Colors.RED); // grandgetParent() become red
node = grandParent; // grandgetParent() become node to
// determine the 1
} else { // 叔父节点不为红色
if (parent.getRightChild() == node) { // node 在父节点的右边
head=RR(parent,head); // 因为LR的操作是要先RR=》LL
temp=parent;
parent=node;
node=temp;
}
// LL情况
parent.setColor(Colors.BLACK);
grandParent.setColor(Colors.RED);
head=LL(grandParent,head);
}
} else {
uncle = grandParent.getLeftChild();
if (uncle != null && uncle.getColor() == Colors.RED) // 情景3
{
uncle.setColor(Colors.BLACK); // uncle and parent become black
parent.setColor(Colors.BLACK);
grandParent.setColor(Colors.RED); // grandgetParent() become red
node = grandParent; // grandgetParent() become node to
// determine the 1
} else { // 叔父节点不为红色
if (parent.getLeftChild() == node) {
head=LL(parent,head); //RL=>LL=>RR
temp=parent;
parent=node;
node=temp;
}
parent.setColor(Colors.BLACK);
grandParent.setColor(Colors.RED);
head=RR(grandParent,head);
// inorderReserve(head);
}
}
}
head.setColor(Colors.BLACK); // root is always black;
return head;
}
/*
* a b
* / / \
* b => c a
* /
* c
* here node=a
**/
public static Node LL(Node node, Node head) {
Node b = node.getLeftChild();
if(node.getParent()!=null){ //如果node不是根节点
node.getParent().setLeftChild(b);
}else{
head=b;
}
node.setLeftChild(b.getRightChild());// 子节点转换
b.setRightChild(node);
b.setParent(node.getParent()); // 父节点转换
node.setParent(b);
return head;
}
/*
* a b
* \ / \
* b => a c
* \
* c
* here node=b
**/
public static Node RR(Node node, Node head) {
Node b = node.getRightChild();
if(node.getParent()!=null){ //如果node不是根节点
node.getParent().setRightChild(b);
}else{
head=b;
}
node.setRightChild(b.getLeftChild());
b.setLeftChild(node);
b.setParent(node.getParent()); // 父节点转换
node.setParent(b);
return head;
}
/*
* a a
* / /
* b => c =>LL
* \ /
* c b
* here node=a
**/
public static Node LR(Node node, Node head) {
node = RR(node.getLeftChild(), head);
return LL(node, head);
}
/*
* a a
* \ \
* b => c =>RR
* / \
* c b
* here node=a
**/
public static Node RL(Node node, Node head) {
node = LL(node.getRightChild(), head);
return RR(node, head);
}
/*
* Detemine whether there is keyBut didn't change the headIf exist return
* the NodeIf not exist return the insert positionSo must detemine it again
*/
public static Node searchNode(Node head, int key) {
Node temp = null;
int num;
while (head != null) {
num = head.getNum();
temp = head;
if (num < key)
head = head.getRightChild();
else if (num > key)
head = head.getLeftChild();
else
return head;
}
return temp;// if not exist return the parent!
}
public static void inorderReserve(Node head) {
if (head != null) {
inorderReserve(head.getLeftChild());
System.out.println(head.getNum()+" Color:"+head.getColor());
inorderReserve(head.getRightChild());
}
}
}
class Node {
private int num;
private Colors color;// 0-red 1-black
private Node leftChild;
private Node rightChild;
private Node parent;
public Node(int num) {
// init the num
this.num = num;
// default the color
this.color = Colors.RED;
this.leftChild = this.rightChild = this.parent = null;
}
}
2.删除
//X的兄弟是红色的-1 //对X的父节点做一次左旋 //X的父节点和兄弟改变颜色
//X的兄弟是黑色的-2 //X的兄弟的孩子都是黑色的 //X的兄弟节点变为红色 //X父节点为新的节点X
//X的兄弟是黑色的-3 //X的兄弟左孩子是红色，右孩子是黑色 //交换X兄弟和它左孩子的颜色 //然后对它兄弟进行右转 //变成问题4
//X的兄弟是黑色的-4 //X的兄弟的右孩子是红色的 //颜色修改 //X的父节点做旋转
相关推荐
红黑树广泛应用于各种数据结构和算法中，例如标准模板库（STL）中的`std::map`和`std::set`就是基于红黑树实现的，它们提供了一种高效、有序的键值对存储方式。此外，数据库索引、虚拟内存管理、编译器符号表等也都...
总的来说，这个数据结构课程设计的红黑树源码是学习数据结构和算法的好材料，特别是对于C++和MFC使用者，它展示了如何将抽象的数据结构与实际编程结合，提供了实用的图形化界面展示，有助于初学者理解和掌握红黑树这...
红黑树之所以被称为“近似平衡”，是因为它并不像AVL树那样严格要求左右子树的高度差不超过1，而是允许一定的不平衡存在。尽管如此，红黑树依然能够保持较低的高度，一般情况下，最坏情况下红黑树的高度不超过2log2...
数据结构—红黑树 红黑树是一种自平衡二叉查找树，它的每个结点都遵守着某些特性，红黑树的出现是为了解决二叉查找树的缺陷，即在插入和删除操作时可能会出现最坏情况的运行时间为O(N)，红黑树通过引入一些平衡条件...
红黑树是计算机科学中的一个重要概念，尤其在数据结构的学习和应用中占据核心地位。作为东南大学计算机系高级数据结构实验的一部分，红黑树的深入探究对于学生掌握复杂数据结构和算法具有重要意义。本文将详细介绍...
总而言之，红黑树之所以成为许多系统实现中的首选数据结构，是因为其高效的自平衡能力。这使得在各种动态场景中，例如在大规模数据的快速查找、插入和删除操作中，红黑树能够提供稳定的性能。尽管实现红黑树的插入和...
总结来说，红黑树是一种重要的数据结构，它的动态演示是理解和掌握其工作原理的有效工具。通过随机数字的插入，我们可以直观地看到红黑树如何维持其平衡特性，这有助于提升我们在算法和数据结构方面的知识。
### 一种高效二叉查找树——红黑树 #### 一、引言 在计算机科学领域，二叉查找树(Binary Search Tree, BST)是一种非常重要的数据结构，它能够有效地实现查找、插入和删除等基本操作。然而，在某些情况下，普通的...
红黑树是一种自平衡的二叉查找树，它在数据结构和算法领域有着重要的应用，尤其是在需要高效查找、插入和删除操作的场景中。它的设计目标是确保任何节点到其每个叶子节点的所有路径都大致相等，从而避免了二叉查找树...
红黑树（Red-Black Tree）是一种自平衡二叉查找树，它在计算机科学中扮演着重要的角色，尤其是在实现高效的数据结构和算法时。在Java中，虽然标准库并未直接提供红黑树的类，但我们可以自定义实现，如提供的`Red...
红黑树作为高效的数据结构，广泛应用于各种场景，如STL（Standard Template Library）中的map和set容器，以及编译器的符号表管理等。 算法是解决问题或执行任务的精确步骤集合。红黑树的插入、删除和查找算法都需要...
`RBTree.h`是头文件，定义了红黑树的数据结构和接口。阅读这些文件，可以深入理解红黑树的C语言实现细节。 通过理解红黑树的原理并实践其C语言实现，我们可以更好地掌握数据结构的核心概念，并在实际编程中灵活应用...
总结来说，红黑树是一种重要的数据结构，广泛应用于各种需要高效查找、插入和删除操作的场景，如内存管理、数据库索引、编译器符号表等。掌握红黑树的概念和操作是提升算法和数据结构能力的关键，而"红黑树数据结构...
通过红黑树实现的这些数据结构在性能上比传统的链表或数组有显著优势，特别是在大量的插入、删除和查找操作中。 总结来说，红黑树是一种高效且平衡的二叉查找树，其核心在于通过颜色规则保证树的平衡性，从而优化...
掌握红黑树的原理和实现细节，对于理解和优化数据结构的性能至关重要，特别是在需要高效查找、插入和删除操作的场景下。通过分析和实践提供的源码，你可以深入了解红黑树的内部工作机制，并提升自己的编程能力。
红黑树是一种自平衡二叉搜索树，在实际应用中，它广泛用于Linux内核、Java的TreeMap和TreeSet数据结构以及C++的STL中。红黑树的设计旨在保持树的平衡，但是与AVL树不同，它追求的不是绝对的平衡，而是通过放弃一定的...
红黑树是一种自平衡二叉查找树（Self...rbtree文件可能包含了实验的源代码和相关报告，这对于理解和掌握红黑树这一高级数据结构非常有帮助。通过这样的实践，学生不仅可以提升编程能力，还能加深对数据结构理论的理解。
本文将深入探讨Java中树的数据结构，特别是红黑树的实现，以及如何构建一个有效的学习路线。 首先，让我们从"树的基本概念"开始。树是一种非线性的数据结构，它由节点（或称为顶点）和边构成，每个节点可以有零个或...
理解红黑树有助于深入理解数据结构和算法，提升编程能力，特别是在处理大量数据的排序、查找等场景，能够编写出高效且稳定的代码。 7. **应用拓展**： 红黑树的原理也可以应用于其他自平衡二叉树，例如B树、B+树...
在ACM（国际大学生程序设计竞赛）中，数据结构和算法是至关重要的部分，红黑树因其高效的特性，常被用作解决复杂问题的基础。 1. **红黑树的基本属性** - **颜色属性**：每个节点都有红色或黑色。 - **根节点**：...