最近在阅读《数据结构与算法分析-Java语言描述》，对几种常用数据结构有了比较清晰的认识，作此知识点整理以便翻阅。
1. 表的数组实现,查询为常数时间，插入和删除为线性时间，链表相反（变动位置已知的前提）。
2. Iterator，被迭代的集合如果在结构上发生变化（add/remove），使用Iterator会抛异常（其实删除倒数第二个可以，hasNext()返回false） 。使用Iterator内部方法改变结构不受影响，因此应该在立即使用迭代器时，再获取迭代器。
3. Collection扩展了Iterable接口，List接口继承了Collection接口。
4. Iterator等操作，“当前项”其实是两个数中间的位置，next返回下一项，previous返回上一项，add插到下一项前面。
5. 中缀表达式改成后缀表达式，字符正常输出，操作符压入栈中，并弹出栈中优先级不低于自己的操作符输出。
6. 尾递归可以等效为将代码放到一个while循环中使用并未每一个参数赋值，以此来消除递归,在此过程中没有必须知道的值，节省内存。
7. 循环队列，当front大于back且差值为1（back指已插入元素），即为空列。（也有书籍的back指即将插入的元素，那么front=back为空或满）
8. 树的链表实现，记录全部子节点开销大，可以指向第一个儿子以及指向兄弟节点完成。
9. 数的先序遍历指先计算自己，再计算子节点，后序遍历相反，中序遍历是先左子节点，再自己，再右子节点。这些遍历算法也在表达式树中对应着相应前/后/中缀表达式。
10. 二叉树-->二叉查找树（大小关系）-->AVL数（平衡关系）。
11. 二叉树平均深度为根号N，二叉查找树，平均深度为logN。
12. 二叉查找树的删除操作，使用左子树的最大值或右子树的最小值来代替被删除节点。
13. 单旋转可以解决插入发生在“外侧”的情况，双旋转解决插入发生在“内侧”的情况。
14. 进行双旋转，先将“孙”与“子”节点进行旋转，在将后来的“子”与“父”节点进行旋转。
15. 旋转过程中的下方节点的子树可能要重新适配位置。
16. 伸展树，当一个节点被访问后，就要经过一系列AVL树旋转被推到根上。
17. 伸展树的M次操作最多话费O(MlogN)。
18. 伸展树的展开过程，发生在祖父，父，当前节点中。如果是zig-zag情形，则双旋转，如果为zig-zig情形，则变成对称图形。这样可以将访问节点移动到根处同时减少树的深度约一半。
19. 伸展树对于路径长而超出正常查找时间的时候，对未来操作有益。当访问耗时少的时候，则不那么有益甚至有害。
20. 伸展树的删除，当删除当前节点，可以找到左子树的最大值旋转到该节点，再连接右子树。
21. 中序遍历：先操作左子树，再处理当前节点，再处理右子树。后序遍历：先子树，再自己。先序遍历：先自己，后子树。层序遍历：遍历完当前层，再遍历下一层。
<br /><br />
网友评论