神族九帝's blog
wu529778790
2022-04-21

计算机基础

【腾讯文档】4、第四部分：计算机基础(14 题).

# 1. 网络

# 1.1 udp

# ⾯向报⽂

UDP 是⼀个⾯向报⽂（报⽂可以理解为⼀段段的数据）的协议。意思就是 UDP 只是报⽂的搬运⼯，不会对报⽂进⾏任何拆分和拼接操作

具体来说

  • 在发送端，应⽤层将数据传递给传输层的 UDP 协议， UDP 只会给数据增加⼀个 UDP 头标识下是 UDP 协议，然后就传递给⽹络层了
  • 在接收端，⽹络层将数据传递给传输层， UDP 只去除 IP 报⽂头就传递给应⽤层，不会任何拼接操作

# 不可靠性

  • UDP 是⽆连接的，也就是说通信不需要建⽴和断开连接。
  • UDP 也是不可靠的。协议收到什么数据就传递什么数据，并且也不会备份数据，对⽅能不能收到是不关⼼的
  • UDP 没有拥塞控制，⼀直会以恒定的速度发送数据。即使⽹络条件不好，也不会对发送速率进⾏调整。这样实现的弊端就是在⽹络条件不好的情况下可能会导致丢包，但是优点也很明显，在某些实时性要求⾼的场景（⽐如电话会议）就需要使⽤ UDP ⽽不是 TCP

# 高效

  • 因为 UDP 没有 TCP 那么复杂，需要保证数据不丢失且有序到达。所以 UDP 的头部开销⼩，只有⼋字节，相⽐ TCP 的⾄少⼆⼗字节要少得多，在传输数据报⽂时是很⾼效的

头部包含了以下⼏个数据

  • 两个⼗六位的端⼝号，分别为源端⼝（可选字段）和⽬标端⼝ 整个数据报⽂的⻓度
  • 整个数据报⽂的检验和（ IPv4 可选 字段），该字段⽤于发现头部信息和数据中的错误

# 传输⽅式

UDP 不⽌⽀持⼀对⼀的传输⽅式，同样⽀持⼀对多，多对多，多对⼀的⽅式，也就是说 UDP 提供了单播，多播，⼴播的功能

# 1.2 TCP

# 头部

TCP 头部⽐ UDP 头部复杂的多 对于 TCP 头部来说，以下⼏个字段是很重要的

  • Sequence number ，这个序号保证了 TCP 传输的报⽂都是有序的，对端可以通过序号顺序的拼接报⽂
  • Acknowledgement Number ，这个序号表示数据接收端期望接收的下⼀个字节的编号是多少，同时也表示上⼀个序号的数据已经收到
  • Window Size ，窗⼝⼤⼩，表示还能接收多少字节的数据，⽤于流量控制标识符 URG=1 ：该字段为⼀表示本数据报的数据部分包含紧急信息，是⼀个⾼优先级数据报⽂，此时紧急指针有效。紧急数据⼀定位于当前数据包数据部分的最前⾯，紧急指针标明了紧急数据的尾部。
  • ACK=1 ：该字段为⼀表示确认号字段有效。此外， TCP 还规定在连接建⽴后传送的所有报⽂段都必须把 ACK 置为⼀ PSH=1 ：该字段为⼀表示接收端应该⽴即将数据 push 给应⽤层，⽽不是等到缓冲区满后再提交。
  • RST=1 ：该字段为⼀表示当前 TCP 连接出现严重问题，可能需要重新建⽴ TCP 连接，也可以⽤于拒绝⾮法的报⽂段和拒绝连接请求。
  • SYN=1 ：当 SYN=1 ， ACK=0 时，表示当前报⽂段是⼀个连接请求报⽂。当 SYN=1 ，ACK=1 时，表示当前报⽂段是⼀个同意建⽴连接的应答报⽂。
  • FIN=1 ：该字段为⼀表示此报⽂段是⼀个释放连接的请求报⽂

# 状态机

HTTP 是⽆连接的，所以作为下层的 TCP 协议也是⽆连接的，虽然看似 TCP 将两端连接了起来，但是其实只是两端共同维护了⼀个状态

  • TCP 的状态机是很复杂的，并且与建⽴断开连接时的握⼿息息相关，接下来就来详细描述下两种握⼿。
  • 在这之前需要了解⼀个重要的性能指标 RTT。该指标表示发送端发送数据到接收到对端数据所需的往返时间

