我国神童发明BST的陈启峰至西方IT界求证显露不知"The Art of Computer Programming"
Chen Qifeng
View profile
Hide options Jan 2 2007, 2:35 pm
Newsgroups: comp.theory
From: "Chen Qifeng" <344368...@qq.com>
Date: 1 Jan 2007 22:35:40 -0800
Local: Tues, Jan 2 2007 2:35 pm
Subject: Re: "Size Balanced Tree" - more efficient than any known algorithm?
Print | Individual message | Show original | Report this message | Find messages by this author
I am sorry for the vagueness about "amortized".
I means that at worst the amortized runtime of Maintain is still O(1).
It is similar with Splay. Maybe the runtime for some Maintain is more
than O(1).
Edward M. Reingold
View profile
Hide options Jan 2 2007, 9:48 pm
Newsgroups: comp.theory
From: reing...@emr.cs.iit.edu (Edward M. Reingold)
Date: 02 Jan 2007 07:48:24 -0600
Local: Tues, Jan 2 2007 9:48 pm
Subject: Re: "Size Balanced Tree" - more efficient than any known algorithm?
Print | Individual message | Show original | Report this message | Find messages by this author
>>>>> "CQ" == Chen Qifeng <344368...@qq.com> writes:
See the top of page 476 in vol. 3 of Knuth, 2nd ed.
--
Professor Edward M. Reingold Email: reing...@iit.edu
Department of Computer Science Voice: (312) 567-3309
Illinois Institute of Technology Assistant: (312) 567-5152
Stuart Building Fax: (312) 567-5067
10 West 31st Street, Suite 236
Chicago, IL 60616-3729 U.S.A.
Chen Qifeng
View profile
Hide options Jan 3 2007, 4:17 pm
Newsgroups: comp.theory
From: "Chen Qifeng" <344368...@qq.com>
Date: 3 Jan 2007 00:17:26 -0800
Local: Wed, Jan 3 2007 4:17 pm
Subject: Re: "Size Balanced Tree" - more efficient than any known algorithm?
Print | Individual message | Show original | Report this message | Find messages by this author
Sorry. I don't have that book. What is it about?
On Jan 2, 9:48 pm, reing...@emr.cs.iit.edu (Edward M. Reingold) wrote:
- Show quoted text -
Edward M. Reingold
View profile
Hide options Jan 3 2007, 10:44 pm
Newsgroups: comp.theory
From: reing...@emr.cs.iit.edu (Edward M. Reingold)
Date: 03 Jan 2007 08:44:24 -0600
Local: Wed, Jan 3 2007 10:44 pm
Subject: Re: "Size Balanced Tree" - more efficient than any known algorithm?
Print | Individual message | Show original | Report this message | Find messages by this author
>>>>> "CQ" == Chen Qifeng <344368...@qq.com> writes:
CQ> Sorry. I don't have that book. What is it about?
CQ> On Jan 2, 9:48 pm, reing...@emr.cs.iit.edu (Edward M. Reingold) wrote:
>> >>>>> "CQ" == Chen Qifeng <344368...@qq.com> writes:See the top of page
>> 476 in vol. 3 of Knuth, 2nd ed.
It is THE standard for this type of data structure result; it is in most
science/engineering libraries around the world.
--
Professor Edward M. Reingold Email: reing...@iit.edu
Department of Computer Science Voice: (312) 567-3309
Illinois Institute of Technology Assistant: (312) 567-5152
Stuart Building Fax: (312) 567-5067
10 West 31st Street, Suite 236
Chicago, IL 60616-3729 U.S.A.
A. L.
View profile
Hide options Jan 3 2007, 10:52 pm
Newsgroups: comp.theory
From: A.L. <alewa...@fala2005.com>
Date: Wed, 03 Jan 2007 08:52:39 -0600
Local: Wed, Jan 3 2007 10:52 pm
Subject: Re: "Size Balanced Tree" - more efficient than any known algorithm?
Print | Individual message | Show original | Report this message | Find messages by this author
On 03 Jan 2007 08:44:24 -0600, reing...@emr.cs.iit.edu (Edward M.
Reingold) wrote:
>>>>>> "CQ" == Chen Qifeng <344368...@qq.com> writes:
> CQ> Sorry. I don't have that book. What is it about?
> CQ> On Jan 2, 9:48 pm, reing...@emr.cs.iit.edu (Edward M. Reingold) wrote:
> >> >>>>> "CQ" == Chen Qifeng <344368...@qq.com> writes:See the top of page
> >> 476 in vol. 3 of Knuth, 2nd ed.
>It is THE standard for this type of data structure result; it is in most
>science/engineering libraries around the world.
Maybe excluding China...
A.L.
================================================================================
http://www.zsjz.com/noi/index.asp?BoardID=2&Page=4
http://topic.zsedu.net/jcxz/001.html
为了进一步加强我市青少年思想政治教育，推进公民道德建设深入持久开展，在全市广大青少年中树立榜样，引导他们用真情感动他人，用毅力激励他人，用行动影响他人，展示21世纪我市中小学生的聪明才智和青春风采，在全市中小学生中掀起学习先进的新高潮。为此，市教育局面向全市中小学生开展2008年“杰出中山学子”评选活动， 经过推荐申报，评委评选，现将初选入围的候选人事迹公示，接受全市人民的投票（投票结果占总分的50%），总成绩前十名的优秀学生将成为2008年“杰出中山学子”。
为理想而拼博
——中山纪念中学陈启峰同学事迹介绍
※※如不能正常收看本栏目视频的用户，请先下载安装Adobe Flash Player V9.0
01 中山纪念中学 陈启峰
中山纪念中学培养了众多品学兼优的学生，陈启峰同学是他们中的杰出代表，通过刻苦的训练，他成为广东省首位取得国际信息学奥赛金牌的中学生。走近他，我们看到了一个为理想而奋力拼搏的新世纪少年；走近他，我们将发现冠军光环背后的付出并不仅仅只有汗水。
四年磨一剑 霜刃今日试
陈启峰同学在信息学竞赛领域中所取得的成绩非常突出。他在学习信息学的四年时间里，共获得了三枚全国比赛的金牌和一枚国际奥赛的金牌。
2003年陈启峰同学开始接受信息学训练，当时他正在纪念中学三鑫双语学校读初中，初一暑假时参加了中山纪念中学信息学选拔考试并被录取，此后就在三鑫双语学校接受一年半的信息学训练。2005年，读初三的陈启峰在广东省省队选拔赛中以第一名的成绩入选省队，并在全国决赛中取得金牌。这是当时全国唯一获得金牌的初中选手，也是广东省第一个获得全国金牌的初中选手。
成功的道路也并不是一帆风顺，陈启峰被选拔到国家集训队，并被清华大学免试保送录取，但因微弱劣势在国家队选拔赛中落选。2006年就读高一时他东山再起，在选拔赛中发挥稳定，又一次获得全国金牌，最终以全国第二名的出色成绩轻松入选国家队，接着在2007年7月举行的全国比赛中再次获得金牌，实现了“三连冠”。
2007年8月13日，陈启峰与国家队另外三名选手一起出征克罗地亚，参加本届IOI2007国际信息学奥赛，陈启峰取得全世界第8名的优异成绩，为中山市、为广东省、为中国夺得一枚沉甸甸的金牌。
陈启峰是中山市第一个入选五大学科奥赛中国国家队的学生，他取得的这枚金牌也是中山学子代表五大学科奥赛中国国家队夺得的第一枚国际金牌，而且为广东省填补了国际信息学奥赛金牌的空白。
天赋加勤奋等于成功
学习四年时间夺得三枚国家级金牌，一枚国际金牌，陈启峰取得的成绩并不仅因为在信息学方面有很高的天赋，更多的是他后天的勤奋刻苦以及政府、学校以及各级教练的支持。
陈启峰谦虚地说，能取得今日的成绩，一方面是因为自己对信息学有着浓厚的兴趣，陶醉在她所呈现的美丽画卷之中，此外自己比较努力，懂得运用高效的学习方法，并不断对学习过程进行反思。陈启峰还说即使自己有天赋也未必会成功，成绩的取得更多是因为学校给他提供了一个很好的训练环境，老师给了他的更多地关怀和指导。
陈启峰的教练介绍说，在训练过程中，陈启峰曾创下四个月完成400多道题的纪录！“这对一般的学生来说是非常难做到的，这要靠天赋，还要有开阔视野，只有这样，才有可能与世界顶尖高手交流。”学习信息学要达到国家级的水平很辛苦，而陈启峰正具备能吃苦的精神，在训练中，普通学生 6年也未必能完成400道题，他抓紧课余时间孜孜以求，仅用4个月就做完了，创下了信息学领域里的一个奇迹。
“有志者，事竟成，百二秦川终归楚；苦心人，天不负，三千越甲可吞吴。”这是陈启峰同学的座右铭，他相信只要不断努力，就终有一天成功。他在学习中不怕辛苦，勤学好问，在遇到困难时从不退缩，他通过网络向国家队教练、队友虚心请教；而且在实践中善于思考并总结经验，形成一套科学的学习方法，他说掌握学习方法要比单纯的学习知识更为重要。
一枚枚金牌的获得，充分体现了陈启峰同学个人的顽强拼搏精神、攻坚破难的勇气和永不言败的意志与品质，为今日学子树立了很好的榜样和模范作用，也为教育工作者如何培养德才兼备的高素质人才提供了经验。
综合素质全面发展
陈启峰不仅在信息学方面表现出色，在学校他更是一个综合素质全面发展的优秀学生。例如，本次比赛取得国际金牌，从克罗地亚回到北京时，在北京的庆功会上，中国4名选手只有他能流利地发言，并在发言中感谢祖国、政府以及学校、老师对他的栽培，这份成绩并不属于他一个人，由衷的感激一路上给过他帮助的老师和领导。
理想是成功的源泉，陈启峰同学的成功，与他从小志存高远，有远大的理想抱负，有为国争光的志向是分不开的。关于他的理想，他说他要创造出比Windows还要强大的操作系统、比Google还要快速的搜索引擎、比Yahoo还要方便的网站，然后把它们奉献给最可爱的人民。在这个竞争激烈的信息化时代，他决心要为实现理想做一个坚持不懈、永攀高峰的人。
陈启峰喜欢学习，却不是信息学的“书呆子”，他平日喜欢运动，兴趣广泛，喜欢看电影，喜欢看书，如名人传记、演讲、哲学、历史等。小学时他还拿过“全国作文竞赛二等奖”，“我想这可能是我能够拿奖牌的一个重要因素，因为信息学需要海量的知识。”陈启峰说。
而且，他还乐于助人，善于处理好与同学之间关系。每年学校组织义卖，并把义卖的钱捐给学校的希望工程部，是纪中一直以来扶贫助困的方式之一。每次学校组织该项活动，陈启峰都很积极，最近一次活动中，他上网采购了一批学生们喜爱的小饰品进行义卖，短短几天就赚了3000多元，他把这些钱都捐给了学校的希望工程部。2007年9月20日南方日报《中山观察》CO1版题为《救救小志轩！》报道发出以后，在社会上引起强烈反响。陈启峰在征得父母同意的情况下主动捐了1万块钱给纪中希望工程部，并希望希望工程部能够从1万块钱中抽出部分钱捐给小志轩。
为锻炼自己的组织能力，陈启峰同学有意识地参加各种各样的活动。2007年的十一黄金周，他协助清北学堂举办一次奥赛培训班活动，在北京担任了5天的助教，负责经验讲课、组织学生讨论、总结补充等任务。为锻炼自己的写作演讲能力，从初中起，他就是个演讲课上最活跃的学生。每次在演讲课上他总是以富有逻辑、结构清晰的演说征服台下的听众。他还购买了大量关于演讲的书籍，其中最喜欢的就是美国的原版教材《The Art Of Public Speaking》。到了高中，由于竞赛成绩突出，陈启峰同学还多次在学校、颁奖会、信息学研讨会上发言，做到实践与理论相结合，并发表过一篇名为《Size Balanced Tree》的英文论文，得到国内外多间大学教授的赞赏。
在各种各样的信息学比赛中，他认识了很多不同国籍的朋友，当这些朋友遇到难题时，都很喜欢请教陈启峰，陈启峰每次都耐心地帮助别人。在本次参加国际比赛之前，陈启峰在北京买了许多2008年北京奥运的纪念品，在比赛的时候送给其他国家的参赛选手，热心宣传2008北京奥运，其他国家的选手也回赠给他许多小礼物，他把这些小礼物收藏了起来。
在陈启峰的身上，我们看到了一个高素质中学生的良好品德，一个阳光少年健康、乐观、昂扬向上的精神，他是新世纪学子的骄傲，是广大学生学习的楷模。
[解决办法]
SBT比红黑树效率高吗？
[解决办法]
个人认为在一般情况下，红黑树是确定性平衡树中效率最高的,从而也是迄今为止最好的确定性平衡树，比AVL要好。没仔细研究过SBT，印象中SBT好像只是通过旋转改变树的weight，是不是因为这样做代码写起来简单，适应于竞赛的环境？