数据结构与算法（二）

二叉树

概念
- 节点的高度：结点到叶子结点的最长路径
- 节点的深度：根节点到这个结点所经历边的个数
- 节点的层级：结点的深度+1
- 树的高度：根节点的高度

二叉树的类型

- 满二叉树：编号2，叶子节点都在最底层，除叶子节点外，每个节点都有左右两个子节点。
- 完全二叉树：编号3，叶子节点都在最下层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大。

存储二叉树
- 链表存储法
- 顺序存储法
  
  如果是完全二叉树，数组存储是最节省内存的方法。

二叉树的遍历 O(n)

前序遍历：对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
中序遍历：对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
后序遍历：对于树中的任意节点来说，线打印它的左子树，然后打印右子树，最后打印它本身。

按层遍历

// 前序遍历
function preOrder(root) {
  if (root == null) return;
  console.log(root.val) 
  preOrder(root->left);
  preOrder(root->right);
}

// 中序遍历
function inOrder(root) {
  if (root == null) return;
  inOrder(root->left);
  console.log(root.val) 
  inOrder(root->right);
}

// 后序遍历
function postOrder(root) {
  if (root == null) return;
  postOrder(root->left);
  postOrder(root->right);
  console.log(root.val) 
}

二叉查找树 O(logn)

要求：对于树中任意一个节点，其左子树的值都要小与这个节点的值，右子树的值都要大于这个节点的值。
平衡时间复杂度：O(logn)

二叉查找树的查找：

function treeSearch(tree,value){
    if(tree.value === value){
        return tree.value;
    }
    else if(tree.value<value && tree.right){
        return treeSearch(tree.right,value);
    }
    else if(tree.value>value && tree.left){
        return treeSearch(tree.left,value);
    }
    return null;
}

二叉树插入操作：

// 假设插入的数据在叶子节点上
function treeInsert(tree,value){
    var p = tree;
    while (p!=null){
        if(p.value === value){
            return 'repeat'
        }
        else if(p.value < value){
            if(!p.right){
                p.right = {value: value};
                return;
            }
            p = p.right;
        }
        else if(p.value > value){
            if(!p.left){
                p.left = {value: value};
                return;
            }
            p = p.left;
        }
    }
}

二叉树删除操作

如果该节点没有子节点，删除该节点，并将父节点指向Null。
如果该节点有一个子节点，删除该节点，并将父节点指向子节点。

如果该节点有两个及以上子节点，删除该节点，并将右子树中最小节点替换到该位置。

function treeDelete(tree,value){
    var p = tree;
    var pp = null; // 父节点
    while (p!=null && p.value!= value){
        pp = p;
        if(value > p.value){
            p = p.right;
        }else {
            p = p.left;
        }
    }
    if( p == null){
        return null;
    }
    // 没有子节点
    if(!p.left && !p.right){
        if(pp.right == p){
            delete pp.right;
        }else {
            delete pp.left;
        }
        return;
    }
    // 有一个子节点
    else if(!p.left || !p.right){
        var child = p.left? p.left:p.right;
        if(pp.right == p){
            pp.right = child;
        }
        else{
            pp.left = child;
        }
        return;
    }
    // 有两个及以上子节点
    else{
        //找右子树中的最小值
        minP = p.right; 
        minPP = p;
        while(minP.left !=null){
            minPP = minP;
            minP = minP.left;
        }
        p.value = minP.value;
        delete minPP.left;
    }
}

快速查找最大、最小节点、前驱节点、后继结点
中序遍历查找二叉树，可以输出有序的数据，时间复杂度是O(n)
支持重复数据的二叉查找树：
- 方法一：二叉查找树每个节点不止存储一个数据，存储一个链表，或者是动态扩容的数据。
- 方法二：每个节点只存储一个数据，如果重复，将这个值放在右子树，当作大于这个节点处理。查找时，查到值相同节点不停止查找，继续在右子树中查找，知道找到叶子节点。删除时，先找到所有节点，再按正常删除操作处理。
与散列表对比：
- 散列表数据是无序的，如需要有序的数据，先排列；二叉查找树只需要中序遍历，可以在O(n)时间复杂度内，输出有序的数据序列。
- 散列表扩容需要耗时比较久，遇到散列冲突时，性能不稳定；平衡二叉树的性能稳定，时间复杂度在O(logn)。
- 散列表查找操作时间时常数级，但因为哈希冲突存在，这个常量不一定比logn小，加上哈希函数的耗时。
- 散列表的构造比二叉查找树要复杂；平衡二叉查找树只需要考虑平衡性这一个问题。