# 建⽴连接三次握⼿

  • 在 TCP 协议中，主动发起请求的⼀端为客户端，被动连接的⼀端称为服务端。不管是客户端还是服务端， TCP 连接建⽴完后都能发送和接收数据，所以 TCP 也是⼀个全双⼯的协议。
  • 起初，两端都为 CLOSED 状态。在通信开始前，双⽅都会创建 TCB 。 服务器创建完 TCB 后遍进⼊ LISTEN 状态，此时开始等待客户端发送数据
# 第⼀次握⼿

客户端向服务端发送连接请求报⽂段。该报⽂段中包含⾃身的数据通讯初始序号。请求发送后，客户端便进⼊ SYN-SENT 状态，x 表示客户端的数据通信初始序号。

# 第二次握手

服务端收到连接请求报⽂段后，如果同意连接，则会发送⼀个应答，该应答中也会包含⾃身的数据通讯初始序号，发送完成后便进⼊ SYN-RECEIVED 状态。

# 第三次握手

当客户端收到连接同意的应答后，还要向服务端发送⼀个确认报⽂。客户端发完这个报⽂段后便进⼊ ESTABLISHED 状态，服务端收到这个应答后也进⼊ ESTABLISHED 状态，此时连接建⽴成功。

  • PS：第三次握⼿可以包含数据，通过 TCP 快速打开（ TFO ）技术。其实只要涉及到握⼿的协议，都可以使⽤类似 TFO 的⽅式，客户端和服务端存储相同 cookie ，下次握⼿时发出 cookie 达到减少 RTT 的⽬的

# 你是否有疑惑明明两次握⼿就可以建⽴起连接，为什么还需要第三次应答？

  • 因为这是为了防⽌失效的连接请求报⽂段被服务端接收，从⽽产⽣错误

可以想象如下场景。客户端发送了⼀个连接请求 A，但是因为⽹络原因造成了超时，这时 TCP 会启动超时重传的机制再次发送⼀个连接请求 B。此时请求顺利到达服务端，服务端应答完就建⽴了请求。如果连接请求 A 在两端关闭后终于抵达了服务端，那么这时服务端会认为客户端⼜需要建⽴ TCP 连接，从⽽应答了该请求并进⼊ ESTABLISHED 状态。此时客户端其实是 CLOSED 状态，那么就会导致服务端⼀直等待，造成资源的浪费

PS：在建⽴连接中，任意⼀端掉线，TCP 都会重发 SYN 包，⼀般会重试五次，在建⽴连接中可能会遇到 SYN FLOOD 攻击。遇到这种情况你可以选择调低重试次数或者⼲脆在不能处理的情况下拒绝请求

# 断开链接四次握⼿

TCP 是全双⼯的，在断开连接时两端都需要发送 FIN 和 ACK 。

# 1. 第⼀次握⼿

若客户端 A 认为数据发送完成，则它需要向服务端 B 发送连接释放请求。

# 2. 第⼆次握⼿

B 收到连接释放请求后，会告诉应⽤层要释放 TCP 链接。然后会发送 ACK 包，并进⼊ CLOSE_WAIT 状态，表示 A 到 B 的连接已经释放，不接收 A 发的数据了。但是因为 TCP 连接时双向的，所以 B 仍旧可以发送数据给 A。

# 3. 第三次握⼿

B 如果此时还有没发完的数据会继续发送，完毕后会向 A 发送连接释放请求，然后 B 便进⼊ LAST-ACK 状态。

PS：通过延迟确认的技术（通常有时间限制，否则对⽅会误认为需要重传），可以将第⼆次和第三次握⼿合并，延迟 ACK 包的发送。

# 4. 第四次握⼿
  • A 收到释放请求后，向 B 发送确认应答，此时 A 进⼊ TIME-WAIT 状态。该状态会持续 2MSL（最⼤段⽣存期，指报⽂段在⽹络中⽣存的时间，超时会被抛弃） 时间，若该时间段内没有 B 的重发请求的话，就进⼊ CLOSED 状态。当 B 收到确认应答后，也便进⼊ CLOSED 状态。

