数据结构与算法

名词

大O表示法：指代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度，简称时间复杂度。
空间复杂度：空间复杂度全称就是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。
平均时间复杂度：即加权平均时间复杂度或者期望时间复杂度。
均摊时间复杂度：就是一种特殊的平均时间复杂度，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度低的情况上。

时间复杂度分析

只关注循环执行次数最多的一段代码
加法法则：总复杂度等于量级最大的那段代码的复杂度
乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

书单

入门

《大话数据结构》
《算法图解》
不同编程语言
《数据结构与算法分析：JavaScript(/Python/..)语言描述》
经典
《算法》
《算法导论》
殿堂级
《计算机程序设计艺术》
面试
《编程之美》
《剑指offer》
《编程珠玑》
闲暇
《数学之美》
《算法之美》
《算法帝国》

数组

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
最大的特点就是支持随机访问，但插入、删除操作也因此变得比较低效，平均情况时间复杂度为 O(n)，根据下标随机访问的时间复杂度为 O(1)。

链表

链表不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用。其中，把内存块成为“结点”

单链表：每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的的地址（即后续指针 next）

头结点记录了链表的基地址，尾节点的指针指向Null空地址。
循环链表：与单链表区别是，尾节点的指针指向头节点。
双向链表：每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针prev指向前一个节点。

链表数组性能对比

数组使用连续内存空间，可以借助cpu缓存机制，进行预读。
[CPU缓存机制]CPU在从内存读取数据的时候，会先把读取到的数据加载到CPU的缓存中。而CPU每次从内存读取数据并不是只读取那个特定要访问的地址，而是读取一个数据块(这个大小我不太确定。。)并保存到CPU缓存中，然后下次访问内存数据的时候就会先从CPU缓存开始查找，如果找到就不需要再从内存中取。这样就实现了比内存访问速度更快的机制，也就是CPU缓存存在的意义:为了弥补内存访问速度过慢与CPU执行速度快之间的差异而引入。
数据缺点是大小固定，而链表天然支持动态扩容。

基于链表LRU缓存淘汰策略

维护一个有序单链表，越靠近尾部节点是越早之前访问
插入数据（新增），缓存未满，将数据插入链表头部
插入数据（已有），缓存未满，将改数据从原来节点迁移到头部节点
插入数据（新增），缓存已满，删除尾节点数据，将新数据插入链表头部

栈

后进者先出，先进者后出。（比如垒起来的盘子）

动态扩容：均摊复杂度O(1)
函数调用栈：操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”的结构，用来存储函数调用时的临时变量。每进入一个函数，就会讲临时变量作为一个栈帧进入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。
应用：

表达式求值：编译器就是通过两个栈来实现的。其中一个保存操作数的栈，另一个是保存运算符的栈。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取2个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。
表达式求值

function calculate(val){
    var cal = val.split(' ');
    var numAry = [];
    var utilAry = [];
    var level = {
        '+':1,
        '-':1,
        '*':2,
        '/':2
    }
   
    var toCalNow = function (){
        var sum = null;
        console.log('calnow',numAry,utilAry);
        for(var n=0,j=0;n<numAry.length,j<utilAry.length;n++,j++){
            var num1 = numAry[n+1];
            if(n == 0){
                var num2 = numAry[n];
            }
            else{
                var num2 = sum;
            }
            var handler = utilAry[j]
            num2 = parseInt(num2);
            num1 = parseInt(num1);
            switch (handler){
                case '+':
                    sum = num1 + num2;
                    break;
                case '-':
                    sum = num1 - num2;
                    break;
                case '*':
                    sum = num1 * num2;
                    break;
                case '/':
                    sum = num1 / num2;
            }
        }
        console.log('sum',sum);
        numAry = [sum];
        utilAry = [];
    }
    cal.forEach(v => {
        if(v == '+' || v == '-' || v == '*' || v == '/'){
            util = utilAry[0]
            if(!!util & level[v] < level[util]){
                toCalNow();
            }
            utilAry.unshift(v)
            
        }
        else{
            numAry.unshift(v)
        }
    });
    toCalNow();
    return numAry[0];
}
>>> console.log(calculate('12 + 2 * 2 - 1 * 2 / 2'))

