最近在閱讀《數(shù)據(jù)結(jié)構(gòu)與算法分析-Java語言描述》瘩燥，對幾種常用數(shù)據(jù)結(jié)構(gòu)有了比較清晰的認識蕴忆，作此知識點整理以便翻閱悲幅。
1. 表的數(shù)組實現(xiàn),查詢?yōu)槌?shù)時間汰具，插入和刪除為線性時間，鏈表相反（變動位置已知的前提）吟孙。
2. Iterator聚蝶，被迭代的集合如果在結(jié)構(gòu)上發(fā)生變化（add/remove），使用Iterator會拋異常（其實刪除倒數(shù)第二個可以碘勉，hasNext()返回false） 验靡。使用Iterator內(nèi)部方法改變結(jié)構(gòu)不受影響雏节，因此應(yīng)該在立即使用迭代器時高职，再獲取迭代器。
3. Collection擴展了Iterable接口寥粹，List接口繼承了Collection接口产禾。
4. Iterator等操作亚情，“當(dāng)前項”其實是兩個數(shù)中間的位置，next返回下一項楞件，previous返回上一項土浸，add插到下一項前面。
5. 中綴表達式改成后綴表達式泪酱，字符正常輸出还最，操作符壓入棧中，并彈出棧中優(yōu)先級不低于自己的操作符輸出斯撮。
6. 尾遞歸可以等效為將代碼放到一個while循環(huán)中使用并未每一個參數(shù)賦值扶叉，以此來消除遞歸,在此過程中沒有必須知道的值，節(jié)省內(nèi)存溢十。
7. 循環(huán)隊列达吞，當(dāng)front大于back且差值為1（back指已插入元素），即為空列乌庶。（也有書籍的back指即將插入的元素，那么front=back為空或滿）
8. 樹的鏈表實現(xiàn)螃征，記錄全部子節(jié)點開銷大透敌，可以指向第一個兒子以及指向兄弟節(jié)點完成酗电。
9. 數(shù)的先序遍歷指先計算自己，再計算子節(jié)點撵术，后序遍歷相反，中序遍歷是先左子節(jié)點寝姿，再自己划滋，再右子節(jié)點。這些遍歷算法也在表達式樹中對應(yīng)著相應(yīng)前/后/中綴表達式根资。
10. 二叉樹-->二叉查找樹（大小關(guān)系）-->AVL數(shù)（平衡關(guān)系）同窘。
11. 二叉樹平均深度為根號N塞椎，二叉查找樹睛低，平均深度為logN。
12. 二叉查找樹的刪除操作骂铁，使用左子樹的最大值或右子樹的最小值來代替被刪除節(jié)點罩抗。
13. 單旋轉(zhuǎn)可以解決插入發(fā)生在“外側(cè)”的情況，雙旋轉(zhuǎn)解決插入發(fā)生在“內(nèi)側(cè)”的情況套蒂。
14. 進行雙旋轉(zhuǎn)钞支，先將“孫”與“子”節(jié)點進行旋轉(zhuǎn)茫蛹，在將后來的“子”與“父”節(jié)點進行旋轉(zhuǎn)。
15. 旋轉(zhuǎn)過程中的下方節(jié)點的子樹可能要重新適配位置烁挟。
16. 伸展樹婴洼，當(dāng)一個節(jié)點被訪問后，就要經(jīng)過一系列AVL樹旋轉(zhuǎn)被推到根上撼嗓。
17. 伸展樹的M次操作最多話費O(MlogN)柬采。
18. 伸展樹的展開過程，發(fā)生在祖父且警，父粉捻，當(dāng)前節(jié)點中。如果是zig-zag情形斑芜，則雙旋轉(zhuǎn)，如果為zig-zig情形杏头，則變成對稱圖形树酪。這樣可以將訪問節(jié)點移動到根處同時減少樹的深度約一半。
19. 伸展樹對于路徑長而超出正常查找時間的時候大州，對未來操作有益续语。當(dāng)訪問耗時少的時候，則不那么有益甚至有害厦画。
20. 伸展樹的刪除疮茄，當(dāng)刪除當(dāng)前節(jié)點，可以找到左子樹的最大值旋轉(zhuǎn)到該節(jié)點根暑，再連接右子樹力试。
21. 中序遍歷：先操作左子樹，再處理當(dāng)前節(jié)點排嫌，再處理右子樹畸裳。后序遍歷：先子樹，再自己淳地。先序遍歷：先自己怖糊，后子樹。層序遍歷：遍歷完當(dāng)前層颇象，再遍歷下一層伍伤。
<br /><br />