为什么 A 要进⼊ TIME-WAIT 状态，等待 2MSL 时间后才进⼊ CLOSED 状态？

  • 为了保证 B 能收到 A 的确认应答。若 A 发完确认应答后直接进⼊ CLOSED 状态，如果确认应答因为⽹络问题⼀直没有到达，那么会造成 B 不能正常关闭

# 1.3 HTTP

HTTP 协议是个⽆状态协议，不会保存状态

# 3.1 Post 和 Get 的区别

  • Get 请求能缓存， Post 不能
  • Post 相对 Get 安全⼀点点，因为 Get 请求都包含在 URL ⾥，且会被浏览器保存历史纪录， Post 不会，但是在抓包的情况下都是⼀样的。
  • Post 可以通过 request body 来传输⽐ Get 更多的数据， Get 没有这个技术
  • URL 有⻓度限制，会影响 Get 请求，但是这个⻓度限制是浏览器规定的，不是 RFC 规定的
  • Post ⽀持更多的编码类型且不对数据类型限制

# 3.2 常⻅状态码

# 2XX 成功
  • 200 OK ，表示从客户端发来的请求在服务器端被正确处理
  • 204 No content ，表示请求成功，但响应报⽂不含实体的主体部分
  • 205 Reset Content ，表示请求成功，但响应报⽂不含实体的主体部分，但是与 204 响应不同在于要求请求⽅重置内容
  • 206 Partial Content ，进⾏范围请求
# 3XX 重定向
  • 301 moved permanently ，永久性重定向，表示资源已被分配了新的 URL
  • 302 found ，临时性重定向，表示资源临时被分配了新的 URL
  • 303 see other ，表示资源存在着另⼀个 URL，应使⽤ GET ⽅法丁⾹获取资源
  • 304 not modified ，表示服务器允许访问资源，但因发⽣请求未满⾜条件的情况
  • 307 temporary redirect ，临时重定向，和 302 含义类似，但是期望客户端保持请求⽅法不变向新的地址发出请求
# 4XX 客户端错误
  • 400 bad request ，请求报⽂存在语法错误
  • 401 unauthorized ，表示发送的请求需要有通过 HTTP 认证的认证信息
  • 403 forbidden ，表示对请求资源的访问被服务器拒绝
  • 404 not found ，表示在服务器上没有找到请求的资源
# 5XX 服务器错误
  • 500 internal sever error ，表示服务器端在执⾏请求时发⽣了错误
  • 501 Not Implemented ，表示服务器不⽀持当前请求所需要的某个功能
  • 503 service unavailable ，表明服务器暂时处于超负载或正在停机维护，⽆法处理请求

# 3.3 HTTP 首部

通⽤字段 作⽤
Cache-Control 控制缓存的⾏为
Connection 浏览器想要优先使⽤的连接类型，⽐如 keep-alive
Date 创建报⽂时间
Pragma 报⽂指令
Via 代理服务器相关信息
Transfer-Encoding 传输编码⽅式
Upgrade 要求客户端升级协议
Warning 在内容中可能存在错误
请求字段 作⽤
Accept 能正确接收的媒体类型
Accept-Charset 能正确接收的字符集
Accept-Encoding 能正确接收的编码格式列表
Accept-Language 能正确接收的语⾔列表
Expect 期待服务端的指定⾏为
From 请求⽅邮箱地址
Host 服务器的域名
If-Match 两端资源标记⽐较
If-Modified-Since 本地资源未修改返回 304（⽐较时间）
If-None-Match 本地资源未修改返回 304（⽐较标记）
User-Agent 客户端信息
Max-Forwards 限制可被代理及⽹关转发的次数
Proxy-Authorization 向代理服务器发送验证信息
Range 请求某个内容的⼀部分
Referer 表示浏览器所访问的前⼀个⻚⾯
TE 传输编码⽅式
响应字段 作⽤
Accept-Ranges 是否⽀持某些种类的范围
Age 资源在代理缓存中存在的时间
ETag 资源标识
Location 客户端重定向到某个 URL
Proxy-Authenticate 向代理服务器发送验证信息
Server 服务器名字
WWW-Authenticate 获取资源需要的验证信息
实体字段 作⽤
Allow 资源的正确请求⽅式
Content-Encoding 内容的编码格式
Content-Language 内容使⽤的语⾔
Content-Length request body ⻓度
Content-Location 返回数据的备⽤地址
Content-MD5 Base64 加密格式的内容 MD5 检验值
Content-Range 内容的位置范围
Content-Type 内容的媒体类型
Expires 内容的过期时间
Last_modified 内容的最后修改时间