红黑树

红黑树是一种性能非常稳定的平衡二叉树，它是为了解决普通二叉树在数据更新中，复杂度退化的问题产生的，红黑树的高度近似log2n，所以它是近似平衡，查找、插入、删除的时间复杂度都是O(logn)。

要求
- 根节点是黑色
- 每个叶子节点都是黑色空节点，也就是说叶子节点不存储数据
- 任何相邻节点不同时为红色，也就是说，红色节点是被黑色节点隔开
- 每个节点，从该节点到达其可达叶子节点所经过的所有路径，经过的黑色节点的数目相同
实现
- 左旋：围绕某个节点的左旋
  右旋：围绕某个节点的右旋
插入
- 插入操作的平衡调整：
  规定：插入的节点必须是红色的，而且二叉查找树中新插入的节点都是放在叶子节点上。
  1. 如果插入节点的父节点是黑色的，那我们什么都不用做，它仍然满足红黑树的定义。
  2. 如果插入的节点是根节点，那我们直接改变它的颜色，把它变成黑色就可以了。
  3. 除此外的情况需要左右旋转、改变颜色来满足规定。
- case1: 如果关注节点是 a，它的叔叔节点 d 是红色
  1. 将关注节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑色
  2. 将关注节点 a 的祖父节点 c 的颜色设置成红色；
  3. 关注节点变成 a 的祖父节点 c；
  4. 跳到 CASE 2 或者 CASE 3。
- case2: 如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a是其父节点 b 的右子节点
  1. 关注节点变成节点 a 的父节点 b；
  2. 围绕新的关注节点b 左旋；
  3. 跳到case3.
- case3: 如果关注节点是 a，它的叔叔节点d是黑色，关注节点a 是其父节点b的左子节点
  1. 围绕关注节点 a 的祖父节点 c 右旋;
  2. 将关注节点 a 的父节点 b、兄弟节点 c 的颜色互换。
  3. 调整结束。
删除
- Step1: 针对删除节点初步调整，保证整个红黑树在删除这个节点后，依然满足“每个节点，从该节点到达其可达叶子节点所经过的所有路径，经过的黑色节点的数目相同”。
  1. case1: 如果要删除的节点是 a，它只有一个子节点 b
    - 删除节点 a，并且把节点 b 替换到节点 a 的位置
    - 节点a只能是黑色，节点b只能是红色。在case1中，将节点b改成黑色。
    - 不需要二次调整
  2. case2: 如果要删除的节点 a 有两个非空子节点，并且它的后继节点就是a的右子节点c
    - 如果节点 a 的后继节点就是右子节点 c，那右子节点 c 肯定没有左子树。我们把节点 a 删除，并且将节点 c 替换到节点a的位置。
    - 把节点c 的颜色设置为节点a的颜色
    - 如果节点c是黑色，为了不违反最后一条定义，给节点c的右子节点d增加一个黑色。
    - 此时关注节点变成d ，进行二次调整。
  3. case3: 如果要删除的是节点 a，它有两个非空子节点，并且节点 a 的的后继节点不是右子节点
    - 找到后继节点 d，并将它删除，删除后继节点 d 的过程参照case1
    - 将节点 a 替换成后继节点 d
    - 把节点 d 的颜色设置为跟节点 a 相同的颜色
    - 如果节点 d 是黑色，为了不违反红黑树的最后一条定义，我们给节点d的右子节点c多加一个黑色
    - 此时关注节点变成c，进行二次调整。
