红黑BST的基本操作过程

红黑BST是2-3查找树的一种具体实现方式,它将2-3查找树中的3-节点视为两个相连的2-节点,并对链接设定了颜色(红,黑)属性以描述这些特殊的2-节点。这样就不用再为3-节点定义专门的数据结构,基础操作直接复用BST的逻辑即可,基于基础操作可方便地实现更多更高级的操作。

红黑BST的基本设定:

  • 红色链接一律为左链接
  • 不可出现同时与两条红链接相连的节点

《2-3查找树的基本操作过程》中讨论删除操作的时候,把3-节点视为两个2-节点相连,且规定后来的那个节点为子节点,于是得到了下图。此时的链接就不都是左链接。

一个节点与两条红色链接相连的情况 ...


2-3查找树的基本操作过程

假设一组key:{ 9, 3, 8, 1, 2, 10, 4, 5, 7, 6 }

执行操作:put(key)、del(key)、get(key),只考虑key,不考虑value ...


硬性关闭TCP连接

硬性关闭是指:使用非正常的手法立即终止当前TCP连接,只求关闭,不考虑后果,丢失数据也无所谓。这种方式在处理一些紧急状况时或许是必要的。

正常的关闭流程是在连接双方的配合下经历四次握手完成的。应用程序里的操作就是调用close接口。

对socket实施close操作,实际上会产生一个FIN报文段,这个段当然也要遵从TCP的规则,它会在发送缓冲区中排队。显然,调用close的一方要想实际发出这个FIN段,当然要先将排在它之前的那些字节发出去才行。也就是说,调用close后,到实际发出FIN之前,发送缓冲区中的数据已经发送到对端了。

上面说的是正常的关闭,用close接口即可发起。非正常关闭,也是用这个接口,只不过要配置一下socket的LINGER选项。

linger有“苟延残喘”的意思 ...


网线断了是什么状态-续

之前测试的场景是两个主机直接连接,中间没有其他设备。在现实情况中,这种做法几乎是不存在的。一端连接主机的网线,其另一端通常接入的是交换机,集线器之类的网络设备。

在这种情况(除接入一个交换机之外,其他设定与之前相同)下,执行前篇进行的各种操作,可能会有不同的结论 ...


二叉树的几个术语

根(root)节点、内部(inner)节点、叶子(leaf)节点。

边 ...


普通BST的基本操作过程

假设一组key:{ 9, 3, 8, 1, 2, 10, 4, 5, 7, 6 }

执行操作:put(key)、del(key)、get(key),只考虑key,不考虑value

put(key):插入一个键值为key的节点

依次插入上面的那10个key:

  • put(9)

  • put(3)

  • put ...