# 1.4 DNS

DNS 的作⽤就是通过域名查询到具体的 IP。

  • 因为 IP 存在数字和英⽂的组合（IPv6），很不利于⼈类记忆，所以就出现了域名。你可以把域名看成是某个 IP 的别名，DNS 就是去查询这个别名的真正名称是什么

在 TCP 握⼿之前就已经进⾏了 DNS 查询，这个查询是操作系统⾃⼰做的。当你在浏览器中想访问 www.google.com 时，会进⾏⼀下操作

  • 操作系统会⾸先在本地缓存中查询
  • 没有的话会去系统配置的 DNS 服务器中查询
  • 如果这时候还没得话，会直接去 DNS 根服务器查询，这⼀步查询会找出负责 com 这个⼀级域名的服务器
  • 然后去该服务器查询 google 这个⼆级域名
  • 接下来三级域名的查询其实是我们配置的，你可以给 www 这个域名配置⼀个 IP，然后还可以给别的三级域名配置⼀个 IP

以上介绍的是 DNS 迭代查询，还有种是递归查询，区别就是前者是由客户端去做请求，后者是由系统配置的 DNS 服务器做请求，得到结果后将数据返回给客户端。

# 2. 数据结构

# 2.1 栈

# 概念

栈是⼀个线性结构，在计算机中是⼀个相当常⻅的数据结构。 栈的特点是只能在某⼀端添加或删除数据，遵循先进后出的原则

# 实现

每种数据结构都可以⽤很多种⽅式来实现，其实可以把栈看成是数组的⼀个⼦集，所以这⾥使⽤数组来实现

class Stack {
  constructor() {
    this.stack = [];
  }
  push(item) {
    this.stack.push(item);
  }
  pop() {
    this.stack.pop();
  }
  peek() {
    return this.stack[this.getCount() - 1];
  }
  getCount() {
    return this.stack.length;
  }
  isEmpty() {
    return this.getCount() === 0;
  }
}

# 应用

匹配括号，可以通过栈的特性来完成

var isValid = function (s) {
  let map = {
    "(": -1,
    ")": 1,
    "[": -2,
    "]": 2,
    "{": -3,
    "}": 3,
  };
  let stack = [];
  for (let i = 0; i < s.length; i++) {
    if (map[s[i]] < 0) {
      stack.push(s[i]);
    } else {
      let last = stack.pop();
      if (map[last] + map[s[i]] != 0) return false;
    }
  }
  if (stack.length > 0) return false;
  return true;
};

这个可以看算法： https://blog.shenzjd.com/pages/9eaae444f0d5b/#有效括号 (opens new window)

# 2.2 队列

# 2.2.1 概念

队列⼀个线性结构，特点是在某⼀端添加数据，在另⼀端删除数据，遵循先进先出的原则

# 2.2.2 实现

这⾥会讲解两种实现队列的⽅式，分别是单链队列和循环队列

  • 单链队列
class Queue {
  constructor() {
    this.queue = [];
  }
  enQueue(item) {
    this.queue.push(item);
  }
  deQueue() {
    return this.queue.shift();
  }
  getHeader() {
    return this.queue[0];
  }
  getLength() {
    return this.queue.length;
  }
  isEmpty() {
    return this.getLength() === 0;
  }
}

因为单链队列在出队操作的时候需要 O(n) 的时间复杂度，所以引⼊了循环队列。循环队列的出队操作平均是 O(1) 的时间复杂度

  • 循环队列
