BST   BBST 为了解决BST插入后不平衡的问题 

目录 插入 zig-zag  删除 zig​ zag-zig​  BST因为高度不能保证动态静态操作在log(n)以下。 h（CBT）=log（n）。 h（BBST）=O(log n)，渐进意义下高度不超过log n。  插入 zig-zag   删除 zig 虚线连接表示至少有一个叶节点，T2下的虚线方框里如果有节点，那么h不变。 zag-zig

udp标识字段   udp首部  udp+IP IP首部单位：4B，片偏移单位：8B 以太网帧的数据段的最大长度是1500B

目录  总线的分类  系统总线的结构 单总线结构 双总线结构​ 三总线结构​ 四总线结构​    总线的分类 串行总线与并行总线（按数据传输格式） 串行总线传输速度不一定比并行总线低。  系统总线的结构 单总线结构 双总线结构 通道是不是就是缓存？  三总线结构 四总线结构

 磁盘、磁道、扇区  磁盘的物理地址    一次磁盘读、写操作需要的时间

列表访问完一个元素后，将他放到前面便于下次访问。仿照这种方法，二叉搜索树变成了伸展树。也提出了逐层伸展的方法。   逐层伸展 父节点旋转。 直到访问的节点成为根节点。整棵树的高度，取决于左子树和右子树的高度差。 逐层伸展的最坏情况退化成了列表和向量的复杂度。故提出了双层伸展策略：祖父节点旋转后，父节点再旋转。直到访问的节点成为根节点。整棵树的高度，缩短为原来的一半。为什么呢？ 折叠效果   分摊性能

顺序查找：O（n） 二分查找（折半查找）：O（logn）（AVL-TREE的高度） 插值查找：O（loglogn） 伸展树双层伸展：O（logn）

dicrease and conquer：О(n)  把下一次要解决问题的规模每次都减1：迭代。  二分查找（A）  divide and conquer：О(n) 

   

后向边：v->u(discovered)，后代访问到自己的祖先：有回路； 前向边：v->u(visited)，v先被发现，祖先访问到已经被访问完的后代：有多条路径。 跨边：v->u(visited)，u先被发现。     有向图的dfs  

目录  程序直接方式​  中断驱动方式​ DMA方式​ 通道控制方式​​  i/o控制器      程序直接方式  中断驱动方式 DMA方式 通道控制方式

目录 信道利用率-停止等待协议 信道利用率-后退n帧协议 有效数据率​ 吞吐率​​  信道利用率（时间/时间）=发送窗口把帧放到信道上的时间 ÷  发送窗口要发送的1个或几个帧从发送站传送到信道上的时间+ 这些帧传输到目的站的时间+ 确认帧发送到信道的时间+ 确认帧传输到发送站的时间   有效数据率（bit/时间）=发送帧中的数据bit ÷  发送窗口要发送的1个或几个帧从发送站传送到信道上的时间+ 这些帧传输到目的站的时间+ 确认帧发送到信道的时间+ 确认帧传输到发送站的时间  吞吐率（先根据信道利用率算出一次最多发送几个帧）=发送窗口把这几个帧传输到信道上的时间 &#x...