数据结构与算法分析：C++描述 和 数据结构（刘大有）笔记
1.在计算机科学中，所有的对数都是以2为底的，除非另有声明。
2.递归不是循环逻辑，虽然用一个函数本身来定义这个函数，但是并没有用一个函数实例本身来定义该特定实例。
3.如下递归是低效的（计算任何事情不要超过一次）
bool isEven(int n){ return n%2==0;}long pow(long x,int n){ if(n==0) return 1; if(isEven(n)) return pow(x*x,n/2);//一次乘法 else return pow(x*x,n/2)*x;//两次乘法}因为把问题分半最多需要两次乘法（当N为奇数的时候），因此需要的乘法次数最多是2 log N。
7.当队列采用数组实现的时候，应使用循环数组，即回绕队头和队尾。
8.UNIX文件系统中每个目录还有一项指向该目录本身以及另一项指向该目录的父目录。因此，严格来说，UNIX文件系统不是树，而是类树（treelike）
9.在处理二叉树的时候应注意处理重复元的情况。二叉树平均深度是O(根号 N)。
10.对任意常数k，(logN)的k次等于O(N)。它告诉我们对数增长得非常缓慢。
11.大O分析假设所有的操作都是相等的。当涉及磁盘IO的时候这么假设是不合适的。几乎在所有的情况下，控制运行时间的都是磁盘访问的次数。于是如果我们把磁盘访问的次数减少一半，那么运行时间也将减少一半。
12.树-----二叉树-----二叉查找树-----AVL树
-----伸展树
-----线索二叉树
-----M叉查找树-----B树
-----表达式树（二元运算符）
树：Father数组可顺序存储树。链接存储：Father链接；孩子链表链接；左孩子右兄弟
满二叉树：高度为k的有2^(k+1) -1个节点，叶结点都在第k层上，每个分支节点都有两个字节点。
完全二叉树：一棵包含n个节点的高为k的二叉树T，当按层次顺序编号T的所有节点，对应于一棵高为k的满二叉树中编号由1至n的那些节点。可采用二叉树顺序存储，A[0]存储根，A[i]的左儿子存放在A[2i+1]，右儿子存放在A[2i+2]。
二叉查找树：节点X的左子树中所有项的值小于X中的项，右子树中所有项大于X中的项。二叉查找树平均深度为O(log N)。
表达式树：树叶是操作数，其他节点为操作符。
AVL树（平衡树）：每个节点的左子树和右子树的高度最多差1的二叉查找树（空树的高度定义为-1）。必须保证树的深度是O(log N)。当插入破坏AVL树的特性时，要通过旋转来修正。插入：（1）左左、（2）左右、（3）右左、（4）右右。（1）（4）需要通过单旋转，（2）（3）通过双旋转。单旋转是插入路径上第一个不平衡的节点及其子节点，旋转两者的位置。双旋转是插入路径上第一个不平衡节点和其子节点、孙节点，将孙节点旋转到另外两者之间。
伸展树：它保证从空树开始任意连续M次对树的操作最多花费O(M log N)时间。当M次操作的序列总的最坏情形运行时间为O(M f(N))时，我们就说它的摊还运行时间为O(f(N))。因此，一棵伸展树每次操作的摊还代价是O(log N)。在访问后将实施伸展操作。之字形（zig-zag）：双旋转。一字形（zig-zig）：将祖-父-孙伸展为孙-父-祖。伸展时需要一路伸展到根。
B+树：（1）数据项存储在树叶上。（2）非叶节点存储直到M-1个键，以指示搜索的方向；键i代表子树i+1中的最小的键。（3）树的根或者是一片树叶，或者其儿子数在2和M之间。（4）除根外，所有非树叶节点的儿子数在(M/2)取天棚和M之间。（5）所有的树叶都在相同深度上并有(L/2)取天棚和L之间个数据项。分裂树根将增高树。删除根将降低树。
线索二叉树：可直接查找任一节点在某种遍历顺序下的前驱节点和后继节点的二叉树。对于找前驱节点和后继节点的操作，线索树优于非线索树。
红黑树：
set和map使用自顶向下红黑树。
13.一棵树所有节点的深度和称为内部路径长。
14.懒惰删除：当一个元素要被删除时，它仍留在树中，而只是做了个被删除的记号。