2011-07-09 21:37:55Morris
[2011/7/9] 鏈結奮鬥
第一天 寫了 HASH
第二天 寫了 Splay Tree
第三天 寫了 AVL Tree
每一個都寫了一天，有點逼近瘋了，bug 都抓好久
總覺得這幾天都是蟲蟲危機
今天寫則是 AVL Tree，以前寫過，但是只有插入的功能
這次用鏈結寫且增加刪除功能，發生了一些奇怪問題
只好生測資來測資看有沒有 TLE， N = 1000，我根本抓不出來
只好生 N = 100，開始來摸彩，玩了 2 個小時，我終於中獎了
而且也用了 "哨兵" 去做處理 NIL，但願暫時不會有問題
<引用>
哨兵（sentinel）是一个哑对象，可以简化边界条件。是一个附加的链表节点，该节点作为第一个
节点，但是它其实并不存储任何东西，只是为了操作的方 便而引入的。因此，如果一个链表有哨兵节
点的话，那么线性表的第一个元素应该是链表的第二个节点（个位置的时候，需要考虑该位置上原来的
节点并没有前驱节 点；而如果有哨兵节点的话， 线性表的每个位置的节点都有前驱节点，因此可以统
一处理。（注意：哨兵节点根本不出现在线性表中，所以虽然它没有前驱，但是前面的那句话并不矛
盾）
簡單的說，可以減少一些 if 判斷會不會有"NULL->?"的可能，可以讓程式碼簡潔點
奮鬥那麼久，真是累人，一題用了三種寫法
可惡的 example 居然叫我用 "紅黑樹" 寫，這樣下去一定會鬧人命的 ...
下一篇：[2011/7/11] 退場