class SqQueue {
  constructor(length) {
    this.queue = new Array(length + 1);
    // 队头
    this.first = 0;
    // 队尾
    this.last = 0;
    // 当前队列⼤⼩
    this.size = 0;
  }
  enQueue(item) {
    // 判断队尾 + 1 是否为队头
    // 如果是就代表需要扩容数组
    // % this.queue.length 是为了防⽌数组越界
    if (this.first === (this.last + 1) % this.queue.length) {
      this.resize(this.getLength() * 2 + 1);
    }
    this.queue[this.last] = item;
    this.size++;
    this.last = (this.last + 1) % this.queue.length;
  }
  deQueue() {
    if (this.isEmpty()) {
      throw Error("Queue is empty");
    }
    let r = this.queue[this.first];
    this.queue[this.first] = null;
    this.first = (this.first + 1) % this.queue.length;
    this.size--;
    // 判断当前队列⼤⼩是否过⼩
    // 为了保证不浪费空间，在队列空间等于总⻓度四分之⼀时
    // 且不为 2 时缩⼩总⻓度为当前的⼀半
    if (this.size === this.getLength() / 4 && this.getLength() / 2 !== 0) {
      this.resize(this.getLength() / 2);
    }
    return r;
  }
  getHeader() {
    if (this.isEmpty()) {
      throw Error("Queue is empty");
    }
    return this.queue[this.first];
  }
  getLength() {
    return this.queue.length - 1;
  }
  isEmpty() {
    return this.first === this.last;
  }
  resize(length) {
    let q = new Array(length);
    for (let i = 0; i < length; i++) {
      q[i] = this.queue[(i + this.first) % this.queue.length];
    }
    this.queue = q;
    this.first = 0;
    this.last = this.size;
  }
}

# 2.3 链表

# 2.3.1 概念

链表是⼀个线性结构，同时也是⼀个天然的递归结构。链表结构可以充分利⽤计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销⽐较⼤

# 2.3.2 实现

  • 单项链表
class Node {
  constructor(v, next) {
    this.value = v;
    this.next = next;
  }
}
class LinkList {
  constructor() {
    // 链表⻓度
    this.size = 0;
    // 虚拟头部
    this.dummyNode = new Node(null, null);
  }
  find(header, index, currentIndex) {
    if (index === currentIndex) return header;
    return this.find(header.next, index, currentIndex + 1);
  }
  addNode(v, index) {
    this.checkIndex(index);
    // 当往链表末尾插⼊时，prev.next 为空
    // 其他情况时，因为要插⼊节点，所以插⼊的节点
    // 的 next 应该是 prev.next
    // 然后设置 prev.next 为插⼊的节点
    let prev = this.find(this.dummyNode, index, 0);
    prev.next = new Node(v, prev.next);
    this.size++;
    return prev.next;
  }
  insertNode(v, index) {
    return this.addNode(v, index);
  }
  addToFirst(v) {
    return this.addNode(v, 0);
  }
  addToLast(v) {
    return this.addNode(v, this.size);
  }
  removeNode(index, isLast) {
    this.checkIndex(index);
    index = isLast ? index - 1 : index;
    let prev = this.find(this.dummyNode, index, 0);
    let node = prev.next;
    prev.next = node.next;
    node.next = null;
    this.size--;
    return node;
  }
  removeFirstNode() {
    return this.removeNode(0);
  }
  removeLastNode() {
    return this.removeNode(this.size, true);
  }
  checkIndex(index) {
    if (index < 0 || index > this.size) throw Error("Index error");
  }
  getNode(index) {
    this.checkIndex(index);
    if (this.isEmpty()) return;
    return this.find(this.dummyNode, index, 0).next;
  }
  isEmpty() {
    return this.size === 0;
  }
  getSize() {
    return this.size;
  }
}

# 2.4 树

# 2.4.1 二叉树

  • 树拥有很多种结构，⼆叉树是树中最常⽤的结构，同时也是⼀个天然的递归结构。
  • ⼆叉树拥有⼀个根节点，每个节点⾄多拥有两个⼦节点，分别为：左节点和右节点。树的最底部节点称之为叶节点，当⼀颗树的叶数量数量为满时，该树可以称之为满⼆叉树

# 2.4.2 二叉搜索树

  • ⼆分搜索树也是⼆叉树，拥有⼆叉树的特性。但是区别在于⼆分搜索树每个节点的值都⽐他的左⼦树的值⼤，⽐右⼦树的值⼩
  • 这种存储⽅式很适合于数据搜索。如下图所示，当需要查找 6 的时候，因为需要查找的值⽐根节点的值⼤，所以只需要在根节点的右⼦树上寻找，⼤⼤提⾼了搜索效率

# 2.4.3 实现

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
class BST {
  constructor() {
    this.root = null;
    this.size = 0;
  }
  getSize() {
    return this.size;
  }
  isEmpty() {
    return this.size === 0;
  }
  addNode(v) {
    this.root = this._addChild(this.root, v);
  }
  // 添加节点时，需要⽐较添加的节点值和当前
  // 节点值的⼤⼩
  _addChild(node, v) {
    if (!node) {
      this.size++;
      return new Node(v);
    }
    if (node.value > v) {
      node.left = this._addChild(node.left, v);
    } else if (node.value < v) {
      node.right = this._addChild(node.right, v);
    }
    return node;
  }
}
  • 以上是最基本的⼆分搜索树实现，接下来实现树的遍历。

对于树的遍历来说，有三种遍历⽅法，分别是先序遍历、中序遍历、后序遍历。三种遍历的区别在于何时访问节点。在遍历树的过程中，每个节点都会遍历三次，分别是遍历到⾃⼰，遍历左⼦树和遍历右⼦树。如果需要实现先序遍历，那么只需要第⼀次遍历到节点时进⾏操作即可

// 先序遍历可⽤于打印树的结构
// 先序遍历先访问根节点，然后访问左节点，最后访问右节点。
preTraversal() {
 this._pre(this.root)
}
_pre(node) {
 if (node) {
  console.log(node.value)
  this._pre(node.left)
  this._pre(node.right)
 }
}
// 中序遍历可⽤于排序
// 对于 BST 来说，中序遍历可以实现⼀次遍历就
// 得到有序的值
// 中序遍历表示先访问左节点，然后访问根节点，最后访问右节点。
midTraversal() {
 this._mid(this.root)
}
_mid(node) {
  if (node) {
    this._mid(node.left)
    console.log(node.value)
    this._mid(node.right)
  }
}
// 后序遍历可⽤于先操作⼦节点
// 再操作⽗节点的场景
// 后序遍历表示先访问左节点，然后访问右节点，最后访问根节点。
backTraversal() {
 this._back(this.root)
}
_back(node) {
 if (node) {
  this._back(node.left)
  this._back(node.right)
  console.log(node.value)
 }
}

以上的这⼏种遍历都可以称之为深度遍历，对应的还有种遍历叫做⼴度遍历，也就是⼀层层地遍历树。对于⼴度遍历来说，我们需要利⽤之前讲过的队列结构来完成

breadthTraversal() {
 if (!this.root) return null
 let q = new Queue()
 // 将根节点⼊队
 q.enQueue(this.root)
 // 循环判断队列是否为空，为空
 // 代表树遍历完毕
 while (!q.isEmpty()) {
 // 将队⾸出队，判断是否有左右⼦树
 // 有的话，就先左后右⼊队
 let n = q.deQueue()
 console.log(n.value)
 if (n.left) q.enQueue(n.left)
 if (n.right) q.enQueue(n.right)
 }
}

接下来先介绍如何在树中寻找最⼩值或最⼤数。因为⼆分搜索树的特性，所以最⼩值⼀定在根节点的最左边，最⼤值相反

getMin() {
 return this._getMin(this.root).value
}
_getMin(node) {
 if (!node.left) return node
 return this._getMin(node.left)
}
getMax() {
 return this._getMax(this.root).value
}
_getMax(node) {
 if (!node.right) return node
 return this._getMin(node.right)
}

向上取整和向下取整，这两个操作是相反的，所以代码也是类似的，这⾥只介绍如何向下取整。既然是向下取整，那么根据⼆分搜索树的特性，值⼀定在根节点的左侧。只需要⼀直遍历左⼦树直到当前节点的值不再⼤于等于需要的值，然后判断节点是否还拥有右⼦树。如果有的话，继续上⾯的递归判断

floor(v) {
 let node = this._floor(this.root, v)
 return node ? node.value : null
}
_floor(node, v) {
 if (!node) return null
 if (node.value === v) return v
 // 如果当前节点值还⽐需要的值⼤，就继续递归
 if (node.value > v) {
 return this._floor(node.left, v)
 }
 // 判断当前节点是否拥有右⼦树
 let right = this._floor(node.right, v)
 if (right) return right
 return node
}

排名，这是⽤于获取给定值的排名或者排名第⼏的节点的值，这两个操作也是相反的，所以这个只介绍如何获取排名第⼏的节点的值。对于这个操作⽽⾔，我们需要略微的改造点代码，让每个节点拥有⼀个 size 属性。该属性表示该节点下有多少⼦节点（包含⾃身）

class Node {
 constructor(value) {
 this.value = value
 this.left = null
 this.right = null
 // 修改代码
 this.size = 1
 }
}
// 新增代码
_getSize(node) {
 return node ? node.size : 0
}
_addChild(node, v) {
 if (!node) {
 return new Node(v)
 }
 if (node.value > v) {
 // 修改代码
 node.size++
 node.left = this._addChild(node.left, v)
 } else if (node.value < v) {
 // 修改代码
 node.size++
 node.right = this._addChild(node.right, v)
 }
 return node
}
select(k) {
 let node = this._select(this.root, k)
 return node ? node.value : null
}
_select(node, k) {
 if (!node) return null
 // 先获取左⼦树下有⼏个节点
 let size = node.left ? node.left.size : 0
 // 判断 size 是否⼤于 k
 // 如果⼤于 k，代表所需要的节点在左节点
 if (size > k) return this._select(node.left, k)
 // 如果⼩于 k，代表所需要的节点在右节点
// 注意这⾥需要重新计算 k，减去根节点除了右⼦树的节点数量
 if (size < k) return this._select(node.right, k - size - 1)
 return node
}

接下来讲解的是⼆分搜索树中最难实现的部分：删除节点。因为对于删除节点来说，会存在以下⼏种情况

  • 需要删除的节点没有⼦树
  • 需要删除的节点只有⼀条⼦树
  • 需要删除的节点有左右两条树
  • 对于前两种情况很好解决，但是第三种情况就有难度了，所以先来实现相对简单的操作：
  • 删除最⼩节点，对于删除最⼩节点来说，是不存在第三种情况的，删除最⼤节点操作是和
  • 删除最⼩节点相反的，所以这⾥也就不再赘述
delectMin() {
 this.root = this._delectMin(this.root)
 console.log(this.root)
}
_delectMin(node) {
 // ⼀直递归左⼦树
 // 如果左⼦树为空，就判断节点是否拥有右⼦树
 // 有右⼦树的话就把需要删除的节点替换为右⼦树
 if ((node != null) & !node.left) return node.right
 node.left = this._delectMin(node.left)
 // 最后需要重新维护下节点的 `size`
 node.size = this._getSize(node.left) + this._getSize(node.right) + 1
 return node
}
  • 最后讲解的就是如何删除任意节点了。对于这个操作， T.Hibbard 在 1962 年提出了解决这个难题的办法，也就是如何解决第三种情况。
  • 当遇到这种情况时，需要取出当前节点的后继节点（也就是当前节点右⼦树的最⼩节点）来替换需要删除的节点。然后将需要删除节点的左⼦树赋值给后继结点，右⼦树删除后继结点后赋值给他。
  • 你如果对于这个解决办法有疑问的话，可以这样考虑。因为⼆分搜索树的特性，⽗节点⼀定⽐所有左⼦节点⼤，⽐所有右⼦节点⼩。那么当需要删除⽗节点时，势必需要拿出⼀个⽐⽗节点⼤的节点来替换⽗节点。这个节点肯定不存在于左⼦树，必然存在于右⼦树。然后⼜需要保持⽗节点都是⽐右⼦节点⼩的，那么就可以取出右⼦树中最⼩的那个节点来替换⽗节点
delect(v) {
 this.root = this._delect(this.root, v)
}
_delect(node, v) {
 if (!node) return null
 // 寻找的节点⽐当前节点⼩，去左⼦树找
 if (node.value < v) {
 node.right = this._delect(node.right, v)
 } else if (node.value > v) {
 // 寻找的节点⽐当前节点⼤，去右⼦树找
 node.left = this._delect(node.left, v)
 } else {
 // 进⼊这个条件说明已经找到节点
 // 先判断节点是否拥有拥有左右⼦树中的⼀个
 // 是的话，将⼦树返回出去，这⾥和 `_delectMin` 的操作⼀样
 if (!node.left) return node.right
 if (!node.right) return node.left
 // 进⼊这⾥，代表节点拥有左右⼦树
 // 先取出当前节点的后继结点，也就是取当前节点右⼦树的最⼩值
 let min = this._getMin(node.right)
 // 取出最⼩值后，删除最⼩值
 // 然后把删除节点后的⼦树赋值给最⼩值节点
 min.right = this._delectMin(node.right)
 // 左⼦树不动
 min.left = node.left
 node = min
 }
 // 维护 size
 node.size = this._getSize(node.left) + this._getSize(node.right) + 1
 return node
}

# 2.5 堆

# 2.5.1 概念

  • 堆通常是⼀个可以被看做⼀棵树的数组对象。
  • 堆的实现通过构造⼆叉堆，实为⼆叉树的⼀种。这种数据结构具有以下性质。
  • 任意节点⼩于（或⼤于）它的所有⼦节点 堆总是⼀棵完全树。即除了最底层，其他层的节点都被元素填满，且最底层从左到右填⼊。
  • 将根节点最⼤的堆叫做最⼤堆或⼤根堆，根节点最⼩的堆叫做最⼩堆或⼩根堆。
  • 优先队列也完全可以⽤堆来实现，操作是⼀模⼀样的。

# 2.5.2 实现大根堆

堆的每个节点的左边⼦节点索引是 i * 2 + 1 ，右边是 i * 2 + 2 ，⽗节点是 (i - 1) /2 。

  • 堆有两个核⼼的操作，分别是 shiftUp 和 shiftDown 。前者⽤于添加元素，后者⽤于删除根节点。
  • shiftUp 的核⼼思路是⼀路将节点与⽗节点对⽐⼤⼩，如果⽐⽗节点⼤，就和⽗节点交换位置。
  • shiftDown 的核⼼思路是先将根节点和末尾交换位置，然后移除末尾元素。接下来循环判断⽗节点和两个⼦节点的⼤⼩，如果⼦节点⼤，就把最⼤的⼦节点和⽗节点交换
class MaxHeap {
  constructor() {
    this.heap = [];
  }
  size() {
    return this.heap.length;
  }
  empty() {
    return this.size() == 0;
  }
  add(item) {
    this.heap.push(item);
    this._shiftUp(this.size() - 1);
  }
  removeMax() {
    this._shiftDown(0);
  }
  getParentIndex(k) {
    return parseInt((k - 1) / 2);
  }
  getLeftIndex(k) {
    return k * 2 + 1;
  }
  _shiftUp(k) {
    // 如果当前节点⽐⽗节点⼤，就交换
    while (this.heap[k] > this.heap[this.getParentIndex(k)]) {
      this._swap(k, this.getParentIndex(k));
      // 将索引变成⽗节点
      k = this.getParentIndex(k);
    }
  }
  _shiftDown(k) {
    // 交换⾸位并删除末尾
    this._swap(k, this.size() - 1);
    this.heap.splice(this.size() - 1, 1);
    // 判断节点是否有左孩⼦，因为⼆叉堆的特性，有右必有左
    while (this.getLeftIndex(k) < this.size()) {
      let j = this.getLeftIndex(k);
      // 判断是否有右孩⼦，并且右孩⼦是否⼤于左孩⼦
      if (j + 1 < this.size() && this.heap[j + 1] > this.heap[j]) j++;
      // 判断⽗节点是否已经⽐⼦节点都⼤
      if (this.heap[k] >= this.heap[j]) break;
      this._swap(k, j);
      k = j;
    }
  }
  _swap(left, right) {
    let rightValue = this.heap[right];
    this.heap[right] = this.heap[left];
    this.heap[left] = rightValue;
  }
}

# 3. 算法

推荐看这个： https://blog.shenzjd.com/pages/9eaae444f0d5b/ (opens new window)

# PDF 下载

https://docs.qq.com/pdf/DV0ZySVJxc2Z0dnRW (opens new window)

编辑 (opens new window)
上次更新: 2024/11/05, 06:40:27
高级篇
高频考点

← 高频考点→

最近更新
01
Code Review
 10-14
02
富强
 10-13
03
ComfyUI
 10-11
更多文章>
Power by vuepress | Copyright © 2015-2024 神族九帝
×