- Step2: 二次调整，以满足“即不存在相邻的两个红色节点“
  1. case1: 如果关注节点是 a，它的兄弟节点 c 是红色的
    - 围绕关注节点 a 的父节点 b 左旋
    - 关注节点 a 的父节点 b 和祖父节点 c 交换颜色
    - 关注节点不变
    - 继续从四种情况中选择适合的规则来调整
  2. case2: 如果关注节点是 a，它的兄弟节点 c 是黑色的，并且节点 c的左右子节点 d、e 都是黑色的
    - 将关注节点 a 的兄弟节点 c 的颜色变成红色
    - 从关注节点 a 中去掉一个黑色，这个时候节点 a 就是单纯的红色/黑色
    - 给关注节点 a 的父节点b增加一个黑色
    - 关注节点从 a 变成其父节点 b
    - 继续从四种情况中选择适合的规则来调整
  3. case3: 如果关注节点是 a，它的兄弟节点 c 是黑色，c 的左子节点d 是红色，c的右子节点d是黑色
    - 围绕关注节点 a 的兄弟节点 c 右旋
    - 节点 c 和节点 d 交换颜色
    - 关注节点不变
    - 继续从四种情况中选择适合的规则来调整
  4. case4: 如果关注节点 a 的兄弟节点 c 是黑色的，并且 c 的右子节点是红色
    - 围绕关注节点 a 的父节点 b 左旋
    - 将关注节点 a 的兄弟节点 c 的颜色，跟关注节点 a 的父节点 b 设置成相同的颜色
    - 将关注节点 a 的父节点 b 的颜色设置为黑色
    - 从关注节点 a 中去掉一个黑色，节点 a 就变成了单纯的红色/黑色
    - 将关注节点 a 的叔叔节点 e 设置为黑色
    - 调整结束

递归树

使用递归树分析时间复杂度

递归树

归并排序递归树
- 每一层耗时的合并操作耗时n
- 满二叉树的高度是logn
- 所以时间复杂度是 O(nlogn)
快排递归树
- 假设每次分区都是1:9
- 每层操作数据之和为n
- 根节点到叶子节点最短路径是log(10)n，最长路径是log(9/10)n，忽略常数，即logn
- 所以时间复杂度是O(nlogn)

斐波那契数列的递归树

function feibo(n) {
if (n == 1) return 1;
if (n == 2) return 2;
return feibo(n-1) + feibo(n-2);
}

斐波那契数列的递归树

- 根节点到叶子节点最长路径是n， 最短路径是n/2
- 如果是n，总耗时就是 2^n - 1； 如果是n/2 总耗时就是 2^(n/2) -1;
- 所以时间复杂度是O(2^n) ~ O(2^(n/2))

全排列的时间复杂度
- 总和：n + n(n-1) + n(n-1)(n-2) +… + n(n-1)(n-2)…21 = O(n!) ~ O(n*n!)

堆

定义：
- 堆是个完全二叉树。
- 堆中每一个节点的值都必须大于等于（或者小于等于）其子树中每个节点的值，称为“大顶堆”（或小顶堆）。
实现
- 用数组存储堆
- 插入元素
  堆化：顺着节点所在的路径，向上或者向下，对比，然后交换。
- 删除堆顶元素
  把最后一个节点放到堆顶，然后利用父子节点对比方法，对于不满足父子节点大小关系的，互换位置，重复该过程直到满足所有大小关系。

基于堆实现排序

时间复杂度：O(nlogn)

Step1: 建堆：

从下往上的堆化

function buildHeap(a, n){
    // 对于完全二叉树来说，下标从n/2 + 1 到 n的节点都是叶子节点
    for(var i = n/2;i>=1; --i){
        heapify(a,n,i)
    }
}
function heapify(a,n,i){
    while (true){
        var maxPos = i;
        if(i*2 <= n && a[i] < a[i*2]){
            maxPos = i*2
        }
        if(i*2+1 <= n && a[maxPos] < a[i*2+1]){
            maxPos = i*2+1;
        } 
        if(maxPos == i) break;
        var tmp = a[i];
        a[i] = a[maxPos];
        a[maxPos] = tmp;
        i = maxPos
    }
}

时间复杂度：O(n)

Step2: 排序：
每次都将最大的元素放到后面

function sort(a){
    buildHeap(a, a.length);
    var k = a.length-1;
    while (k>1){
        tmp = a[k];
        a[k] = a[1];
        a[1] = tmp;
        k--; //除去刚刚交换到末尾的元素，进行堆化
        heapify(a,k,1);
    }
}

时间复杂度：O(nlogn)

快速排序与堆排序对比

堆排序数据访问没有快排友好
对于同样的数据，在排序中，堆排序交换的次数多于快排

堆的应用

