望尽天涯路

明早就要出发去旧金山参观Google总部了，虽然被Google北京狠狠的拒了，我似乎依然是Google的fans。
这次Code Jam Final，Google显得有些小气，不知道是不是受美国经济危机的影响。先是要求从机场到酒店如果坐出租车的话，必须要跟其他参赛者拼车。最后干脆要求在公共交通运行的时间段里必须搭乘公共交通，BART,shuttle啥的，除非半夜或凌晨到的才能叫出租车，而且依然要拼车！我了解了一下，美国的出租车不像国内满大街跑招手就停，还得打电话预约。说起来，我要是叫出租车的话得在机场先换硬币，然后打投币电话，这么麻烦还不如搭地铁然后走一会儿。
今天看了下地图，发现唐人街(Chinatown) 离住的酒店很近，步行几个block就能到了。我9点到机场，下午3点才能check-in，中间这段时间正好可以去逛逛。午饭还得自己解决，这对于英语听说极差的我是个挑战 ，Google会报销最高25刀的餐费，争取正好吃到这个数目:) 还有个什么联合广场(Union Square Park)离酒店更近，也可以顺便看看。金门大桥也不是很远，不过步行是不行的了，估计是没时间看了。时间安排太紧了，下午6点welcome reception，大快朵颐的好机会。还记得北京local final的时候，以为welcome reception最多提供点饮料水果啥的不能当晚饭的，于是就跟同学去酒店附近吃火锅了，完了回来看见招待会上食物相当丰富，甜点，烤肉，烤鹌鹑一应俱全啊，看得我直流口水，可惜火锅吃得太饱腹中再无容物之处，只能吃了点水果忿忿的回房看电视了。第二天白天在Mountain View的Google总部，离酒店五六十公里，按日程安排早上6点半就得起来，然后又是welcome，接着是赛前准备，比赛，午餐，下午参观Google，Tech talk，回酒店晚上颁奖，第二天一早又得闪人。估计我还没能从北京时间调整到旧金山时间就已经又身在北京了。从七月份开始的五轮比赛，持续一个月的签证申请，上海美国使馆楼里楼外4个小时的排队就换来旧金山的短短48小时！不过作为Google的fans能参观Google总部也满足了，况且还有比赛奖金拿:)

