数据结构

递归

基本法则：

1.有某些基准情形，他们不用递归就能求解, 用于结束递归调用

2.不断推进，递归调用必须总能够朝着基准情形的方向推进

3.递归假设所有调用都能运行（只需对一小部分值设计递归，便能扩大到更大的数据集）

4.合成效益法则，不要在不同的递归中做重复工作 p9

递归被正常使用的时候，应该很难将其转换成一个简单的循环

链表：

实现方法：

1.指针实现

2.游标实现

大量插入数据使用线性时间，不宜使用。

栈：

1.后进先出，只在一个位置存取单元

2.能确定栈使用大小的情况，使用数组实现开销更小

用途：

1.开闭符号检查{()}

2.函数调用

队列：

先进先出

树：

遍历：

1.先序遍历：根左右

2.中序遍历：左根右

3.后序遍历：左右根

二叉树：

大部分操作运行时间O(logN)

运用场景：

表达式树

二叉查找树：左子树所有节点小于x,右子树所有节点大于x

红黑树（c++,java标准库使用）

avl树:单旋转、双旋转