平衡树调试技巧

Posted on 2011-06-23 00:07 Mato_No1 阅读(464) 评论(2)  编辑 收藏 引用 所属分类: 平衡树
平衡树操作,尤其是Splay Tree的区间操作(当线段树用的那种),代码长且极易搞疵,当操作多的时候,甚至可能调试的时间比写代码的时间都长!
这里来总结一下平衡树在实际应用(编程)中的易疵点和调试技巧。
【平衡树(这里主要指Splay Tree)的操作】
这个MS前面已经总结过了,主要分以下几类:
(1)基本操作:查找、单结点插入、单结点删除、找第K小、求结点的排名、找指定结点的前趋和后继;
(2)进阶操作:找给定的值在树中的前趋和后继、对一个序列建平衡树、插入整棵子树、删除整棵子树;
(3)区间操作(与线段树的结合):标记(自顶向下);
(4)区间操作(与线段树的结合):最大值、总和等自底向上维护的信息;
(5)一些特别猥琐的操作(比如PKU3580的revolve);
【主要函数及其易疵点】
(1)void sc(int _p, int _c, bool _d);
将_p的_d子结点(0左1右)置为_c,这个就三句话,应该不会搞疵;
(2)void upd(int x);
更新x记录的一些信息(自底向上维护的信息,包括大小域sz),这个,有几个信息就写几句话就行了,不易搞疵;
(3)void rot(int x);
旋转操作,将x旋转到其父结点的位置。这个函数中有两个易疵点:一是若x的父结点为根,则需要在旋转后将根置为x,且将x的父结点置为0(特别注意这个);二是若x的父结点不为根,则需要将x的父结点的父结点的对应子结点(原来是x的父结点的那个)置为x;另外旋转完成后别忘了更新;
(4)void splay(int x, int r);
伸展操作,将x伸展到r的子结点处,这个操作是最核心的操作,只要记住了过程,且rot不搞疵,这个也就不会搞疵;
(5)void dm(int x);
对于有标记的结点的下放标记操作,极易疵!
首先,对于任何结点,标记一打上就必须立即生效,因此除了将x的标记取消、x的两个子结点(如果存在的话)打上标记外,还要更新两个子结点的一些域(当然这里更新千万不能用upd更新);
其次,要搞清楚x的每一个标记的类型,是叠加型标记(如整体加上某一个数的标记)、覆盖型标记(如整体置为某一个数的标记)还是逆向标记(如是否翻转过的标记,因为翻转两次等于没转),然后在下放标记的时候注意写法(因为x的子结点原来可能也有标记,此时只有覆盖型标记需要将x的子结点的原来的标记覆盖掉,对于叠加型标记,应为加法运算,对于逆向标记,应为取反操作,还有其它类型的标记分别处理);
最后还有一点,就是x的左子结点或右子结点可能不存在(0),此时就不能对这里的0号结点下放标记。
(6)int Find_Kth(int x, int K);
在以结点x为根的子树中找第K小的结点,返回结点编号;若省略x,默认x=root(即在整棵树中找);
这个一般不会搞疵,注意两个地方即可:一是有mul域的时候需要考虑mul域,二是结点如果有标记,需要在找的时候下放标记。(凡是查找操作,包括插入新结点时的查找,在查找过程中必须不断下放标记,因为查找之后很可能就要伸展);
(7)void ins(int _v);
       void ins(int x, int _v)
插入一个值为_v的结点。前者是普通插入,后者是用Splay Tree处理序列(当线段树用)时的插入,表示在第x小的结点后插入;
前者注意有三种情况:树为空;树非空且值为_v的结点不存在;树非空且值为_v的结点已存在;
后者需要注意,在将第x小的结点伸展到根,将第(x+1)小的结点伸展到根的右子结点,再插入后,需要upd上述两个结点(注意upd顺序);
(8)void del(int x);
将结点x删除。这个一般不会搞疵,唯一要注意的一点是删除后的upd;
(9)打标记操作(add、reverse、makesame等):
其实打标记操作的代码量是很少的,关键就是对于不同标记要分别处理,同(5);
(10)各种询问操作:
这个直接调出相应的域即可,几乎不可能搞疵;
(11)极其猥琐的操作(revolve等):
这个属于最易疵的操作(否则就体现不出其猥琐了):
首先要搞清楚这个操作的具体过程,不要连具体过程都搞疵了,这样写出来的代码肯定是疵的;
然后,注意一些非常猥琐的细节问题(很多时候,本沙茶都是栽在细节上的);
另外,这些操作中一般都会出现多次伸展,别忘了伸展后的upd;
(12)其它易疵点:
[1]“移动”是由“插入”和“删除”两部分组成的,因此凡是涉及到“移动”类的操作(如将某棵子树或某个结点移动到另一个位置等),必须要同时出现“插入”和“删除”,而不能只插入不删除;
[2]注意检查主函数main()中是否有搞疵的地方;

易疵点也就这么多了,下面是调试技巧:
【Splay Tree调试技巧】
(1)先用样例调试,保证样例能够通过(注意,样例中必须包含所有题目中给出的操作,如果不是这样,那在调试完样例后还要加一组包含所有题目中给出的操作的小数据);
(2)然后用mkdt造大数据,一般平衡树操作题的合法数据都不难造,只要注意别越界就行了;
(3)在调试过程中应不断少量增大数据规模,因为在能找出问题的情况下,数据规模越小越好;
(4)如果调试过程中发现死循环或者RE:
[1]首先输出每个操作,找出是在哪个操作处出了问题;
[2]进入该操作内部检查,也就是把该操作的代码读一遍,一般都能找出问题;
[3]如果找不出问题,可以进入该操作内部跟踪检查;
[4]如果跟踪检查仍然没找出问题,那可能是该操作是对的,而其它操作出了问题,此时可以弄一个vst,把整棵树遍历一下,找出真正出问题的操作,转[2];
(5)排除了死循环或RE后,接下来就是检查输出结果是否正确了:
[1]对于小规模数据可人工计算检查,对于较大规模数据则必须采用对照方法,即弄一个模拟法的代码,保证该代码正确,然后进行对照;
[2]如果发现加入遍历时,结果正确,但去掉遍历后结果不正确,则表明是处理结点标记的时候出了问题(因为在遍历过程中需要下放标记),进入dm或加标记操作中检查即可;
[3]其它情况下,可以在遍历中输出整个序列(或整棵树),进行对照,找出问题所在;
[4]如果数据过大,操作过多,人工分析时间较长,就只能采用读代码的方式检查了;
(6)最后,用mkdt造一个最大规模的数据,检查是否TLE、是否越界(数组是否开小);
如果以上各点全部通过,就可以宣布AC了。

Feedback

# re: 平衡树调试技巧  回复  更多评论   

2014-03-31 17:32 by Pn
请问mkdt是什么

# re: 平衡树调试技巧  回复  更多评论   

2014-04-03 20:29 by yc5-yc
@Pn
难道是。。。makedata?

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理