2-3-4 Tree(2-3-4树)

二叉查找树（Binary Search Tree，简称BST）是一棵二叉树，它的左子节点的值比父节点的值要小，右节点的值要比父节点的值大。它的高度决定了它的查找效率。
我们知道二叉查找树。每个节点只可以有一个key，而2-3-4树就是将节点的key的数量增加，可以有多个key，并且2-3-4树可以保持完美平衡（Perfect balance. Every path from root to leaf has same length）

• 类的功能层次
• 类的实现层次
• 桥接模式的具体事例
• 小结

Bridge的意思是桥梁，作用就是将两边连接起来。桥接模式的作用也是如此，桥接模式分别类的功能层次和类的实现层次连接起来。

这里出现了两个可能有点陌生的词汇，类的功能层次和类的实现层次。

所以我们先来介绍这两种的层次结构，因为桥接模式就是为了连接这两种层次结构。

网络层的重要功能就是路由和转发。而路由是根据路由器根据所维护的路由表进行路由选择。所以，如果创建和更新转发表就是一个很重要的问题。通常，在路由时，我们总是选取所需代价最小的一条路由。

拥塞(Congestion)
给一个非正式定义就是：“太多发送主机发送了太多数据或者发送速度太快，以至于网络无法处理”
如果网络中发生了拥塞，会出现如下表现：

• 分组丢失（路由器缓存溢出）
• 分组延迟过大（在路由器缓存中排队）

和可靠数据传输一样都是网络领域中的top-10的问题。

拥塞现象是指到达[通信子网]中某一部分的分组数量过多，使得该部分网络来不及处理，以致引起这部分乃至整个网络性能下降的现象，严重时甚至会导致网络通信业务陷入停顿，即出现[死锁]现象。这种现象跟公路网中经常所见的交通拥挤一样，当节假日公路网中车辆大量增加时，各种走向的车流相互干扰，使每辆车到达目的地的时间都相对增加（即延迟增加）,甚至有时在某段公路上车辆因堵塞而无法开动(即发生局部[死锁]

可靠数据传输对于应用层、传输层、链路层都很重要，是网络领域的Top10问题。
对于传输层来说，由于相邻的网络层是不可靠的，所以要在传输层实现可靠数据传输（rdt）就比较复杂。
那么我们来了，究竟怎样才是可靠？

• 全排列
• 带重复元素的排列
• 下一个排列
• 上一个排列
• 第 k 个排列
• 排列序号
• 排列序号II
  阅读全文 »