队列

先进者先出
基于数组顺序队列
基于链表的链式队列

循环队列

public class CircularQueue { 
    // 数组：items，数组大小：n
    private $items = []; 
    private $n = 0;
    private $head = 0;
    private $tail = 0;

    public function CircularQueue(int capacity){
        $item = [capacity];  //长度为capacity的数组
        $this->n = capacity;
    }
    // 入队
    public function enqueue(String item){
        //队列满了
        if (($this->tail + 1) % $this->n == $this->head){
            return false;
        }
        $this->items[$this->tail] = item;
        $this->tail = ($this->tail + 1) % $this->n;
        return true;
    }
    // 出队
    public function dequeue(){
        // 如果head == tail 代表队列为空
        if($this->head == $this->tail){
            return false;
        }
        ret = $this->items[$this->head];
        $this->head = ($this->head + 1) % n ;
        return ret;
    }
}

阻塞队列

“消费者”-“生产者”模式
线程池没有空闲线程时，新的任务请求线程资源时，线程池讲新的请求放进数组队列（一定长度）阻塞等待，更多的请求拒绝。

并发队列
加锁

递归

关键：找到如何将大问题分解为小问题的规律，并且基于此写出递归公式，然后在推敲出终止条件，最后将递归公式跟终止条件翻译成代码。
警惕堆栈溢出：函数调用的时候，系统栈/虚拟机调用栈空间一般不大，如果递归求解规模很大，调用层次很深，就有可能造成堆栈溢出。
警惕重复计算：可以通过一个数据结构（如散列表）记录已经求过值f(k)数据，以避免重复计算。
警惕死循环：检查环的存在。
空间复杂度高

排序

排序算法比较

内存消耗
稳定性：稳定排序算法可以保持金额相同的两个对象，在排序之后的前后顺序保持不变。

冒泡排序 O(n^2)

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。

原地排序算法
稳定排序算法
时间复杂度：最好O(n)，最差O(n^2)，平均O(n^2)

// 冒泡排序，a 表示数组
function bubbleSort($a){
    var $n = $a.length;
    if($n<=1) return;
    for($i=0; $i<$n; $i++){
        var $flag = false;
        for ($j=0; $j<$n-$i-1; $j++){
            // 交换
            if($a[$j] > $a[$j+1]){ 
                var $tmp = $a[$j];
                $a[$j] = $a[$j+1];
                $a[$j+1] = $tmp;
                // 有数据交换，可能可以继续交换
                $flag = true;
            }
            // 如果没有交换
            if(!$flag) break;
        }
    }
    return $a;
}

插入排序 O(n^2)

插入排序

将数组中数据分为已排序空间、未排序空间，初始已排序空间只有数组第一个元素。插入排序核心算法就是取未排序空间元素，在已排序空间中找到合适的位置插入，并保证已排序空间一直有序，重复这个过程，直到未排序空间为空。
原地排序算法
稳定排序算法

时间复杂度：最好O(n)，最坏O(n^2)，平均O(n^2)

// 插入排序 $a表示数组
function insertionSort($a){
    if($a.length<=1) return;
    for(var i=1;i<$a.length;i++){
        var value = $a[i];
        var j = i-1;
        for(;j>=0;j--){
            if(value < $a[j]){
                $a[j+1] = $a[j] // 数据移动
            }
            else{
                break;
            }
        }
        $a[j+1] = value //移动完再插入数据到位置
    }
    return $a
}

选择排序 O(n^2)

选择排序

类似插入排序，有已排序空间、未排序空间，但是每次会从未排序空间选择最小的元素，插入到已排序空间的的末尾。
原地排序算法
不稳定排序算法