BBS算法版上时不时的会有人问"一个整数集合，划分成两部分，使得两部分的和的差最小"之类的问题，而且说是面试题目。我想这样的面试官也太不厚道，要是不知道NP理论的面试者岂不是要想算法想得很郁闷。没想到我也在面试中遭遇NP-Hard问题了，不过这个问题没那么裸。
说一个测试数据集U，每次可以任取一个U的子集作为一次O(1)时间测试的输入，测试的结果可能fail或者不fail。测试的结果总是相容的，即子集A是子集B的子集，如果A测试fail那么B测试一定也fail。问题是找到一个最小的子集使得测试fail掉。如果最小的子集只有1个元素，二分就行了；两个元素的情况也可以二分。最小集元素多了就不好办了。我当时想P算法想了好一会，最后觉得应该是NP-Hard的，于是跟面试官说了，然后被要求给个证明。当时把子集和问题归结到这个问题，归结的过程很简单。面试结束后发现，我给的那个reduction错得很离谱，近乎扯淡，面试官当时竟然没发现，而且貌似还对我的证明很赞许。下来又想了下，问题确实是NP-Hard的，证明也不难，可以把Set Cover归结到这个问题。对一个Set Cover问题实例(U, {S1,S2,...,Sn})，构造测试程序，对于输入子集A={ S', S'', ...}，测试返回fail当且仅当A覆盖全集U。显然这个测试可以在多项式时间内完成，而且Set Cover的最小覆盖集正好对应{S1,S2,...,Sn}的最小fail子集。

C++ Tips

1. Usage of "const"
   char greeting[]="Hello";
   const char *p=greeting; //const data
   char * const p=greeting; //const pointer
   const char* const p=greeting; //const pointer and data
   void fun() const; // Declaration of constant member function
   
2. When a derived class of object is deleted through a pointer to a base class with
   a non-virtual destructor, results are undefined. So a class containing any virtual
   function should has a virtual destructor.
   A bad example.
   class base
   {
       //public:
           //virtual ~base(){};
   };
   class derive:public base
   {
       int *a;
       public:
           derive(){a=new int[10];};
           ~derive(){delete [] a;cout<<"deleted"<<endl;};
   };
   int main()
   {
       base *p=new derive();
       delete p;  // ~derive would never be called.
       return 0;
   }
   
3. operator=
   class Widget {private: Bitmap *pb;}
   Widget& Widget::operator=(const Widget& rhs)
   {
       delete pb;
       pb=new Bitmap(*rhs.pb);
       return *this;
   }
   Widget obj;
   obj=obj;  //  Oops! runtime error
4. std::auto_ptr<>;
   void fun()
   {
       std::auto_ptr<myclass> pp(new myclass());
       ...
   }
   When fun() exits, the object will be deleted automatically.
   Another better choice is std::tr1::shared_ptr<>
5. Type cast
   
   • const_cast<T>():  Remove const property.
     const char str[]="aaa";
     char *p=str;  // Can't compile
     char *p=const_cast<char*>(str);
     
   • dynamic_cast<T>(): Perform safe downcasting, i.e. casta base class type into derived class type.
     It will check whether the base object is actually a derived object in run time, it not the cast will fail in run time.
     class base{public: virtual void f(){};};
     class derived: public base{public: void print(){puts("derived");};};
     int main()
     {
         derived obj;
         base *p=&obj;
         dynamic_cast<derived*>(p)->print();
         return 0;
     }
     The base class must be polymorphic.
   • reinterpret_cast<T>(): low-level casts.
     pointer --> int
   • static_cast<T>(): force implicit conversions. e.g. non-const object
     to const object, int to double. Perform reverse of many such conversions.
     It can't assure the correct cast like dynamic_cast<>.
     e.g. void* to typed*, pointer-to-base to pointer-to-derived. It can cast const to non-const.
     
6. Pointer to class member function
   double      \\return type
   ( Point::*  \\class name
     pmf )       \\name of pointer
    ();             \\argument list
   pmf can point to a virtual function, and the polymorphism still holds.
7. class base
   {
       public:
           virtual void fun1()=0;
           virtual void fun2()=0;
           void fun3();
   };
   void base::fun3(){};
   void (base::* p1)()=&base::fun1;
   void (base::* p2)()=&base::fun2;
   void (base::* p3)()=&base::fun3;
   What are values of p1,p2, and p3?
   p1=1, p2=5, p3=some memory address. In fact, p1 and p2 are indexes of the virtual table of
   class base, which correspond to virtual two functions.
8. Difference between reference and pointer.
   Reference should be initialized in its definition.
   The object referenced to by a reference can't be changed.
   Reference would never be null.
9. Virtual functions, Overload, Override and Hide.
   class base
   {
       public:
           virtual void f(int);
           virtual void f(double);
           virtual void g(int i=10);
   };
   class derived: public base
   {
       public:
           void f(complex<double>);
           void g(int i=20);
   };
   int main()
   {
       base b;
       derived d;
       base *pb=new derived;
       b.f(1.0);  \\ base::f(double);
       d.f(1.0);   \\ derived::f(complex<double>)
                       \\derived::f is a hide instead of overload.
                        \\ Need declaration using base::f(int/double) to call f in base.
                         \\ void base::f(double) will lead to override.
       pb->f(1.0);  \\ base::f(double). It is not overridden in derived.
       b.g();        \\ base::g(10).
       d.g();        \\derived::g(20).
       pb->g();    \\ derived::g(10).  Polymorphism.
       delete pb;   \\ ~derived() would never be called. Error!
       return 0;
   }
   
   

上周日去南京参加了MicroXXX (XXX!=soft)公司的面试。一早乘坐不太和谐的"和谐号"到南京火车站，之所以不太和谐是因为觉得票价稍贵:)不过的确够快，一百六十多公里只要一个小时。从合肥到南京，就像是从乡镇到城市，单是两个火车站就有强烈的对比。妙的是南京火车站就在玄武湖旁边，站前广场就连着湖岸，人们坐在湖边吹着风，早晨淡淡的阳光洒在宽阔的湖面上，感觉很是惬意。立马决定绕湖走一圈，反正离面试还早。一路走一路看，玄武湖一部分被明城墙围起来，湖边散布些亭台和小树林，整个被称作玄武湖公园。走了不到四分之一，接到电话问能不能提前去面试，于是从高高的玄武门出公园去面试地点。
面试非常囧，两个中国人非要整洋鬼子的话交流，不知是我英语听力实在太差还是面试官的发音确实有点特别，几乎每个问题我都会要求重复其中的几个关键词，似乎有个问题中的两个词重复了四遍我才听明白，弄得面试官都有些不耐烦了。这次面试结果是挂了，这是后话，我终于栽在自己糟糕的英语听力跟口语了。
面试结束后离返程还有6个小时，决定去看一处名胜，作为"六朝金粉地，东南形胜处"的南京的名胜可多得去了。随便找了个公交站牌看了看，附近有三个地方可去，雨花台，明孝陵和夫子庙。说到南京雨花台就想到《儒林外史》里面的一段趣文。日色已经西斜，只见两个挑粪桶的，挑了两担空桶。歇在山上。这一个拍那一个肩头道："兄弟，今日的货已经卖完了，我和你到永宁泉吃一壶水，回来再到雨花台看看落照。"杜慎卿笑道："真乃菜佣酒保都有六朝烟水气，一点也不差！"。
而明孝陵就是咱英明神武的老祖宗的陵墓，都说同姓的五百年前是一家，算来大明朝正是五六百年前，说不定就是咱的老祖宗也未可知啊:)。可惜了洪武帝一世英明，以为在自己的苦心经营下自家的江山固若金汤能传承万代--其实每个朝代的开国皇帝都这么天真的--子孙们却没几个争气的，有窝里斗的，有几十年不上朝的，有整天做木工的，还有烧丹炼汞的，最后落得个非但亡国竟是亡天下，亡了汉人的天下，让中国人顶着个猪尾巴卑躬屈膝的做了两百多年的奴才。
最后还是决定去夫子庙拜拜孔老夫子，求他老人家赐予我关于人生的智慧。
没想到的是，在会子庙我并没有见到他老人家，而是迷失在成片的店铺和如织的人流中。原来夫子庙竟是一个仿古风格的商业步行街，连椽的店铺，满眼的大字招牌还有嘈杂的人群。最后终于发现了藏在其中的江南贡历史陈列馆，馆前有几尊铜像，有唐伯虎，林则徐，吴承恩和吴敬梓。唐伯虎是苏州才子，不过是在江南贡院中的解元。林则徐则做过这里的主考。吴承恩是率考不中，最后一把年纪才中了进士。说起来吴敬梓跟江南贡院没啥关系，这位老先生平生最恶科举，长期寓居秦淮，写下了巨著《儒林外史》。花二十块钱进陈列馆看了下，无非是些复印版的资料图片，介绍一些跟江南贡院有些关联的知名人物。离开夫子庙前吃了所谓"南京一绝"的鸭血粉丝汤，这个招牌还算谦虚的，还有打"中华一绝"大字招牌的。跟一般的小吃相比也没啥特别的，味道相当的一般，不明白何以成为"一绝"的。

Low(x): ((x^(x-1))&x) is well-known.
How about calculate sum[i]= Sum{ A[j] |  j is a  subset  of  i}?
The common tricks don't work.
One trick is to calculate partSum[i][b]= partSum[i][b+1] + ((1<<b)&i)?partSum[i^(1<<b)][b+1]:0.
Here partSum[i][b] denotes sum of A[k] such that the b low bits of k  and i are the same, and
 the high bits from bit b of k is a subset of that of i.
The time complexity is n2^n. Is there faster method?

前两天收到了Topcoder寄来的一个大信封，信封上有important字样。原来是SRM比赛奖金纳税的return form，有3个一样的copy，分别标记为copy B,C和D。白纸黑字邪写得明白，我总共纳税122.10美元，税率百分之三十。老外做事还真负责，巴巴的跨越重洋寄三张没用的废纸给我。这下做了回有凭有据的米国纳税人，不过天知道我交的税金是不是给"美帝"拿去买了炮弹扔在伊拉克的土地上呢？

3月底的时候给Google的hr发了封邮件表达了一下做暑期return intern的意愿，等了一个星期都没得到回复。然后又给另一位hr发了同样的邮件，一个星期后收到了第三位hr的回复。委婉的告知，Google对return internship把关很严(strict guidance)，如果在第一次实习的feedback不够好是不能获得return internship的机会的。然后说因为我的"feedback is not positive enough"，所以这次不能给我return internship的机会。我又发邮件问这个feedback是否会影响我将来申请full time，并请求告知feedback的细节。回信自然说feedback的细节不能告知，还说给一年的时间去improve然后再申请，包括full time。
看来是被ban掉一年的申请资格了，nnd！之前还以为暑期实习就是感受公司文化，吃零食，玩桌上足球，PS游戏和健身器材，反正也没人盯着做事。估计公司对实习生的评估还是比较认真严格，只是当时没注意。想起来还在公司打印了大量的论文和书，应该有四五百页吧，当时觉得不打白不打，回校的时候装了一整挎包，背的我好累。这些肯定都有打印记录，Google应该不至于小气到因为我滥用打印机而ban掉我，但至少也侧面说明我没干啥正事。不过更甚于我的还有人在，当时在打印机的job队列里看到有人打印红楼梦!!!!

