数据结构与算法--非线性数据结构
目录
树
树的高度，深度，层数的定义下面用图来说明这三个概念的区别
下面用图来说明这三个概念的区别
高度，这个概念跟生活中的楼层一样，从下往上数如第10层，12层起点都是地面
深度，是从上往下度量的，比如水中鱼的深度，是从水平面开始度量读
层数，跟深度类似，但计数起点是1
二叉树
满二叉树，叶子节点全都在最底层，出了叶子节点之外，每个节点都有左右两个子节点
完全二叉树，叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，除了最后一层其他层的节点个数都要达到最大
完全二叉树这种特殊的定义，在用数组存储二叉树时候可以避免浪费，数组的节点都用上了没有空间浪费
二叉树的遍历
前序遍历，对于树种的任意节点，先打印这个节点，再打印它的左子树，最后打印它的右子树
中序遍历，对于树种的任意节点来说，先打印它的左子树，然后打印它本身，最后打印它的右子树
后序遍历，对于树种任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身
三种遍历的代码实现
void preOrder(Node* root) {
if (root == null) return;
print root // 此处为伪代码，表示打印 root 节点
preOrder(root->left);
preOrder(root->right);
}
void inOrder(Node* root) {
if (root == null) return;
inOrder(root->left);
print root // 此处为伪代码，表示打印 root 节点
inOrder(root->right);
}
void postOrder(Node* root) {
if (root == null) return;
postOrder(root->left);
postOrder(root->right);
print root // 此处为伪代码，表示打印 root 节点
}
遍历二叉树，每个节点最多会被访问两次
所以二叉树遍历的时间复杂度是O(n)
一组数据，1，3，5，6，9，10 可以构建出多少种不同的二叉树
这是卡特兰数，是C[n,2n]/(n+1)种形式，c是组合数，节点的不同又是一种全排列
一共是n! * C[n,2n]/(n+1) 个二叉树
二叉查找树
在树种任意一个节点，其左字数中的每个节点的值，都要小于这个节点的值，而右字数节点的值都大于这个节点的值
查找，更新，插入都很容，删除比较复杂有三种情况
1.如果要删除的节点没有子节点，更新父节点指向null即可
2.要删除的节点只有一个子节点(只有左子节点或右子节点)，只要更新父节点指向要删除的节点的子节点即可
3.如果有两个子节点，需要找到这个节点右子树中的最小节点，把它替换到要删除的节点上，再删除这个最小节点，也可以加个删除标记
支持重复数据的二叉查找树
插入时，如果碰到一个节点的值与要插入的值相同，就将要插入的数据放到这个节点的右子树
查找时，遇到相同节点，继续在右子树种查找，直到遇到叶子节点
删除时，先查找每个要删除的节点，再按之前的删除方式，以此删除
完全二叉树的的高度小于等于logn
有了散列表为什么还要用二叉树
- 散列表中断数据是无序存储的，如果要输出有序数据，需要先排序，二叉树的中序遍历O(n)时间就可以输出了
- 散列表扩容时很耗时，遇到散列冲突性能不稳定，平衡二叉树的性能非常稳定
- 尽管散列表的查找操作时间复杂度是常量级，但因哈希冲突这个常量不一定比logn小，实际操作不一定比O(logn)块，加上函数的耗时，也不一定就比平衡二叉树效率高
- 散列表的构造比二叉树要复杂，需要考虑散列函数的设计，冲突解决，扩容缩容，平衡二叉树只要考虑平衡这一个问题
- 为避免过多的散列冲突，散列表的装载因子不能太大，特别是基于开放寻址法解决冲突时
红黑树
平衡二叉树
- AVL树，查找效率高，但删除/增加维护成本高
- 红黑树，查找/删除/增加的时间复杂度为0(logn)
- Treap，
- Splay Tree，这两个大部分情况下操作效率都很高，但极端情况下时间复杂度会降低
红黑树的定义
- 根节点是黑色的
- 每个叶子节点都是黑色的空节点(NIL)，即叶子节点不存储数据
- 任何相邻的节点都不能同时为红色，即红色节点是被黑色节点隔开的
- 每个节点，从该节点达到其可达叶子节点的所有路径，都包含相同数目的黑色节点
增加，删除操作，可能会破坏第三，第四点
平衡调整操作，就是把第三，第四点恢复过来
红黑树的左旋和右旋操作
插入操作
红黑树规定，插入的节点必须是红色的，插入的新节点都在叶子节点上，这里有两个特殊情况
- 如果插入节点的父节点是黑色的，那什么都不用做，它仍满足红黑树的定义
- 如果插入节点是根节点，直接改变它的颜色，变成黑色就可以了
其他情况都会违背红黑树的定义，就需要用左旋，右旋来调整，并改变颜色
红黑树的平衡调整是一个迭代的过程，把正在处理的节点叫做 关注节点，关注节点会随着不停迭代处理，
而不断变化，最开始的关注节点就是新插入的节点
新节点插入后，如果红黑树的平衡被打破，一般会有三种情况，只需要根据每种情况的特点，不断调整，
就可以让红黑树继续符合规定，也就是继续保持平衡
CASE1，如果关注节点是a，它的叔叔节点d是红色，就执行下面操作
- 将关注节点a的父节点b，叔叔节点d的颜色都设置成黑色
- 将关注节点a的祖父节点c的颜色设置成红色
- 关注节点变成a的祖父节点c
- 跳到CASE2或者CASE3
CASE2，如果关注节点是a，它的叔叔节点d是黑色，关注节点a是其父节点b的右子节点，就执行下面操作
- 关注节点变成a的父节点b
- 围绕新的关注节点b左旋
- 跳到CASE3
CASE3，如果关注节点是a，它的叔叔节点d是黑色，关注节点a是其父节点b的左子节点，就执行下面操作
- 围绕关注节点a的祖父节点c右旋
- 将关注节点a的父节点b，兄弟节点c颜色互换
- 调整结束
递归树
借助递归树来分析递归算法的时间复杂度
递归的思想是，将大问题分解为小问题来求解，再将小问题分解为小小问题
把这个一层一层分解的过程画成图，就是一棵树，这棵树就是递归树
下面是归并排序的递归树，每一次是O(n)，一共logn层，所以复杂度是O(n*logn)
快速排序分析
最好的情况下是区间划分后，每次都是一分为二，但这很难
假设分区后，两个分区的大小比列是1:k，当k=9时，用递推公式就是 T(n)=T(n/10)+T(9n/10)+n
用递归树表示如下
每次分区都要遍历待分区的所有数据，每一层区分操作所遍历的数据个数之和就是n，树的高度是h，复杂度是O(h*n)
快速排序的结束条件是分区大小为1，从根节点n到叶子节点1，递归树种最长路径每次要乘以9/10，最短要乘以1/10
遍历数据的个数综合就介于 nlog10n和nlog10/9 n之间，根据大O表示法，可以计算成O(n*logn)
如果k=99，或者999，这个推到仍然是成立的，从概率论角度来说，快速排序平均时间复杂度是O(n*logn)
斐波那契数列的时间复杂度
代码如下
if f(int n) {
if(n==1) return 1;
if(n==2) return 2;
return f(n-1)+f(n-2);
}递归树如下
f(n)分解为f(n-1)和f(n-2)，每次数据规模都是-1或者-2，叶子节点的规模是1或者2
从根节点到叶子节点，每条路径长度不一样，如果每次都-1那最长路径是n，如果每次-2，那最长路径是n/2
每次分解之后合并操作只需要一次加法运算，消耗时间记做1，从上往下第一层总时间消耗是1，第二层是2，第三层是2^2
第k层是2^(k-1)，整个算法的总时间消耗是每一层时间消耗之和
这个算法的时间复杂度介于O(2^n)和O(2^(n/2))之间，所以时间复杂度是指数级的
全排列的时间复杂度
比如把1，2，3 这三个数字做全排列，结果如下
123
132
213
231
312
321它的递归树如下
第一层有n次交换操作，第二层是n*(n-1)，第三层是n*(n-1)*(n-2)
最后一个数，n*(n-1)*(n-2)*...*2*1 等于n!
前面的n-1个数都小雨最后一个数，所以综合肯定小于n*n!
所以全排列的递归算法时间复杂度大于O(n!)，小于O(n*n!)，这个时间复杂度非常高
思考
1个细胞的生命周期是3小时，1小时分裂一次，求n小时候，容器内有多少细胞？
参考