时间复杂度：最好O(n^2)，最坏O(n^2),平均O(n^2)

// 选择排序 $a表示数组
function selectionSort($a){
    if($a.length<=1) return;
    for(var i=0;i<$a.length;i++){
        value = i;
        for(var j=i;j<$a.length;j++){
            if($a[j]< $a[value]){ //找出最小的元素
                value = j;
            }
        }
        tmp = $a[value];
        $a.splice(value,1);  
        $a.splice(i,0,tmp);  //把最小的元素迁移到已排序的末尾
    }
    return $a
}

O(n^2)中优选插入排序

与冒泡排序对比：插入排序赋值操作更少，所以性能更优

与选择排序对比：插入排序是稳定性排序算法

// 冒泡排序
var $tmp = $a[$j];
$a[$j] = $a[$j+1];
$a[$j+1] = $tmp;

// 插入排序
$a[j+1] = $a[j] // 数据移动

归并排序 O(nlogn)

归并排序

非原地排序算法，由于合并数组需要额外申请空间。
稳定算法
时间复杂度：O(nlogn)

空间复杂度 O(n)

// 归并排序，a表示数组
function mergeSort(a){
    return mergeSort_c(a,0,a.length-1);
}
function mergeSort_c(a,p,r){
    // 一个数返回自身
    if(r == p){
        return [a[r]]
    }
    // 两个数对比返回
    if(r-p<=1){
        return concatSort([a[p]],[a[r]])
    }
    // 多个数再拆分
    else{
        var q = parseInt((p + r) / 2);
        var ary1 = mergeSort_c(a,p,q);
        var ary2 = mergeSort_c(a,q+1,r);
        return concatSort(ary1,ary2)
    }
}
// 合并方法
function concatSort(ary1,ary2){
    var tmp = [];
    while (ary1.length>0 && ary2.length>0) {
        if(ary1[0]<= ary2[0]){
            tmp.push(ary1[0]);
            ary1.splice(0,1);
        }
        else{
            tmp.push(ary2[0]);
            ary2.splice(0,1);
        }
    }
    if(ary1.length>0){
        tmp = tmp.concat(ary1);
    }
    if(ary2.length>0){
        tmp = tmp.concat(ary2);
    }
    return tmp;
}

快速排序 O(nlogn)~O(n^2)

快速排序

如果要排序数组下标p到r之间的一组数据，我们选择p到r之间任意一个数据为pivot（分区点）。遍历p到r之间的数据，将小于pivot的放在左边，大于pivot放在右边。根据分治递归的思想，可以用递归排序p到q-1之间的数据和q+1到r之间的数据，直到区间缩小为1，这样说明所有数据都是有序的。
利用快排实现O(n)找到一个数组的第K大元素。
原地排序算法
不稳定算法
时间复杂度：最好O(nlogn),最差O(n^2)

优化分区点选择：

三数取中：取头、中、尾三个数，去中间值那个数作为pivot。

随机法。

// 快速排序，A 是数组，n 表示数组的大小 
function quickSort(a){
    return quickSort_c(a,0,a.length-1);
}
function quickSort_c(a,p,r){
    if(p>=r){
        return;
    }
    // 分区
    var partition =function (p,r){
        var pivot = a[r];  // 随便选一个作为pivot
        var i = p;
        for(var j=p;j<r;j++){
            if(a[j]<pivot){
                var tmp = a[j];
                a[j] = a[i];
                a[i] = tmp;
                i++;
            }
        }
        // 交换pivot的位置，放在两个区中间
        var tmp = a[i];
        a[i] = a[r];
        a[r] = tmp;
        return i;
    }

    var q = partition(p,r); 
    quickSort_c(a,p,q-1); //整理左边
    quickSort_c(a,q+1,r); //整理右边
    return a;
}

归并排序、快速排序对比

都利用分治思想，利用迭代实现。
归并排序：从下到上，先处理子问题再合并。稳定但非原地算法。
快速排序：从上到下，先分区，再处理子问题。不稳定但是原地算法。

桶排序 O(n)

桶排序

核心思想：将要排序的数据分到几个有序的桶里，每个桶的数据再单独进行排序，排完后，再把每个桶里的数据按照顺序依次取出。
时间复杂度：O(n)
数据要求严苛：数据需要容易划分为几个桶，并且有天然的大小顺序，数据在每个桶分布需要均匀。
适合使用在外部排序（数据存储在外部磁盘，数据量大，内存有限，无法将数据全部加载到内存中）。

计数排序 O(n)

桶排序特殊情况，当数据范围不大的时候。

时间复杂度：O(n)

其中，A数组为原始数组，C数组为，下标对应分数，值为小于等于该分数的数量。

// 计数排序，a 是数组，n 是数组大小。假设数组中存储的都是非负整数。
public void countingSort(int[] a, int n) {
  if (n <= 1) return;

  // 查找数组中数据的范围
  int max = a[0];
  for (int i = 1; i < n; ++i) {
    if (max < a[i]) {
      max = a[i];
    }
  }

  int[] c = new int[max + 1]; // 申请一个计数数组 c，下标大小 [0,max]
  for (int i = 0; i <= max; ++i) {
    c[i] = 0;
  }

  // 计算每个元素的个数，放入 c 中
  for (int i = 0; i < n; ++i) {
    c[a[i]]++;
  }

  // 依次累加
  for (int i = 1; i <= max; ++i) {
    c[i] = c[i-1] + c[i];
  }

  // 临时数组 r，存储排序之后的结果
  int[] r = new int[n];
  // 计算排序的关键步骤，有点难理解
  for (int i = n - 1; i >= 0; --i) {
    int index = c[a[i]]-1;
    r[index] = a[i];
    c[a[i]]--;
  }

  // 将结果拷贝给 a 数组
  for (int i = 0; i < n; ++i) {
    a[i] = r[i];
  }
}

基数排序 O(n)

数据分割成位，按位来排序。

数据要求：可分割成独立的位，位之间有递进关系，如果a数据高位比b数据大，那剩下的都不用比较。每一位数据范围不大，要可以用线性排序算法来排序。
时间复杂度：O(n)

排序优化

排序算法对比
递归过深的堆栈溢出：限制递归深度；在堆上模拟实现函数调用栈，手动模拟递归压栈、出栈过程。
对于小规模数据（百级），O(n^2) 的排序算法并不一定比 O(nlogn) 排序算法执行时间长，可以选择简单、不需要递归的插入排序。

二分查找 O(logn)

每次都跟区间中的中间元素对比，将待查找的区间缩小一半，直到找到要找对元素，或者区间缩小为零。
时间复杂度：O(logn)

非递归实现（当数据中不存在重复数据时）

function bsearch(a,value){
    var low = 0;
    var high = a.length -1;
    // 如果low和high比较大，容易造成溢出，可以使用位运算 low+((high-low)>>1)
    var mid = parseInt(low +(high-low) /2); 
    // 注意循环退出条件有相等对情况
    while (low<=high){
        if(a[mid] == value){
            return mid;
        }
        else if(a[mid] < value){
            low = mid+1;
        }
        else{
            high = mid-1;
        }
    }
    return -1;
}

递归实现（当数据中不存在重复数据时）

function bsearch(a,value){
    return bsearchInternally(a,0,a.length-1,value);
}
function bsearchInternally(a,low,high,value){
    if(low>high) return -1;
    var mid = low+((high-low)>>1);
    if(a[mid] == value){
        return mid;
    }
    else if(a[mid] < value){
        return bsearchInternally(a,mid+1,high,value);
    }
    else{
        return bsearchInternally(a,low,mid-1,value);
    }
}

局限性

依赖顺序表结构（数组），因为数组根据下标查找是O(1)，链表是O(n)。
依赖有序数据，只适合用在一次排序，多次查找对场景。
数据量太少不适合，顺序遍历更快。但是如果数据间比较操作比较耗时，不管数据量太少，推荐使用二分查找。
数据量太大不合适，因为内存不足以存储这个数组。

二分查找变形

查找第一个值等于给定值对元素

function bsearch(a,value){
    var low = 0;
    var high = a.length -1;
    while(low<=high){
        var mid = parseInt((low+high)/2);
        if(a[mid]<value){
            low = mid+1;
        }
        else if(a[mid]>value){
            high = mid-1;
        }
        else{
            // 如果是第一个元素或者前一个元素不等于value
            if(mid == 0 || a[mid-1] != value){
                return mid
            }
            // 否则要找到的元素还在[low,high-1]区间
            else{
                high = mid -1;
            }
        }
    }
    return -1;
}

查找最后一个等于给定值的元素

function bsearch(a,value){
    var low = 0;
    var high = a.length -1;
    while(low<=high){
        var mid = parseInt((low+high)/2);
        if(a[mid]<value){
            low = mid+1;
        }
        else if(a[mid]>value){
            high = mid-1;
        }
        else{
            if(mid == a.length-1 || a[mid+1] != value){
                return mid
            }
            else{
                low = mid + 1;
            }
        }
    }
    return -1;
}

查找第一个大于等于给定值的元素

function bsearch(a,value){
    var low = 0;
    var high = a.length -1;
    while(low<=high){
        var mid = parseInt((low+high)/2);
        if(a[mid]<value){
            low = mid+1;
        }
        else{
            if(mid == 0 || a[mid-1] < value){
                return mid
            }
            else{
                high = mid - 1;
            }
        }
    }
    return -1;
}

查找最后一个小于等于给定值的元素

function bsearch(a,value){
    var low = 0;
    var high = a.length -1;
    while(low<=high){
        var mid = parseInt((low+high)/2);
        if(a[mid]>value){
            high = mid-1;
        }
        else{
            if(mid == a.length-1 || a[mid+1] > value){
                return mid
            }
            else{
                low = low + 1;
            }
        }
    }
    return -1;
}

跳表SkipList O(logn)

链表加多重索引的结构，就是跳表。空间换时间的设计思路。
时间复杂度：O(logn)
空间复杂度：O(n)
不更新索引的情况下，动态插入、删除时间复杂度也是O(logn)
更新索引：通过一个随机函数，来决定这个结点插入到哪几级索引中，比如随机函数生成K，将这个结点插入到第一级到第K级这K级索引中。
Redis中使用跳表实现有序集合，相比于红黑树，“根据区间[100,990]查到元素”的操作跳表可以做到O(logn)的时间复杂度定位区间起点，然后在起点往后遍历就可以了，效率比较高。实现比较简单。

散列表HashTable O(k)

散列表

散列表用的就是数组支持按照下标随机访问的时候，时间复杂度是O(1)的特性。通过散列函数将元素的键值映射为下标，将数据存储在数组中对应下标的位置。查询的时候，通过同样的散列函数将键值转为下标，根据下标在数组中取值。
散列函数设计的基本要求：
- 散列函数计算的散列值是个非负整数。
- 如果key1 == key2，那hash(key1) == hash(key2)
- 如果key1 != key2，那hash(key1) != hash(key2)
散列冲突：
- 开放寻址法
- 链表法，链表长度影响了散列表查询时的时间复杂度
装载因子= 填入表中元素个数/散列表的长度。装载因子越大，冲突越多，性能下降越多。
JS中Object基于哈希表，JSON只是约定的字符串格式，可以转为JavaScript的object。更多
加密中应用：哈希算法就是将任意数据转换成一定范围数据的算法，这种算法的副作用就是会产生冲突。但是在快速查找中出现的副作用，却是加密功能中的核心，因为有冲突，所以从结果就无法逆推出输入值，这样就实现了数据的单向加密。而输入数据的变化却又会影响到哈希串的值，所以我们可以用哈希串来进行数据的校验。