今天中午被住在宿舍楼下的流浪猫咬了。我只是强摸了它后脑一下，没想到它这么狠，以迅雷不及掩耳盗铃之势转头就是一口咬在我的右手拇指关节处，枉我这两个星期来喂了它这么多火腿肠吃:(
伤口很小，像针扎了一小下，当时挤了一点血出来。后来再网上搜了下被猫咬怎么处理，最后出于对狂犬病的恐惧决定去下午去打疫苗，于是麻烦开始了。
先去了校医院，挂号的叫去安医附院，匆忙赶到安医，挂号的(当然跟前面的不是同一人:)又叫去传染病医院，还好传染病医院也在附近，不过还是冒雨走了好一会。顺利挂号，医生开了疫苗和西药，西药是防"猫爪病"的，其实就是抗生素，当时问医生" 猫爪病"什么症状，医生轻描淡写的说道，淋巴结肿大溃烂，我不由得心中打了个寒战，医生接着又补了一句，死不了也治不好。然后被医生科普了一下，被猫咬的人群中狂犬病发病的比例要高于被狗咬的比例，而被猫咬的人要比被狗咬的人少很多，所以造成人们误解被猫咬不如被狗咬危险。听得我直庆幸自己做了"英明"的决定。我的小伤口的所谓"暴露程度"为"III度"，即最危险级别，而"I度暴露"是完好皮肤被舔！最后医生送忠告， 远离动物，还不忘感叹一下，现在很多以前没有的病都是从动物传染来的。
总共要打五次，第一次两针，以后四次每次一针，整个过程要持续一个月，期间还要忌酒，茶，咖啡因，剧烈运动什么的。更麻烦的是，全部针打完后还得去化验是否产生抗体了，如果没有还得再打三针。打针的时候问护士，如果完了还是没产生抗体怎么办，护士有些无语，说"不可能，那样的人极少"。第一次胳膊和屁股各一针，屁股那一针好疼，医生说是正常的，还说几个小时后还要发烧，叫吃开的那两边退烧药，汗。因为半边屁股疼我在注射室外坐了好一会才走，开药的医生见到我问怎么还没走，faint！
疫苗费用不菲，第一针加西药150多，以后每针55元。不过据说这个是在保险覆盖范围内，到时候找校医院报百分之八十。
这下玩猫玩大发了......

在网上闲逛时发现一个超帅的Pick定理的证明。
http://www.math.ethz.ch/~blatter/Pick.pdf
英文不太好，看了老半天才看懂:(
把整个平面想象成一块大铁板，假设在0时刻在平面的每个格点上都有一个单位热量的热源并均匀向各个方向扩散，那么最终整个平面会达到热量均衡，于是简单格点多边形的面积就等于其内部的热量总和。考虑多边形的任意一条边，整个平面是以这条边的中点中心对称的，于是穿过这条边进入多边形内部的热量之和为0，所以多边形内部的热量全部来自于内部格点和边界格点。前者正好为内部格点数，而后者中每个点的热量只有一部分流向多边形内部且其数量等于对应属于多边形角度除以2PI，再利用简单多边形内角和就可以得到Pick定理了。

ivan_metelsky ，白俄罗斯的，Topcoder的比赛里常见的，通常作为problem writer or tester出现，我出题的两次都有他作为tester之一。以前一直以为他跟我一样是普通会员，今天在Google Talk里聊了一下才知道他原来是TopCoder的full time employee，但是并不在美国的TC公司里上班，而是通过Internet在白俄罗斯的家里工作，而且ms在他还在大学里就开始给TopCoder工作了。工作的内容就是负责测试TopCoder算法比赛的题目和出题。这样的工作真是太酷了！

---

me: Hi. May I ask you some questions?

今天上午第一次作为problem writer参与了一次SRM，非常好玩。用writer特权帐号登录进Arena后，惊奇的发现竟然能看到所有人的悄悄话:)当时就看到有人在用中文私聊TC挣钱的事，都到6位数了...(并非偷看哦:)。
writer在比赛中的责任就是呆在Admin room回答coder的关于题目的提问。不过提问的并不多而且不止我一人回答提问，所以主要还是观战。看着一群大牛们为自己的题目在想啊写啊的，非常有成就感。writer作为admin之一，还可以在比赛中看任何人提交和编译的代码。500分的题目被Petr以480+的高分早早攻破，ACrush紧随其后。1000分可就不那么简单了，大部分的高rating coder都被挡住了。赛前就有题目的tester估计应该只有4，5个人做得出来，那个tester说他想了2个多小时才做出来。不过还是有几个人较早的提交了1000分，打开看了发现大都是分解大数的冒险做法，心中暗喜。又过了一段时间，发现SnapDragon提交了一个跟我的reference solution几乎一模一样的程序。真是太佩服了，这么短的时间内能想到做法，数学功底应该是相当的好。
最后，Petr和ACrush都没能在这道题得到较高的提交分数，貌似Petr还resubmit了，更糟的是ACrush最终还fail掉了:( SnapDragon虽然提交了一个优雅的1000分solution，不过还是没能win，因为还有人更早的提交了正确的1000分，TC真是卧虎藏龙啊。比赛结束后，SnapDragon跟我悄悄话，称赞我的1000分题目是一个cool problem。
我在回答问题的时候还犯了一个错误。当时正在跟另一个admin用wisper方式聊1000分题目的做法，突然有人提问，
于是我把消息发送方式改成reply那个人的消息，回答完后竟然忘了把消息发送方式切换回来，就给那个admin发了一句
提示解题的消息。被其他admin发现后，他们赶紧讨论如何处理，其中一个admin还说我透露的是一个significant的消息。我当时觉得事情似乎大条了，可能要取消比赛。不过最后还是算了，貌似admin发现收到消息的人并没有因为这个消息就顺利的做出1000分的题目，而房间里其他人虽然也能看到消息，但是大家都忙着coding，谁会去注意满屏移动的乱七八糟的各种消息呢。

晚上出去吃饭的时候，就开始下小雪籽了。
一路撑着伞，呯呯砰砰的，回来时伞一点没湿。
现在外面真飘雪了，阳台已经开始积雪了。
长这么大第二次看到下雪，而且第一次还是十来年前小学四年级的时候。
期待明晨的银装素裹......

---

早起看雪，积得不多，薄薄的一层，像是石灰。
从窗口第一眼看到积雪时，脑子想到的竟然是红楼梦里的词句，
”好一似食尽鸟投林，落了片白茫茫大地真干净”......

---

中午在校园逛了逛，“梅园”里的腊梅还真开着，不过没什么香气，不曾想还做了回“踏雪寻梅”的雅事，
只是离“琉璃世界白雪红梅”的意境还差得远。
然后去足球场玩，场上竟然还有猛男穿着短裤踢球。
生平头一次玩滚雪球，不过耐心有限，草草收场。

A is a nXm matrix. Alice has a choice of n so-called pure strategies and Bob has a choice of
m pure strategy. If Alice picks strategy i and Bob picks strategy j, the payoff is Aij, meaning
Aij dollars are transferred from Alice to Bob. Thus, Alice want to pick a strategy to minimize
the payoff while Bob wants a strategy to maximize the payoff. The matrix A is called the payoff
matrix. It's well known that to play the game well, you need to use a mixed strategy--a random
choice from among pure strategies. A mixed strategy is just a particular probability distribution
over pure strategies. Say Alice's maxed strategy is vector X and Bob's is Y, then Alice and Bob
try to solve two problems below to find their best X and Y, respectively.
Min{Max{XAY|Y}|X}   s.t. Sigma{X}=Sigma{Y}=1  X>=0 Y>=0      (1)
Max{Min{XAY|X}|Y}   s.t. Sigma{X}=Sigma{Y}=1  X>=0 Y>=0      (2)
For (1), whatever X Alice picks, Bob can always pick a Y such that (XA)Y=Max{element of XA}.
So we can convert (1) to a linear programming
Minimize Z s.t. XA<=Z Sigma{X}=1 X>=0 (A)
Likewise,  (2) can be converted to 
Maximize Z s.t. AY>=Z Sigma{Y}=1 Y>=0 (B)
It's surprising that (A) and (B) are duality linear programming of each other, so they are equal.
It means Alice and Bob can't improve their payoff even if he/she know the other's strategy. It's
called they are in Nash Equilibrium.

一年真是过得太快了，到明天按虚岁算我又长一岁了，nnd！
我理解的虚岁就是当前年份减去出生年份，不过有人说是出生就一岁，还有人说出生算十个月大。
昨晚，一个广西室友说，壮族人一出生就算三岁大，因为天，地，父母各给一岁。
还好，汉族人没这个传统，不然按"天地君亲师"，生下来就5岁啦:)

A MST is obviously a BST. In fact, a simply linear algorithm exists for BST.
It appears in CLRS problem  23-3, but I didn't come up with it and just Google it. I stupid!!!
It looks like a divide and conquer algorithm.
Find the median of all edge weights Em.
Using a DFS to check whether there exists a spanning tree with edge  weights not greater than Em.
If yes, remove all edges of weight greater than Em. Repeat.
If no, contract  all edges  of weight not greater than Em and get a smaller graph. Repeat.
Obviously, each edge is processed one time. 

A segment tree T stores a set S of n intervals on the line. A standard segment tree is a balanced binary search tree over the 2n endpoints of S that are stored at the leavesof T . We use the same notation for both a leaf and the point that it contains. We associate an interval denoted
by range(v) with each node v in T . If v is a leaf then range(v) is the interval [v, v]. If v is an internal node, where w is the leftmost leaf in the subtree rooted by v, and z is the rightmost leaf in the subtree rooted by v, then range(v) = [w, z]. We associate with each node v in T a set S(v) consisting of all segments s in S containing range(v) but not containing range(p(v)). Each node v in T holds a secondary data structure, representing the set S(v).
An interval tree is defined similarly. The difference is that in an interval tree an interval s = (xs, xe) is in S(v) if and only if v is the lowest common ancestor of xs and xe in T . It follows that a segment tree required O(n log n) space and an interval tree requires O(n) space.
------From "Optimal dynamic vertical ray shooting in rectilinear planar subdivisions" SODA07

Sometime, we need maintain a segment tree, which supports querying a minimal of a specified interval and adding a constant to a specified interval. It's a common problem in programming contest. Usually, we maintain the interval segment tree by a folk technique called "deferred operation" or "contract subtree". Let's see how Tarjan dealt with this problem in his paper on Dynamic Tree.
Define
dvalue[v]=value[v]-value[parent[v]] if v is not root, otherwise value[v] if v is root.
dmin[v]=min[v]-min[parent[v]] if v is not root, otherwise min[v] if v is root.
It's easy to maintain the segment tree of dvalue[] and dmin[].
Moreover, it's elegant!  

How to solve a difference constraints system subjected to that a subset (not necessary all)
of unknowns must be integral? 

上周实现了一下RB Tree，其实并不是想象中的那么麻烦（split和join暂缺，主要是模板类结构没规划好，
导致这两个操作写起来别扭）。
另外似乎有人说CLRS上的代码在处理哨兵节点上有错，不过句我仔细分析和实践，代码是对的。
顺便orz一下它的发明者R.Bayer(发现者？奇怪的是，paper中大都说xx discover了xx算法)。
平衡树的始祖应该是AVL树，三个俄国人搞出来的。
跟AVL相比BRTree的优势在于：

1. 每个节点只需要一个bit的用于平衡的额外空间，而AVL需要记录高度。
2. 每次作Fixup的时候，RBTree的Rotate次数是O(1)的，而AVL是O(lgN)的。
3. 虽然RBTree作Fixup时Recolor的操作是O(lgN)的，但是其均摊复杂度确是O(1)的！这个意味着，N个插入删除操作的代价是O(N)的。（参见CLRS习题）

不过，ms AVL树更平衡，因为兄弟子树高度差不超过1，而RBTree一棵子树的实际高度可能是其兄弟子树的2倍。
总的来说，RBTree效率肯定更高。难怪，本科看Linux内核的虚存管理时发现早一点的内核版本用的AVL树，后来就改成RBTree了。

给Topcoder写的题目终于被采用了，不过是TCHS SRM 47，中学生玩的
不管怎样，希望是个好的开始吧，其实我的题目几乎都不是很novel和interesting。
期待一次真正的SRM。