优先级队列
- 合并有序小文件：
  假设我们有 100 个小文件，每个文件的大小是 100MB，每个文件中存储的都是有序的字符串。我们希望将这些 100 个小文件合并成一个有序的大文件。我们从这 100 个文件中，各取第一个字符串，放入数组中，然后比较大小，如果每次都遍历数据找出最小的一个，显然比较慢。使用堆，小文件中取出来的字符串放入到小顶堆中，那堆顶的元素，也就是优先级队列队首的元素，就是最小的字符串。
- 高性能定时器：
  按照任务设定的执行时间，将这些任务存储在优先级队列中，队列首部（也就是小顶堆的堆顶）存储的是最先执行的任务。
  定时器拿队首任务的执行时间点，与当前时间点相减，得到一个时间间隔T。定时器就设定在T秒后，执行这个任务。
  这样就不用每个1s轮询一次。
利用堆求Top K
- 静态数据：
  维护一个大小为K的小顶堆，遍历静态数据数组n，如果元素比堆顶大，删除堆顶元素，插入该元素。
- 动态数据：
  维护一个大小为K的小顶堆，当有新数据时，如果元素比堆顶大，删除堆顶元素，插入该元素。
利用堆求中位数
- 静态数据：
  直接数组排序
- 动态数据：
  维护两个堆，一个大顶堆，一个小顶堆。大顶堆中存储前半部分数据，小顶堆存后半部分数据，且小顶堆中堆数据都大于大顶堆中堆数据。如果是奇数，大顶堆中存n/2+1个数据。中位数就是大顶堆的堆顶。
- 求99% 响应时间：
  将响应时间从小到达排序后，第n99%的数据就是99%响应时间。
  同样维护两个堆，一个大顶堆，一个小顶堆。大顶堆中存储n99%的数据，小顶堆存储1%的数据，取大顶堆堆顶数据。

图

概念
- 无向图：
- 有向图：
- 带权图：
- 顶点
- 边
- 度：跟顶点相连接的边的个数
- 入度：多少个边指向这个顶点。出度：多少个边以这个顶点为起点。
存储
- 邻接矩阵
  
  简单直接，浪费空间。
- 邻接表
  
  节省空间，使用耗时
  可以将链表改成平衡二叉树、红黑树提升效率。

广度优先算法、深度优先算法

基于“图”这种数据结构

广度优先算法(Breadth-First-Search)

先查找离起始顶点最近的，然后是次近的，依次往外搜索。
时间复杂度：O(E)，E是边的个数

空间复杂度：O(V)，V是顶点的个数

public void bfs(int s, int t) {
    if (s == t) return;
    boolean[] visited = new boolean[v];
    visited[s]=true;
    Queue<Integer> queue = new LinkedList<>();
    queue.add(s);
    int[] prev = new int[v];
    for (int i = 0; i < v; ++i) {
        prev[i] = -1;
    }
    while (queue.size() != 0) {
        int w = queue.poll();
    for (int i = 0; i < adj[w].size(); ++i) {
        int q = adj[w].get(i);
        if (!visited[q]) {
            prev[q] = w;
            if (q == t) {
            print(prev, s, t);
            return;
            }
            visited[q] = true;
            queue.add(q);
        }
        }
    }
    }

    private void print(int[] prev, int s, int t) { // 递归打印 s->t 的路径
    if (prev[t] != -1 && t != s) {
        print(prev, s, prev[t]);
    }
    System.out.print(t + " ");
    }

深度优先算法(Depth-Firsh-Search)

时间复杂度 O(E)，E是边数

空间复杂度 O(V), V是顶点数

boolean found = false; // 全局变量或者类成员变量

public void dfs(int s, int t) {
found = false;
boolean[] visited = new boolean[v];
int[] prev = new int[v];
for (int i = 0; i < v; ++i) {
    prev[i] = -1;
}
recurDfs(s, t, visited, prev);
print(prev, s, t);
}

private void recurDfs(int w, int t, boolean[] visited, int[] prev) {
if (found == true) return;
visited[w] = true;
if (w == t) {
    found = true;
    return;
}
for (int i = 0; i < adj[w].size(); ++i) {
    int q = adj[w].get(i);
    if (!visited[q]) {
    prev[q] = w;
    recurDfs(q, t, visited, prev);
    }
}
}

广度优先搜索需要借助队列来实现，遍历得到的路径就是，起始顶点到终止顶点的最短路径。深度优先算法使用回溯的思想，非常适合递归实现。