工业级别散列表

要求：

支持快速查询、插入、删除操作；
内存占用合理，不能浪费过多内存空间；
性能稳定，极端情况下，散列表性能不会退化到无法接受的情况

设计要点：

设计合适的散列函数：生成的值随机、分布均匀。
定义装在因子阈值，设计动态扩容策略；
避免低效（一次性）的扩容：当装载因子达到阈值时，只申请新空间，不迁移数据。当有一个新数据插入时，将新数据插入到新的散列表中，并从老数据拿出一个迁移到新散列表。迁移期间如果需要查询，先从新散列表查询，没有再从旧散列表查询。
选择合适的散列冲突解决方法；
开放寻址法：适合数据量小，装载因子小（<1)的时候。
链表法：大装在因子容忍度高，适合存储大对象（此时指针占用内存可以忽略）、大数据量。

散列表与链表结合

散列表支持非常高效插入、删除、查找，但是顺序是打乱的，没有办法按照某种顺序快速遍历，将链表结合使用可以解决这个问题。

LRU淘汰算法

散列表+双向链表存储结构，时间复杂度O(1)。
查找：散列表中时间复杂度接近O(1)，找到数据后，迁移到双向链表尾部。
删除：借助散列表，在O(1)复杂度中找到要删除的结点，双向链表通过O(1)找到前驱结点。
插入：先查找这个数据是否在缓存中，如果在，迁移到双向链表尾部，如果不在，如果缓存满了，将双向链表头部结点删除，再将数据放在双向链表尾部，如果缓存没满，直接将数据放在双向链表尾部。

Redis有序集合

散列表+跳表
按照分值将对象组织成跳表，在按键值构建一个散列表。

Java LinkedHashMap

哈希算法

要求：
- 从哈希值不能反向推导出原始数据。
- 输入的数据不同，哈希值不同。
- 散列冲突概率很小。
- 执行效率要高。
应用：
- 安全加密：MD5、SHA、DES、AES
  字典攻击：加盐
- 唯一标识：从图片二进制编码取某一些字节，进行加密，使用加密值代表这样图片的唯一标识
- 数据校验：文件切割，分别对各个文件求哈希值，用户下载完各个切割文件后，先校验哈希值是否一致，以检查文件是否被篡改/完整。
- 散列函数
区块链：区块链是一块块区块组成的，每个区块分为两部分：区块头和区块体。区块头保存着[自己区块体]和[上一个区块头]的哈希值。因为这种链式关系和哈希值的唯一性，只要区块链上任意一个区块被修改过，后面所有区块保存的哈希值就不对了。区块链使用的是 SHA256 哈希算法，计算哈希值非常耗时，如果要篡改一个区块，就必须重新计算该区块后面所有的区块的哈希值，短时间内几乎不可能做到。

哈希算法在分布式系统中应用

负载均衡
- 实现会话粘滞的负载均衡算法：通过哈希算法，将客户端ip/用户session id进行计算，将哈希值与服务器数量进行取模计算，得到的值就是服务器编号。
数据分片
- 数据量非常大的时候，将数据进行分片分开存储到n台服务器上，将数据进行哈希计算，取模，获得服务器编号。
分布式存储
- 分布式缓存：一致性哈希算法，一致性算法图解
  假设k台机器，数据范围[0~MAX]，分成m（m>>k)个区间，每个机器负责m/k个小区间。当有新机器加入的时候，将某几个小区间的数据从原来服务器迁移到新服务器中。

二叉树

概念
- 节点的高度：结点到叶子结点的最长路径
- 节点的深度：根节点到这个结点所经历边的个数
- 节点的层级：结点的深度+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: