数据结构与算法基础

Contents

1. 数组
2. 链表
3. 栈
1. 3.1. 特点
2. 3.2. 栈的应用
4. 队列
5. 递归
6. 哈希算法
7. 树
8. 排序
1. 8.1. 基于比较的排序算法
  1. 8.1.1. 如何分析一个 “排序算法”

数组

定义

数组是一种线性表数据结构。它用一组连续的空间，来存储一组具有相同类型的数据。

特点

低效的插入和删除

插入
如果向一个数组长度的为 n 的数组中的第 k 个位置插入数据，为了腾出位置，需要将k~n的数据都顺序向后移动。平均时间复杂度为 O(n).
改善方法：如果数组是有序的那么就必须安装上诉方法逐个移动然后插入，如果存储的数据无序，可以将第K个元素直接放到最后，然后把新的元素放到K的位置，这样就能减少大量的数据迁移操作。
删除
删除操作同样如此，删除第 K 个位置，为了内存的连续性，也需要搬移数据。
改善方法：
每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，再触发执行一次真正的删除。

警惕数据越界

在 C 语言中，只要不是访问受限的内存，所有的内存空间都是可以自由访问的。

ArrayList

将对数组操作的细节封装起来，支持动态扩容。如果实现能确定数组大小，可以向ArrayList指定数据大小。

适合使用数组的情况

特别关注性能的时候，可以使用数组。
如果数据大小已知，并且对数组的操作简单。

注意事项

数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。而不能说数组的查找时间复杂度为 O(1）。

链表

链表应用场景

LRU（Least Recently Used，最近最少使用）缓存淘汰策略。
常用的缓存淘汰策略：

先进先出策略（FIFO，First In First Out）
最少使用策略（LFU,Least Frequently Used）
最近最少使用策略（LRU，Least Recently Used）

如何实现一个 LRU 缓存：
维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，从链表头部开始顺序遍历链表。

如果数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的节点，并将其从原来的位置删除，然后插入到链表的头部。
如果此数据没有在缓存链表中，又可以分为两种情况：
- 如果缓存未满，则将此节点直接插入到链表的头部。
- 如果此时链表已满，则链表尾节点删除，将新的数据节点插入到链表的头部。

优化方案：使用散列表，将缓存访问的时间复杂度降到 O(1).

2.2 存储结构

不需要连续的内存空间，通过指针将一组零散的内存块串联起来使用。

2.3 链表分类

单链表
双链表
循环链表

单链表

链表通过指针将一组零散的内存块串在一起，其中每个内存块称为一个节点，每个链表的结点除了存储数据之外，还需要记录链上下一个节点的地址，将这个记录下个节点地址的指针叫做后继指针 next。在整个链表上有两个节点比较特殊，分别为第一个节点（头节点）和最后一个节点（尾节点）。其中头节点用来记录链表的基地址，通过它可以遍历其他节点；尾节点指针不指向下一个节点，而是指向一个空地址 NULL。

单链表的插入与删除

链表的插入和删除的时间复杂度为 O(1)，而随机访问的效率为O(n)，因为查询某个数据时，需要遍历所有的节点，以找到需要查找的数据。

循环链表

循环链表是一个特殊的单链表，它和单链表唯一的区别就是尾节点。循环链表的尾节点的指针指向链表的头节点。
与单链表相比，循环链表的优点就是从链尾到链头比较方便。当要处理的数据具有环形结构特点时，使用循环链表比较方便。

双链表

双向链表支持两个方向，每个节点不仅有一个后继指针 next 指向后面的节点，还有一个前驱指针 prev 指向前面的节点。

删除数据的两种情况

删除节点中 “值等于某个给定值”的节点。
不管时单链表还是双链表，为了查找到值等于给定值的节点都需要从头节点一个个遍历，直到找到给定值的节点。尽管删除操作的时间复杂读为O(1),但遍历的时间复杂度为O(n).
删除给定指针指向的节点。
这种情况，已经找到了要删除的节点，但删除某个节点，需要找到前驱节点，但单链表不支持直接获取前驱节点，所以需要通过从头遍历来找到前驱节点，时间复杂度为O(n)。但使用双链表可以直接获取到前驱节点，时间复杂度为O(1)。
插入的情况与上面类似。

查找

对于一个有序链表，双链表的按值查询效率也比单链表的高，因为可以记录上次查找的位置 p，根据要查找的值与 p 的大小关系，可以决定时往前查，还是往后查，这样一般平均只需要一般的时间。

双向循环链表

尾节点的next指针指向头节点，头节点的 prev 节点指向尾节点。

编写链表代码注意事项

理解指针和引用的含义

指针和引用，都是存储所指对象的内存地址
将某个变量赋值给指针，就是将这个变量的地址赋值给指针。或者说，指针存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

警惕指针丢失和内存泄漏

插入结点时，要注意操作顺序（比如在结点a和b之间插入结点x，要先将x的next指向a的next，也就是b；再将a的next指向x）
删除链表结点时，要记得手动释放内存空间。

利用哨兵简化实现难度

在p结点后插入新的结点：
new_node->next=p->next
p->next=new_node
如果向一个空链表插入一个结点：
if(head==null){head=new_node;}
删除结点p的后继结点:
p->next=p->next->next
如果要删除链表中的最后一个结点：
if(head->next==null){head=null;}
针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。
哨兵主要用于解决边界问题，不直接参入业务逻辑。
以上实例代码中的head，表示头结点指针，指向链表中第一个结点。head=null，表示链表中没有结点。
引入哨兵结点后，在任何情况下，不管链表是不是空，head指针都会一直指向这个哨兵结点。有哨兵结点的链表称为带头链表。哨兵结点不存储数据，因为哨兵结点一直存在，所以插入第一个结点和插入其他结点，删除最后一个结点和删除其他结点，都可以统一为相同的代码逻辑。

// 在数组 a 中，查找 key，返回 key 所在的位置
// 其中，n 表示数组 a 的长度
int find(char* a, int n, char key) {
  // 边界条件处理，如果 a 为空，或者 n<=0，说明数组中没有数据，就不用 while 循环比较了
  if(a == null || n <= 0) {
    return -1;
  }
  
  int i = 0;
  // 这里有两个比较操作：i<n 和 a[i]==key.
  while (i < n) {
    if (a[i] == key) {
      return i;
    }
    ++i;
  }
  
  return -1;
}

使用哨兵：
// 在数组 a 中，查找 key，返回 key 所在的位置
// 其中，n 表示数组 a 的长度
// 我举 2 个例子，你可以拿例子走一下代码
// a = {4, 2, 3, 5, 9, 6}  n=6 key = 7
// a = {4, 2, 3, 5, 9, 6}  n=6 key = 6
int find(char* a, int n, char key) {
  if(a == null || n <= 0) {
    return -1;
  }
  
  // 这里因为要将 a[n-1] 的值替换成 key，所以要特殊处理这个值
  if (a[n-1] == key) {
    return n-1;
  }
  
  // 把 a[n-1] 的值临时保存在变量 tmp 中，以便之后恢复。tmp=6。
  // 之所以这样做的目的是：希望 find() 代码不要改变 a 数组中的内容
  char tmp = a[n-1];
  // 把 key 的值放到 a[n-1] 中，此时 a = {4, 2, 3, 5, 9, 7}
  a[n-1] = key;
  
  int i = 0;
  // while 循环比起代码一，少了 i<n 这个比较操作
  while (a[i] != key) {//如何理解，当 i=n-1时，会退出循环
    ++i;
  }
  
  // 恢复 a[n-1] 原来的值, 此时 a= {4, 2, 3, 5, 9, 6}
  a[n-1] = tmp;
  
  if (i == n-1) {
    // 如果 i == n-1 说明，在 0...n-2 之间都没有 key，所以返回 -1
    return -1;
  } else {
    // 否则，返回 i，就是等于 key 值的元素的下标
    return i;
  }
}

重点留意边界条件处理

如果链表为空时，代码是否能正常工作？
如果链表只包含一个结点时，代码是否能正常工作？
如果链表只包含两个结点时，代码是否能正常工作？
代码逻辑在处理头结点和尾结点的时候，是否能正常工作？

练习

单链表反转
链表中环的检测
两个有序链表合并
删除链表倒数第n个结点
求链表的中间结点

栈

特点

后进者先出，先进者后出。栈是一种“操作受限”的线性表。
栈可以用数组实现，也可以用链表实现。用数组实现的栈叫顺序栈，用链表实现的栈叫链式栈。
不支持动态扩容的栈的出栈和入栈操作的时间复杂度都为 O(1),支持动态扩容的栈，出栈操作的时间复杂度尾O(1)，入栈操作由于空间不够的时候需要重新申请空间并进行数据搬移，所以最好时候的时间复杂度为 O(1)，最坏时候的时间复杂度为 O(n).采用均摊的方法，将每次数据搬移均摊到每次入栈上，可以得到，平均时间复杂度为 O(1)。

栈的应用

栈在函数调用中的应用
存储函数调用时的临时变量。
栈在表达式求值中的应用
使用两个栈，一个栈用于保存操作数，另一个栈保存运算符。从左向右遍历表达式，当遇到数字，直接压入操作数栈，遇到运算符，与运算符栈的栈顶元素比较，如果比运算符栈的栈顶元素的优先级高，就将当前运算符压入栈，如果比运算符栈的栈顶元素的优先级低或则相同，从运算符栈中取出栈顶运算符，从操作数栈的栈顶取俩个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。
在括号匹配中的应用
用栈来保存未匹配的左括号，从左到右依次扫描字符串，当扫描到左括号时，将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号，如果能匹配，则继续扫描字符串。如果扫描过程中，遇到不能匹配的右括号，或者栈中没有数据，则说明为非法格式。

队列

特点

先进先出，队列也是一种操作受限的线性表数据结构。
具有额外特性的队列：

循环队列
阻塞队列
并发队列

队列可以用数组实现，也可以用链表实现。用数组实现的队列叫顺序队列，用链表实现的队列叫链式队列。
顺序队列与链式队列实现线程池的区别：
链式队列可以实现一个支持无限排队的无界队列，但是可能会导致过多的请求排队等待，请求处理的响应时间过长，所以针对响应时间比较敏感的系统，使用链式队列来实现线程池不合适。
顺序队列，大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来时，相对更加合理。但对线程池大小的设置要合适。
顺序队列：
队列需要两个指针，一个是 head 指针，指向队头；一个是 tail 指针指向队尾。队空判断条件，head==tial；队满判断条件，tail==n。

循环队列

通过循环队列可以避免顺序队列的数据迁移操作。
代码实现关键点：
确定好对空和队满的判定条件。队空判断条件,head=tail；队满判断条件,(tail+1)%n=head。循环队列会浪费一个的存储空间，当队满时，tail 所指向的位置没有存储数据。

阻塞队列

在队列的基础上增加了阻塞操作，在队列为空时，从对头取数据会被阻塞。因为此时买没有数据可取，直到队列中有数据了才能返回。如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后返回。（如：生产者-消费者模型）

并发队列

当有多个线程同时操作队列的时候，就会存在线程安全问题，线程安全的队列别称为并发队列。基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这是循环队列比链式队列应用广泛的原因。

队列的应用场景

线程池的请求排队场景
数据库连接池

队列可以应用于任何有限资源池中，用于排队请求。对于大部分资源有限的场景，当没有空闲资源时，基本都可以通过 “队列” 这种数据结构来实现请求排队。循环队列的长度设定需要对并发数据有一定的预测，否则会丢失太多请求。
使用 CAS 可以实现无锁队列。

递归

理解递归

递归分为去的过程和回的过程，去的过程叫 “递”，回的过程叫 “归”。
递归需要满足三个条件，只有满足这三个条件的问题，才能够用递归解决。

一个问题的解可以分解为几个子问题的解。
这个问题与分解之后的问题，除了数据规模不同，求解思路完全一样。
存在递归终止条件。
把问题分解为子问题，把子问题再分解为子子问题，一层一层分解下去，不能存在无限循环，这就需要有终止条件。

如何编写递归代码

写递归代码最关键的时写出递推公式，找到终止条件。
找到递归公式后，为了找到终止条件，可以先带入一些特殊值，验证一下。由于一个问题可能会被分解为多个子问题，那么该递归公式就会有多个递归表达式组合而成，递归条件也可能不止一个。
写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。
对于递归代码，试图想清楚整个递和归的做法，是进入了一个思维误区，很多时候，理解起来比较吃力，原因是自己给自己制造了这些理解障碍。
正确的做法应该是：如果一个问题 A 可以分解为若干子问题 B、C、D，你可以假设B、C、D问题已经解决，在此基础上思考如何解决问题 A。而且，只需要思考问题 A 与子问题B、C、D两层之间的关系即可，不需要一层一层往下思考子问题与子子问题，子子问题与子子子问题的关系。屏蔽掉递归细节，这样就理解起来简单多了。
因此，编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑分解递归的每个步骤。

编写递归代码的注意事项

递归代码要警惕堆栈溢出
解决方法：在代码中限制递归调用的最大深度；当递归调用超过一定深度之后，就不继续向下调用了，直接返回报错。但这种做法并不能完全解决问题，因为最大允许的递归深度跟当前线程剩余的栈空间大小有关，事先无法计算。
递归代码要警惕重复计算
解决方法：通过一个数据结构（散列表）来保存已经求解过的f(k)，当递归调用到f(k)时，限查看一下散列表是否求解过。如果求解过直接从散列表中取出值。

递归代码改为非递归代码

递归优点：表达力强，写起来简洁。
递归缺点：空间复杂度高，有堆栈溢出风险，存在重复计算、过多函数调用会耗时较多。
规模比较大，递归层次很深的递归代码，不能使用IDE的单步调试。此时可以采用：
1. 打印日志，发现递归值
2. 结合条件断点进行调试。

哈希算法

常用的哈希算法：

MD5（MD5 Message-Digest Algorithm，MD5消息摘要算法）MD5 的哈希值是 128 位的 Bit 长度。
SHA（Secure Hash Algorithm，安全散列算法）
不管是“散列”还是“哈希”，这都是中文翻译的差别，英文都是“Hash”。

定义

将任意长度的二进制值串，映射为固定长度的二进制值串，这个映射规则就被称为哈希算法。元素数据映射之后得到的二进制值串就是哈希值。
一个优秀的哈希算法需要满足以下几点：

从哈希值不能反向推导出原始数据，（哈希算法也被称为单向哈希算法）
对输入数据非常敏感，哪怕原始数据修改了一个 Bit，最后得到的哈希值也不同。
散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小。
哈希算法执行的效率要尽量高效，针对较长的文本，也能快速的计算出哈希值。

哈希算法的应用

安全加密
最常用于加密的哈希算法时MD5和SHA。除此之外还有，
DES（Data Encryption Standard，数据加密标准）和 AES（Advanced Encryption Standand，高级加密标准）。
唯一标识
可以对众多资源进行编码，以便进行区别。例如从海量的图库中，搜索一张图片是否存在，可以对每个图片设置一个唯一标识，或者说时信息摘要。
例如：可以从图片的二进制码串中开头取100个字节，中间取100个字节，再从末尾取100个字节，然后将这300个字节放到一起通过哈希算法，得到一个哈希字符串，用它作为图片的唯一标识。通过这个唯一标识判断图片是否存在。可以进一步优化，把图片的唯一标识和相应图片文件在图库中的路径信息都存储在散列表中。这样需要的时候可以根据唯一标识直接查询散列表。
数据校验
BT下载，其原理是基于P2P协议，从多个机器中并行下载一个2GB的文件，这个文件可能被分割成很多文件块（假设为100块），等文件块都下载完成之后，再组装成一个完成的文件。由于文件再网络传输中有可能被篡改，可以通过对着100个文件块分别取哈希值，并且保存再种子文件中，当文件下载完成后，可以通过相同的哈希算法对下载好的文件块逐一求哈希值，然后和种子文件中保存的哈希值对比，如果不同，说明文件不完整或被篡改，就需要重新下载。
散列函数
散列函数对于散列算法计算得到的值，是否能贵反向解密不关心，散列函数中用到的散列算法，更多关注散列后的值是否平均分布。
负载均衡
负载均衡的算法有很多，如轮询、随机、加权轮询。可以使用哈希算法实现一个会话粘滞（session Sticky）的负载均衡算法（比如：在同一个客户端上，在一次会话中的所有请求都路由到同一个服务器上。）
可以通过哈希算法，对客户端IP地址或者会话ID计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。
数据分块
- 统计“搜索关键词”出现的次数
  对数据进行分片，然后采用多台机器来处理的方法，来提高处理速度。
  思路：用n台机器并行处理，从搜索记录的日志文件中，依次读出每个搜索关键词，并且通过哈希函数计算哈希值，然后再和n取模，最终得到的值，就是应该被分配到的机器编号。这样，哈希值相同的搜索关键词就被分配到同一个机器上，即同一个搜索关键词被分配到同一个机器上。
- 快速判断图片是否在图库中
  针对海量数据的处理问题，都可以采用多机分布式处理，借助这种分片处理的思路，可以突破单机内存、CPU等资源的限制。
分布式存储
为了提高数据的读取、写入能力，一般都采用分布式的方式来存储数据，如分布式缓存。针对海量的数据需要缓存，一个缓存机器肯定不够，需要将数据分布在多台机器上。通过哈希算法来决定哪个数据将要放到哪个机器上。同样采用，对数据取哈希值，然后对机器个数取模，这个最终值就是应该存储缓存的机器的编号 。如果再对机器进行扩容，就需要重新计算哈希值，重新计算每个数据应该存储到的机器。所以需要一种方法，使得再新加入一个机器后，并不需要做大量的数据搬移，这时就需要使用一致性哈希算法。
一致性算法的简单描述:
假设有K个机器，数据的哈希值的范围是[0，MAX]，可以将整个区间划分为 m 个小区间（m 远大于 k），每个机器负责 m/k 个小区间。当有新机器加入时，我们就将某几个小区间的数据，从原来的机器中搬移到新的机器中，这样就避免了重新哈希、搬移数据，也保证了各个机器上数据量的均衡。
在分布式应用中，利用一致性哈希算法，可以解决缓存等分布式系统的扩容、缩容导致数据量搬移的难题。
其他的应用还有，网络中CRC校验，git commit id 等

如何保证密码的安全

维护一个常用密码的字典表，把字典中的每个密码用哈希算法计算出哈希值，然后拿哈希值与脱库后的密文对比，如果相同可以认为这个加密之后的密码对应的明文就是字典中的这个密码。针对字典攻击，可以引入 盐（salt），和用户的密码组合在一起，增加密码的复杂度。

树

关于数的几个概念

高度、深度、层：

节点的高度=节点到叶子节点的最长路径（边数）
节点的深度=根节点到这个节点所经历的边的个数
节点的层数=节点的深度 + 1
树的高度=根节点的高度

理解高度与深度的技巧：
“高度”可以看作从下往上度量。（楼的高度）
“深度”可以看作从上往下度量。（海的深度）
两者的计数的起点都是0。

二叉树

满二叉树
除了叶子节点外，每个节点都有左右两个子节点。
完全二叉树
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边。
1. 所有的叶结点都出现在第k层或k-l层（层次最大的两层）
2. 对任一结点，如果其右子树的最大层次为L，则其左子树的最大层次为L或L+l。

二叉树的存储方式

链式存储
基于指针或引用的二叉链式存储法。每个节点有三个字段，其中一个存储数据，另外两个时指向左右节点的指针。大部分二叉树代码都是通过这种结构实现的。
顺序存储
基于数组的顺序存储法。根节点存储在 i=1 的位置，左子节点存储在下标 2 * i=2 的位置，右节点存储在 2 * i+1=3 的位置，以此类推。对于完全二叉树采用顺序存储方式会比较高效，只会浪费下标为 0 的位置，如果是非完全二叉树，则比较浪费数组的存储空间。这也是要求完全二叉树最后一层的子节点靠左的原因。

二叉树的遍历

二叉树有三种遍历方式，分别为前序遍历，中序遍历和后序遍历。这里的前、中、后，表示的是节点与它的左右子树节点遍历打印的先后顺序。

前序遍历
当前节点 –> 当前节点的左子树 –> 当前节点的右子树
中序遍历
当前节点的左子树 –> 当前节点 –> 当前节点的右子树
后续遍历
当前节点的左子树 –> 当前节点的右子树 –> 当前节点

二叉树的前、中、后序遍历就是一个递归的过程。
二叉树遍历递归实现的递推公式：
前序遍历
preOrder(r)=print r->preOrder(r->left)->preOrder(r->right)
中序遍历
inOrder(r=inOrder(r->left)->print r->inOrder(r->right)
后续遍历
postOrder(r)=postOrder(r->left)->postOrder(r->right)->print r
实现

//前序遍历伪代码，中、后遍历与以下代码类型，只是代码的先后顺序不同
void preOrder(Node* root)
{
    if(root==null)return;
    
    print root;
    preOrder(root->left);
    preOrder(root->right);
}

前、中、后序遍历的复杂度：
这三种遍历的时间复杂度都为O(n)。

二叉查找树（二叉搜索树、二叉排序树）

二叉树的最大特点是，支持数据集合的快速插入、删除、查找操作。散列表也支持这些操作，而且散列表的这些操作比二叉树更高效。时间复杂度为O(1)。
二叉查找树是为了实现快速查找而存在的。二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树的节点的值都要大于这个节点的值。

二叉查找树的查找操作

取根节点，如果它等于要查找的数据，就返回。
如果查找的数据比根节点的值小，就在左子树中递归查找

如果查找的数据比根节点的值大，就在右子树中递归查找。

public class BinarySearchTree {
  private Node tree;

  public Node find(int data) {
    Node p = tree;
    while (p != null) {
      if (data < p.data) p = p.left;
      else if (data > p.data) p = p.right;
      else return p;
    }
    return null;
  }

  public static class Node {
    private int data;
    private Node left;
    private Node right;

    public Node(int data) {
      this.data = data;
    }
  }
}

二叉查找树的插入操作
二叉查找树的插入过程与查找操作类似。

如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。

如果要插入的数据比节点的数据小，并且节点的左子树为空，就将新数据直接插到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。

public void insert(int data) {
  if (tree == null) {
    tree = new Node(data);
    return;
  }

  Node p = tree;
  while (p != null) {
    if (data > p.data) {
      if (p.right == null) {
        p.right = new Node(data);
        return;
      }
      p = p.right;
    } else { // data < p.data
      if (p.left == null) {
        p.left = new Node(data);
        return;
      }
      p = p.left;
    }
  }
}

二叉查找树的删除操作有三种情况：

如果要删除的节点没有子节点，只需要直接将父节点中，指向删除节点的指针置为null。
如果要删除的节点只有一个子节点（只有左子节点或右子节点），只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。

如果要删除的节点有两个子节点。首先需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上，然后再删除掉这个最小节点。因为最小节点肯定没有左子节点（有左子节点，就不是最小的了），最后应用上面的2个规则删除节点。

public void delete(int data) {
  Node p = tree; // p 指向要删除的节点，初始化指向根节点
  Node pp = null; // pp 记录的是 p 的父节点
  while (p != null && p.data != data) {
    pp = p;
    if (data > p.data) p = p.right;
    else p = p.left;
  }
  if (p == null) return; // 没有找到

  // 要删除的节点有两个子节点
  if (p.left != null && p.right != null) { // 查找右子树中最小节点
    Node minP = p.right;
    Node minPP = p; // minPP 表示 minP 的父节点
    while (minP.left != null) {
      minPP = minP;
      minP = minP.left;
    }
    p.data = minP.data; // 将 minP 的数据替换到 p 中
    p = minP; // 下面就变成了删除 minP 了
    pp = minPP;
  }

  // 删除节点是叶子节点或者仅有一个子节点
  Node child; // p 的子节点
  if (p.left != null) child = p.left;
  else if (p.right != null) child = p.right;
  else child = null;

  if (pp == null) tree = child; // 删除的是根节点
  else if (pp.left == p) pp.left = child;
  else pp.right = child;
}

其他操作
1. 快速查找最大节点和最小节点、前驱节点和后继节点。
2. 中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度为O(n).
时间复杂度
二叉查找树的插入、删除和查找的时间复杂度都和树的高度成正比，也就是O(height)（理想情况下为O(logn)）。

平衡二叉查找树

平衡二叉查找树的初衷，是为了解决二叉查找树因为动态更新导致的性能退化问题。

动态数据结构

动态数据结构支持动态的更行操作，里面存储的数据时时刻变化的，即不仅仅支持查询，还支持删除、插入数据。而且操作都比较高效。如果不高效，就算不上时有效的动态数据结构了。
链表、队列和栈都算不上是动态是动态数据结构，因为他们的操作非常有限，查询效率不高。
动态的数据结构有：

散列表
删除、插入和查询时间复杂度都为O(1)。但不能顺序遍历，扩容，缩容新年损耗。
跳表
删除、插入和查询时间复杂度都为O(logn)。但空间复杂度太高，为O(n)。
红黑树
删除、插入和查询时间复杂度都为O(logn)。中序遍历为有序序列。但难以实现。

排序

基于比较的排序算法

基于比较的排序算法的执行过程，涉及两种操作，一种是元素比较大小，另一种是元素交换移动。

如何分析一个 “排序算法”

排序算法的执行效率
1. 最好情况、最坏情况、平均情况时间复杂度
2. 时间复杂度的系数、常熟、低阶
3. 比较次数和交换（或移动）次数
排序算法的内存消耗
原地排序
排序算法的稳定性

数组

定义

特点

低效的 插入 和 删除