Question

树的深度和高度定义?
树中结点的深度和高度定义?

树

扩展二叉树
    将二叉树中每个结点的空指针引向一个虚结点后的二叉树。扩展二叉树可以做到一个历遍序列确定一棵二叉树。
线索二叉树
堆
    是具有如下性质的完全二叉树：
        每个节点的值都大于或等于其左右孩子节点的值，称为大顶堆
        每个节点的值都小于或等于其左右孩子节点的值，称为小顶堆
    i是2*i, 2*i+1的双亲

图

存储模型
    邻接表
    邻接矩阵
    十字链表：  将邻接表和逆邻接表整合，时间复杂度同邻接表；针对有向图。
    邻接多重表：针对侧重边操作的无向图；和邻接表的唯一区别是此处边只用一个边结点表示。
    边集数组：  对边的操作需要历遍边集数组；适合对边依次进行的操作。
历遍
    DFS：类似于树的前序历遍
        time 邻接矩阵 - O(n^2)；邻接表 - O(n+e)
    BFS：类似于树的层序历遍
        time 邻接矩阵 - O(n^2)；邻接表 - O(n+e)
最小生成树
    Prim
        以某顶点为起点，逐步找各顶点上最小权值边来构建最小生成树；以顶点为目标
    Kruskal
        逐步找最小权值边来构建，但是不能形成环；以边为目标；使用边集数组
最短路径
    Dijkstra
    Floyd
拓扑排序
    选择一个入度为0的边输出，删除此顶点，并删除以此顶点为尾的弧，重复此过程直到输出所有顶点。
    有向无回路图
    time：O(n+e)
测试环路

Search

静态查找表：不涉及添加和删除
动态查找表

Sequential search：优化技巧设置哨兵可以减少越界检查的开销
    time O(n)；适合数据量小；查找概率不同时，如果将高概率项放在前面，效率会提高。
有序表查找
    Binary search：线性表中的记录必须是关键码有序，采用顺序存储；time O(lgn)
        mid = low + (1/2)*(high - low)
    Interpolation search：适合表长较长，关键字分布较均匀的查找表，此时平均性能优于二分查找
        mid = low + ((key - a[low])/(a[high] - a[low]))*(high - low)
    Fibonacci search：使用黄金分割原理；time O(lgn)；平均性能优于二分查找，但是如果key一直在左侧，低于二分查找
        mid = low + F[k - 1] - 1
        |low, len=F[k-1]-1 | mid | len=F[k-2]-1, high|
        |                len=F[k] - 1                |
        计算只涉及加减，所以大数据情况下有性能优势

    三种方法的差别在于mid的计算选择

    有序适合静态查找表

线性索引查找
    索引是为了加快查找速度而设计的一种数据结构。索引就是把一个关键字与它对应的记录相关联的过程。
    一个索引由若干个索引项组成，每个索引项至少包含关键字和其对应的记录在存储器中的位置
    类型
        线性索引：将索引项集合组织成线性结构，也称为索引表
            稠密索引
                在线性索引中，将数据集中的每个记录对应一个索引项（关键码，指针）
                索引表中，索引项一定是按照关键码有序的排列；方便采用以上三种有序查找方法
                特点：索引项和数据集的记录个数相同；因此，大数据情况下，内存不够用，增加磁盘访问量 => 性能下降
                time O(lgn)
            分块索引
                将数据集分块，块内无序(或有序)，快间有序(即，关键字的大小区间有序)
                每一块对应一个索引项 => 分块索引
                （最大关键码，          -> 下一块最小关键字也比这个最大关键字大，用于查找分块
                 块中记录数，           -> 循环时使用
                 指向块首数据元素的指针） -> 便于开始对这块记录进行历遍
                查找方式：二分法找到对应分块，块内顺序查找
                time: 总共n条记录，分成m块，每块t条记录，n=m*t -> O(m + t)；
                      如果m=t，time O(n^(1/2))
            倒排索引 (inverted index)
                通过属性值来确定包含该属性值的所有记录，而不是通过记录来确定属性值
                （次关键字， -> 属性值
                 记录号表）  -> 记录主关键字或指针
                次关键字进行排序
                优点：查找记录非常快
                缺点：记录号不定长，插入和删除开销大

        树形索引
        多级索引

二叉查找树
    适合动态表；查找，插入和删除效率都不错
    定义
        或者是一棵空树
        或者是具有如下性质的二叉树
            如果左子树不空，左子树上所有结点的值均小于它的根结点的值
            如果右子树不空，右子树上所有结点的值均大于它的根结点的值
            它的左右子树也分别为二叉查找树
    以链表形式存储，执行插入和删除时不需要移动元素
    time O(depth of tree)

平衡二叉树（AVL tree）
    Height-balanced BST
    BST且每个结点的左右子树高度相差对多为1
    Balance Factor（BF 平衡因子）：二叉树结点的左子树深度减去右子树深度的值
    time：insert/delete O(lgn)；find O(lgn)

红黑树（red-black tree）

多路查找树（multi-way search tree）
    如果数据量大到内存无法处理，那么访问集合元素的时间不仅包括寻找该元素所需的比较次数的函数，还得考虑对磁盘等外部存储设备的访问时间和多少次单独访问
    每个结点的孩子树可以多于两个，且每个结点处可存储多个元素。由于是查找树，所有元素之间存在某种排序关系。

    每个结点存储多少个元素和它的孩子数的多少 进行分类：
        2-3树
        2-3-4树
        B树
        B+树

散列表查找（Hash）
    散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系，每个key对应一个存储位置H(key)
    采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间为Hash table
    散列技术的记录之间不存在任何逻辑关系，它们只与关键字之间有关系
    不适合范围查找，一对多的关系，无法获得排序
    设计简单，均匀，存储利用率高的散列函数是散列技术的关键
    如果key1 != key2，但是H(key1) == H(key2)，出现冲突(collision)；把key1和key2称为H()的同义词(synonym)
    好的散列函数
        计算简单：消耗时间少
        散列地址分布均匀

    如何设计散列函数
        直接寻址法：H(key)=a*key+b (a,b是常数)；适合知道关键字的分布情况，查找表较小且连续的情况
        数字分析法：抽取关键字的部分来计算存储位置；适合关键字位数较大，如果知道关键字的分布并且关键字的若干位分布较均匀
        平方取中法：n*n然后取中间几位；适合不知道关键字分布，并且位数又不是很大的情况
        折叠法：将关键字从左到右分割成位数相等的几部分，叠加，取其中几位；适合不知道关键字分布，并且位数很大的情况
        除数取余法：H(key)=key mod p；p为小于或等于散列表长m的质数
        随机数法：选择一个随机数，取关键字的随机函数值为散列地址，H(key)=random(key)；适合关键字长度不同的情况

    处理冲突
        开放地址法
            线性探测法
                H(key)=(H'(key)+di) mod m (di=0,1,...,m-1)
                堆积（不是同义词，但是争夺同一个地址的情况）
            二次探测法
                H(key)=(H'(key)+di^2) mod m (di=0,1,...,m-1)
            随机探测法
                H(key)=(H'(key)+ri) mod m (ri为伪随机函数)
            再散列值法

        链地址法
            所有关键字为同义词的记录存在一个单链表中

        公共溢出区法
            将冲突的记录都放到一个公共溢出区表，在此表中的项目是顺序查找的

        散列表性能分析
            散列查找的平均长度
                散列函数是否均匀
                处理冲突
                散列表的装填因子=填入表中的记录数/散列表的长度

排序

稳定性：key相同的记录在排序前后保持相同的顺序
内/外排序：排序过程中待排序的所有记录是否全部放置在内存中
性能因素
    内排序
        时间（操作包括 比较 和 移动）
        辅助空间：除了放置待排序所占空间外，算法执行需要的空间
        算法实现的复杂程度
    外排序
排序分类
    根据排序过程中借助的主要操作分为：插入排序，交换排序，选择排序和归并排序
    根据复杂程度：冒泡，选择，插入排序；希尔，堆，归并，快速排序

基于'数组'的排序
    Bubble sort
        两两比较相邻记录的关键字，如果反序则交换，直到没有反序记录为止
        In-place
    Select sort
        每一趟在n-i+1(i=1,2,...,n-1)个记录中选取关键字最小的记录作为有序序列的第i个记录；
        通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并与第i（1<=i<=n）个记录交换
        In-place
    Insert sort
        将一个记录插入到已经排好序的有序表中，从而得到一个新的，记录数加1的有序表；
        记录少或者基本有序时高效
        基本有序定义：小的关键字基本在前面，大的关键字基本在后面，不大不小的基本在中间
        In-place
    Shell sort
        是Insert sort的改进；分成若干组（记录少）分别进行插入排序，整个数组变成基本有序数组，然后再进行一次针对完整数组的插入排序
        分割待排序记录的目的：减少待排序记录个数，使整个序列朝基本有序方向发展
        采用跳跃分割技术：将相距某个增量的记录组成一个子序列，这样才能保证对子序列分别进行插入排序后得到的基本有序序列而不是局部序列
        In-place/not in-place
        不稳定！
    Heap sort:
        是Select sort的改进；每次选择最小记录的同时，根据比较结果对其他记录进行调整，减少下次选择最小记录的时间
        将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是根节点。将它移走（与数组末尾元素交换），然后将剩下的n－1序列重新构造成堆
        堆排序对原始数据的排序状态不敏感，无论最好，最坏和平均时间都是O(n*lgn)；
        建堆 time O(n)
        In-place
        不稳定！ 因为记录的比较和交换是跳跃进行的
        建堆需要的比较次数较多，不适合小数据量的情况
    Merge sort
        从长度为1的子序列开始，不断两两归并，直到得到一个长度为n的有序序列为止；
        类似于一个倒置的二叉树！
        time O(n*lgn) 最好，最坏和平均
        space O(n+lgn)，n是merge使用的数组，lgn是递归使用的栈空间
        稳定！进行两两比较，没有跳跃
        比较占内存，但是效率高且稳定的算法

        非递归版本
            避免了O(lgn)的栈空间
    Quick sort
        是Bubble sort的改进；
        通过比较和移动实现，只不过增大了比较和移动的距离，减少了总的比较和移动次数
        通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对两部分记录继续进行排序
        不稳定！关键字的比较和交换是跳跃的
        time O(nlgn) 最好和平均； O(n^2) 最坏
        space 递归 O(lgn) 最好和平均； O(n) 最坏； 栈空间
        优化
            pivot的选取
                随机选取
                三数选一(median of three): 适合小数组
                九数选一(median of nine): 选三组，每组三个，取每组的中间值，然后再选中间值中的中间值
            优化不必要的交换
                采取替换而不是交换，最后用pivot覆盖最终位置上的数
            优化小数组时的方案
                因为递归产生额外的消耗，不如使用 Insert sort
            优化递归操作
                尾递归优化
    对比

    时间和空间复杂度：
    排序方法 |   平均             |   最好     |   最坏   |   辅助空间   |   稳定
    bubble  | O(n^2)            |  O(n)     | O(n^2)   |    O(1)     |   Yes
    select  | O(n^2)            |  O(n^2)   | O(n^2)   |    O(1)     |   Yes
    insert  | O(n^2)            |  O(n)     | O(n^2)   |    O(1)     |   Yes
    shell   | O(nlgn) ~ O(n^2)  |  O(n^1.3) | O(n^2)   |    O(1)     |   No
    heap    | O(nlgn)           |  O(nlgn)  | O(nlgn)  |    O(1)     |   No
    merge   | O(nlgn)           |  O(nlgn)  | O(nlgn)  |    O(n)     |   Yes
    quick   | O(nlgn)           |  O(nlgn)  | O(n^2)   | O(lgn)~O(n) |   No

    移动次数：
    排序方法 |   平均             |   最好     |   最坏
    bubble  | O(n^2)            |  0        | O(n^2)
    select  | O(n)              |  0        | O(n)
    insert  | O(n^2)            |  O(n)     | O(n^2)
    => 当移动的开销很大时，比如说关键字信息量很大且记录数较小时，select是好选择；
       另外，记录信息量的大小对4种改进算法的影响不大