/* 作者:田帅
学校:**大学
版本:红黑树初始版本
*/
#include"stdio.h"
#include"malloc.h"
#define MIN -99999999 //不要加等号
#define MAX 99999999
struct node
{
long key;
char color;
struct node *p;
struct node *leftChild;
struct node *rightChild;
};
node *nil,*root;//创建根节点和叶子节点
int printnode=0;
node *CreateNode(int key);
void RB_insert_fixUp(node *T,node *z);
void nil_create();//叶子节点创建
void RB_insert(node *T,node *z);//弄算法导论上非递归的吧
void left_rotate(node *T,node *z);//向左旋转
void right_rotate(node *T,node *z);
void PrintRBTree(node *T);//输出树
void nil_create()//叶子节点创建
{
nil=(node *)malloc(sizeof(node));
root=(node *)malloc(sizeof(node));
nil->key=MIN;
nil->color='B';
//nil->p=NULL;//这里注意
nil->leftChild=nil;
nil->rightChild=nil;
root=nil;
}
node *CreateNode(int key)
{
node *x = (node *)malloc(sizeof(node));
x->color ='R';
x->key = key;
x->leftChild = nil;
x->rightChild = nil;
x->p = NULL;
return x;
}
void RB_insert(node *T,node *z)//弄算法导论上非递归的吧
{
node *x,*y;//y用来记录父节点
x=root;//这里应该是 根节点 跟形式参数重复 会造成错误
y=nil;
while(x!=nil)//x为要插入的位置de父节点 y为x的父节点
{
y=x;
if(x->key>z->key)
x=x->leftChild;
else
x=x->rightChild;
}
z->p=y;
if(y==nil)//初始化 插入到空树种
root=z;
else if(z->key<y->key)
y->leftChild=z;
else
y->rightChild=z;
z->leftChild=nil;
z->rightChild=nil;
z->color='R';
RB_insert_fixUp(T,z);
}
void RB_insert_fixUp(node *T,node *z)
{
node *y;
while(z->p->color=='R')//插入节点 是红节点 如果父节点也是红节点 则需要调整
{
if(z->p==z->p->p->leftChild)//插入的节点的父节点 是祖父节点的左孩子
{
y=z->p->p->rightChild;//祖父节点的右孩子
if(y->color=='R')//二叔是 红色的O(∩_∩)O哈哈~
{
z->p->color='B';
y->color='B';
z->p->p->color='R';
z=z->p->p;
}
else
{//这个地方一定要加上 {
if(z==z->p->rightChild)//二叔是黑色 且 要插入的节点是右孩子
{
z=z->p;
left_rotate(T,z);
}
z->p->color='B';//二叔是黑色 且要插入的节点是左孩子
z->p->p->color='R';
// z->p->p->color='R'; //???????????????????????????
right_rotate(T,z->p->p);
}
}
else//插入的节点的父节点 是祖父节点的右孩子
{
y=z->p->p->leftChild;//祖父节点的左孩子
if(y->color=='R')//二叔是 红色的O(∩_∩)O哈哈~
{
z->p->color='B';
y->color='B';
z->p->p->color='R';
z=z->p->p;//???????
}
else
{
if(z==z->p->leftChild)//二叔是黑色 且 要插入的节点是左孩子
{
z=z->p;
right_rotate(T,z);
}
z->p->color='B';//二叔是黑色 且要插入的节点是右孩子
z->p->p->color='R';
left_rotate(T,z->p->p);
}
}
}
root->color='B';//这里不要落下!!!
}
void left_rotate(node *T,node *z)//向左旋转
{
node *y;
y=z->rightChild;//让y 为要旋转的节点的右子树
z->rightChild=y->leftChild;
if(y->leftChild!=nil)
y->leftChild->p=z;
y->p=z->p;//将要旋转节点切下
if(z->p==nil)
root=y;
else if(z==z->p->leftChild)//要旋转节点是 其父节点左孩子
z->p->leftChild=y;
else//要旋转节点是 其父节点右孩子
z->p->rightChild=y;
y->leftChild=z;//将要旋转节点挂到 代替它的孩子的左子树上
z->p=y;
}
void right_rotate(node *T,node *z)
{
node *y;
y=z->leftChild;//让y 为要旋转的节点的左子树
z->leftChild=y->rightChild;
if(y->rightChild!=nil)
y->rightChild->p=z;
y->p=z->p;//将要旋转节点切下
if(z->p==nil)
root=y;
else if(z==z->p->leftChild)//要旋转节点是 其父节点左孩子
z->p->leftChild=y;
else//要旋转节点是 其父节点右孩子
z->p->rightChild=y;
y->rightChild=z;//将要旋转节点挂到 代替它的孩子的左子树上
z->p=y;
}
void PrintRBTree(node *T)
{
int i;
if(T != nil)
{
for(i = 0; i <= printnode;i++)
printf(" ");
printf("(%d",T->key);
if(T->color == 'B')
printf("B,\n");
else
printf("R,\n");
printnode++;
PrintRBTree(T->leftChild);
PrintRBTree(T->rightChild);
printnode--;
for(int j = 0; j <= printnode;j++)
printf(" ");
printf("),\n");
}
else
{
for(int i = 0; i <= printnode;i++)
printf(" ");
printf("Nil,\n");
}
}
void INORDER_TREE_WALK(struct node* x) //中根遍历
{
//printf("%ld %c ",x->key,x->color); //debug 先根遍历
if(x->leftChild!=nil)
INORDER_TREE_WALK(x->leftChild);
printf("%ld %c ",x->key,x->color);
if(x->rightChild!=nil)
INORDER_TREE_WALK(x->rightChild);
}
int main()
{ //long a[11]={4,1,3,2,16,9,10,14,8,7};
//long a[10]={10,9,8,7,6,5,4,3,2,1};
// long a[10]={1,2,3,4,5,6,7,8,9,10};
// long a[]={1,2,3,4,5,6,7,8,9,10};//这个可以
long a[]={4,1,3,2,16,9,10,14,8,7};//这个不可以
node *z[11];
nil_create();
// nil=(node *)malloc(sizeof(node));
// nil=nil_create();
printf(" 1111111");
for(int j = 0; j <10; j++)
{
printf(" 222222 ");
z[j]=CreateNode(a[j]);
RB_insert(root,z[j]);
}
printf(" 222222 ");
INORDER_TREE_WALK(root);
// PrintRBTree(root);
return 0;
}
出现的错误及调试方法:
总是到insert_fix_up时候出现错误;原因是 第三种情况 要写在 if(y.color=='R') else{ if() ; ********} 不要忘记在else 之后加上 大括号
分享到:
相关推荐
#### 四、红黑树操作解析 1. **插入操作**:在红黑树中插入一个新节点涉及到一系列复杂的旋转和重新着色过程,以保持红黑树的性质不变。 2. **删除操作**:同样地,删除操作也需要进行相应的旋转和重新着色操作来...
在实际操作中,首先要对Linux内核的红黑树源码进行分析,理解其结构和操作流程,然后逐个解决上述问题。对于rbtree这个文件,它可能是包含红黑树实现的源代码文件,可能包含了红黑树的节点定义、颜色定义、旋转操作...
4. 树:二叉树、平衡树(如AVL树、红黑树)、堆(最大堆和最小堆)等,理解它们的性质和操作,如搜索、插入、删除等。 5. 图:邻接矩阵和邻接表的表示,图的遍历(深度优先搜索和广度优先搜索),最短路径算法(如...
作者在编写源码时,对内存池、缓冲区、字符串、链表、红黑树等经典数据结构进行了自定义实现,以及构建了自己的事件驱动模型和HTTP解析机制,使其性能优于其他同类产品。尽管源码耦合度较高,但精巧的代码结构和简洁...
源码中可能包含如红黑树、哈希表等高效数据结构,以及多线程、锁机制、队列等并发控制手段,这些都是保证游戏流畅运行的关键。 其次,服务器的架构设计也是值得关注的焦点。"征途"可能采用了分布式架构,通过多个子...
通过对Linux 2.6.9版本中epoll系统调用源码的分析,我们可以深刻理解epoll如何通过红黑树和就绪队列高效管理大量文件描述符。该机制特别适合在高并发的网络服务器中使用,能够显著提高系统的响应速度和吞吐量。
红黑树不要求严格的平衡,而是通过颜色属性(红色或黑色)来保持相对平衡,从而确保任何路径到叶子节点的长度最多是两倍于最短路径。这样可以保证所有操作在O(log n)时间内完成。 3. Splay树:由Daniel Sleator和...
- 树:二叉树、平衡树(如AVL树、红黑树)和多路搜索树(如B树、B+树),用于高效的查找、插入和删除操作。 - 图:包括有向图和无向图,常用于表示复杂的关系网络,如最短路径问题、拓扑排序等。 2. 算法: - ...
`set`和`map`是基于红黑树的数据结构,用于存储键值对,支持快速查找。 2. **迭代器**:迭代器是STL的重要概念,它像指针一样遍历容器中的元素,但提供了更丰富的操作,如前向、双向和随机访问迭代器。迭代器是STL...
5. **树的平衡**:对于某些类型的树,如AVL树和红黑树,保持树的平衡至关重要,以确保操作的高效性。源码可能涉及这些平衡策略的实现。 6. **数据类模块**:易语言中的数据类模块可能封装了上述所有操作,提供一个...
2. **数据结构**:包括线性结构(如数组、链表、栈和队列)、树形结构(如二叉树、平衡树AVL和红黑树)和图结构(如图遍历和最短路径算法)。每种数据结构的定义、操作和应用场景都有详尽的描述。 3. **排序与查找*...
- **树**:分层数据结构,每个节点可以有零个或多个子节点,如二叉树、AVL树、红黑树等。 - **图**:由节点和连接它们的边组成,用于表示对象之间的关系。 2. **算法**:解决问题或执行任务的步骤。书中可能涵盖...
树结构如二叉树、平衡树(AVL、红黑树)以及堆则在数据组织和操作中扮演重要角色。 7. **贪心算法**:贪心算法在每一步选择局部最优解,以期望达到全局最优。如霍夫曼编码就是一种典型的贪心算法应用,用于数据压缩...
6. **操作**:包括合并树、分割树、旋转树(如AVL树或红黑树的平衡操作)等,这些操作可能用于优化树的性能。 JKTree很可能包含了以上提到的一些或全部功能,通过分析和学习这个源码,开发者可以了解如何在...
collection ...所以将红黑树的实现作为源码分析的开头曲, 先解决一个大家的 疑惑, 网上大部分的资料是通过2-3树来等价红黑树的, 但其实有些红黑树的情况不能概述, 我学习的资料中是采 用2-3-4树即4阶B
而TreeMap则按照键的自然顺序或比较器顺序存储元素,基于红黑树。理解这两种数据结构的实现有助于优化数据操作。 3. **StringBuffer和StringBuilder**:在多线程环境下,StringBuffer线程安全,StringBuilder则在单...
同时,源码分析还能帮助你理解STL在实际编程中的应用和优化技巧,比如什么时候选择哪种容器,如何正确使用迭代器避免错误,以及如何利用算法提升程序性能。 此外,书中可能还涵盖了迭代器失效的常见场景、STL与原始...
常见的树包括二叉树、平衡二叉树(如AVL树和红黑树)、堆(最大堆和最小堆)以及 Trie 树等。二叉搜索树允许快速查找,平衡二叉树保证了查找效率,堆用于优先级队列,而Trie树则适用于字符串搜索。 3. **图数据结构...
`epoll`利用了内核的红黑树数据结构和事件队列,实现了高效的事件分发。在内核源码中,`epoll`的实现主要位于`fs/eventpoll.c`,其中`epOLL_CTL_ADD`、`epOLL_CTL_MOD`和`epOLL_CTL_DEL`分别对应于`epoll_ctl`的三种...