红黑树
时间限制:3000 ms | 内存限制:65535 KB
难度:3
描述
什么是红黑树呢?顾名思义,跟枣树类似,红黑树是一种叶子是黑色果子是红色的树。。。
当然,这个是我说的。。。
《算法导论》上可不是这么说的:
如果一个二叉查找树满足下面的红黑性质,那么则为一个红黑树。
1)每个节点或是红的,或者是黑的。
2)每个叶子节点(NIL)是黑色的
3)如果一个节点是红色的,那么他的两个儿子都是黑的。
4)根节点是黑色的。
5)对于每个节点,从该节点到子孙节点的所有路径上包含相同数目的黑色节点。
我们在整个过程中会用到这些性质,当然,为了公平起见,其实即使你不知道这些性质,这个题目也是可以完成的(为什么不早说。。。。)。在红黑树的各种操作中,其核心操作被称为旋转,那么什么是旋转呢,我们来看一个例子:
假设我们这里截取红黑树的一部分,放在左边,通过操作如果可以把他转化为右边的形式,那么我们就称将根为x的子树进行了左旋,反之我们称将根为Y的树进行了右旋:
恰好慢板同学把自己红黑树弄乱了,然后请你帮忙进行修复,他将向你描述他的红黑树(混乱的。。。)。然后告诉他需要用哪种方式旋转某个节点。在你完成工作之后,直接向大黄提交新的树的中序遍历结果就好了。
Hint:
在这里好心的慢板同学给你简单的解释下样例:
最开始的时候树的样子是这样的:
0
/ \
1 2
然后对于标号为0的节点进行右旋,结果将变为:
1
\
0
\
2
然后呢。。。
中序遍历?这个是什么东西,哪个人可以告诉我下。。。。
输入
输入分两部分:
第一部分:一个整数T(1<=T<=10),表示测试的组数。
第二部分:第一行是一个数字N,表示红黑树的节点个数。0<N<10
然后下面有N行,每行三个数字,每个数字的大小都在-1~N-1之间。第一个数字表示当前节点的标号,后面两个数字表示这个节点的左孩子和右孩子。如果是-1的话表示是空节点。对于所有的输入来说标号为0节点为根。
然后是一个数字M表示需要旋转的次数。M<100
接下来M行,每行有两个数字,分别表示你要旋转的节点标号和你需要的操作。标号的范围为0~n-1,如果标号后面的数字0,那么表示为左旋。如果是1,则表示右旋。
输出
每组测试返回N行数字,表示对树的中序遍历。在每组测试数据之后留一行空行。
样例输入
1
3
0 1 2
1 -1 -1
2 -1 -1
1
0 1
样例输出
1
0
2
注意:二叉树的旋转并不影响中序遍历序列,所以无需考虑旋转的问题,直接保存树,然后对其进行中序遍历即可。
如下奉上java代码:
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner intput = new Scanner(System.in);
int circleNumber = intput.nextInt();
while(circleNumber--> 0){
int number = intput.nextInt();
Node[] nodeArray = new Node[number];
for(int i=0;i<number;i++){
int index = intput.nextInt();
nodeArray[index] = new Node(intput.nextInt(),intput.nextInt());
}
int opt_num = intput.nextInt();
for(int i = 0; i < opt_num; i++){
intput.nextInt();
intput.nextInt();
}
DFS(nodeArray, 0);
// System.out.println();
}
}
public static void DFS(Node[] nodes,int num){
if(num>-1){
DFS(nodes,nodes[num].getL_num());
System.out.println(num);
DFS(nodes,nodes[num].getR_num());
}
}
static class Node {
Node(int l_num,int r_num){
this.l_num = l_num;
this.r_num = r_num;
}
private int l_num;
private int r_num;
public int getL_num() {
return l_num;
}
public int getR_num() {
return r_num;
}
}
}
分享到:
相关推荐
NYOJ,全称为南阳理工学院在线评测系统(Nanyang Institute of Technology Online Judge),是为ACM(国际大学生程序设计竞赛)以及其他编程爱好者提供的一种在线编程练习平台。该系统支持用户提交代码并进行实时...
### nyoj部分ACM答案解析 #### 背景与目的 本篇文章旨在解析一个针对NYOJ(网络在线裁判系统)中ACM题目解答的示例代码。该代码使用了C++语言,并且主要涉及到了回溯算法的实现。对于初学者来说,通过深入理解这段...
查询字符串时,同样按照字符顺序遍历树,若能到达一个标记为字符串结尾的节点,则表示该字符串存在于字典中。 在NYOJ.290.DictionaryTree.cpp文件中,可能包含了以下内容: 1. `TrieNode`结构体定义,用于表示Trie...
NYOJ(New York Online Judge)是一个在线编程竞赛平台,主要面向ACM(国际大学生程序设计竞赛)的参与者。这个离线版包含了NYOJ的所有题目,为编程爱好者和参赛者提供了一个方便的本地化练习环境。通过爬虫技术,...
解决这个问题时,可能会使用到线段树、平衡二叉搜索树(如AVL或红黑树)或者堆等数据结构,以高效地存储和查询矩形的信息。这些数据结构可以用于快速检索矩形的边界、比较大小以及计算嵌套关系。 3. **算法设计**...
总结来说,这个压缩包文件包含了一个关于最大单调递增子序列的问题,可能还有一个与之相关的矩形嵌入问题,这些问题都要求高效的算法实现,可以通过动态规划或贪心策略来解决。解压并阅读“nyoj16.cpp”文件,我们...
NYOJ,全称New York Online Judge,是一个在线编程竞赛平台,提供了丰富的ACM竞赛训练题目。离线版的NYOJ可能是将该平台的部分内容打包成CHM文件,方便用户在没有网络的情况下查阅和练习。这个CHM文件可能包含题目的...
双线程动态规划问题,很值得练习。传一个ac代码,测试一下csdn的功能。
set和map是关联容器,以红黑树实现,用于存储唯一元素并支持快速查找。 2. 迭代器: 迭代器是STL的重要概念,它像指针一样指向容器中的元素,但具有更多操作。例如,可以使用迭代器进行元素的增删查改,遍历容器,...
由于微信小程序没有方法可以获得当前用户所在城市的信息,所以需要调用方法来获取城市信息,用了两个方法去发送请求并返回城市信息 1. @Controller public class WechatLocationManager { private Logger logger ...
前期小程序开发只进行到根据微信...在开发微信小程序的时候,由于对于需求的不理解,导致半天都发在获取用户信息的方法上,由于微信小程序没有access_token,所以,用户信息只能从前台发出,后台负责接收并封装JSON格
这个小程序的主要目的是为了用户用微信的用户信息登录后将用户信息授权存入自己的数据库中,这样以后每次微信登录得到的code 所得到的 openid 可以在项目的数据库中查到该用户的相关信息。 在测试的过程中,需要用户...
该题要求对离散化的线段进行覆盖分析,线段树是一种高效的数据结构,能够支持区间查询和更新操作,适用于此类问题。 #### 10. skiing 经典动态规划题目,旨在寻找最佳路径,这类问题通常需要建立状态转移方程,以...
给定一个由整数组成二维矩阵(r*c),现在需要找出它的一个子矩阵,使得这个子矩阵内的所有元素之和最大,并把这个子矩阵称为最大子矩阵。