要找工作了，終于覺得是時候總結一下數據結構了（ps: 對于數組，鏈表這樣簡單常用的結構就不總結了，此文會持續更新），總結有助于更好地思考。
1. 位圖
位圖的威力可以在＜編程珠璣＞的開頭就體會到。另外在
Find an integer not among four billion given ones中的運用也很精彩。
2. 堆
在＜編程珠璣＞里重點運用了該結構，直接導致我以后經常想到并使用該結構。
不得不說，它真的很有用，如：找N個數中最大／最小的k個數。
實現優先級隊列時也有用。
3. 樹
二叉搜索樹：是一個很容易就能想到的結構，只要讓一棵二叉樹滿足以下一個特性就可以了：對于任一結點N，其左子樹結點left滿足key(x) <= key(N)，其右子樹結點right滿足key(y) >= key(N)，其優點是操作簡單，缺點是插入，刪除結點的復雜度高，為O(N)
二叉搜索樹復雜度高的原因為：樹的高度不確定/不穩定，有可能為n，所以問題的關鍵是：如何控制樹的高度
很多人靈機一動:產生了一系列平衡二叉樹，如：AVL樹，Red-Black樹，
Treap 也產生了很多平衡二叉樹的變種，如：
Weight balanced tree，k-neighbor tree等
Skip List 也是平衡二叉樹之外的另一種選擇
Trie樹 用來存儲一個字典，然后用來查找某個字符串還是很方便的（A trie can be seen as a deterministic finite automaton.） 另外可以看看
Suffix_tree后綴樹。
4. hash
hash的兩個關鍵點在于：a. hash桶大小的設定（一般為一個素數） b. 沖突處理機制，如可以用一個鏈表處理hash值相同的元素。
我很少考慮hash，覺得復雜度不好把握。以后倒是可以考慮用用，如：在問題“判斷兩個鏈表是否相交”有可以使用hash；“判斷鏈表有沒有環”用hash也很給力。
posted on 2011-08-24 20:15
hex108 閱讀(591)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm