数据结构笔记：B-树，Splay树，Trie树

B-树：
1. 所有叶子节点在同一层
2. 对于m阶的B-树，除了根节点有2到m个孩子外，每个内节点有ceil(m/2)到m个孩子，或者说有ceil(m/2)-1到m-1个pairs。
3. level≤log ceil(m/2) (N+1)/2, ceil(m/2)是下标
4.

	Insert	Delete
Average Disk Accesses	h+1	h+4
Worst－case Disk Accesses	3h+1	3h

Worst－case Disk Accesses－Insert：假设有足够的内存存放h个节点。自上往下寻找插入点需要读取h次，自下往上剪枝拆分节点需要存取2s＋1次（s是被拆分的节点数），因此存取磁盘h+2s+1次，最大值为3h+1.
Worst－case Disk Accesses－Delete: 假设有足够的内存存放h个节点。自上往下寻找删除节点需要读取h次，自下往上访问兄弟节点来寻找可借用节点需要读取h-1次，同时合并节点需要写入h-2次，而在根节点时需要三次存取（两次访问兄弟节点是否可被借用，一次写入根）。

R-树：
1.从B+树变化而来，用来组织管理磁盘中被使用的数据块。
2.非长方形的数据块，使用最小可能的长方形(minimum bounding rectangles, MBRs)表示。
3.M阶的R-树的每个内结点（除根外）有m到M个子结点，其中m≤ceil(M/2)；根节点有1到M个子结点。每个索引结点与其孩子具有相同的子结点数目。
4.所有叶子结点在同一层中。
5.R+树在进行插入删除等操作时，需要考虑所有可能情况，从而得到相对较优的解。
6.R+树从R-树变化而来，不同之处在于，内结点不相互覆盖，没有子结点数目的限制，数据结点大小没有限制。由于内结点不相互覆盖，可能发生同一个数据对象被切割分别存储在不同的数据结点中，这也是为什么内结点没有限制子结点数目。
7.Cell Tree是将BSP树和R+树组合到一起。内结点没有相互覆盖的凸多面体，数据结点大小没有上下界，内结点的孩子数目有下界没有上界。

Splay树（伸展树）：
1. Splay节点是每种操作停止的节点。如，插入时发现已存在该节点，已存在的节点就是Splay节点；删除时把删除内节点转换成了删除叶子节点，物理意义上被删除的叶子节点的父节点才是Splay节点（因为子节点被删除了所以不是子节点，或者说最后操作的是父节点）。
2. 所有操作的实际复杂度为O(n)，平摊复杂度为O(log n)。
3. Splay树所做的假设是，刚被存取过的节点近期再次存取的概率很高。对于无规律存取的应用，效率不高。
4. 由于Splay操作的目的是将Splay节点移到根节点，有些rotation是无谓的操作，且会变换节点顺序，而递归在某些特殊设计中可能不安全，会遇到递归桟溢出等现象。因此Top-down（自顶向下）Splay树可以解决这个问题，思想是将Splay节点的所有祖先节点按大小分成两棵树，然后在与Splay节点合并，令Splay节点成为根。

Trie树：
1.Trie树用自根节点向下的整个通路(path)来表示数据，而不是某个特定节点包含了全部信息。对于数据相似度高的数据集，可以节省很多空间；一般应用于字符串集。
2.Compressed Binary Tries: 在Binary Tries(阶为2)的基础上增加一个域bit#，用于存储其左右子树分叉的位置是从关键字(key)的第几个bit。Compressed Binary Trie的孩子数是0或2，因为单个的子节点可以跟父节点合并，并让bit#增加1.
3.高阶Trie(High Order Tries)是阶大于2的Trie. 压缩高阶Trie就是将Compressed Binary Tries中的bit#域改为char#(其实是一个东西)，并将孩子数从2扩展为m。下图中的#ptr用于存储节点中空指针的数目，个人觉得这个域并不会对提高效率产生明显影响。
4.Multibit Tries: 用于表示不同长度的字符串集，即用大于1 bit的比较来决定一个节点之后的分叉。最常用于路由器中路由表的实现，如:IP地址为11*作为父节点，1101*，1110*和1111*的不同分叉用2bits决定不同路由策略。该数据结构分两种，固定步长(fixed-Stride)和可变步长(variable-stride)，步长就是用于决定分叉的bit长度，需要用动态规划算法来决定最优的步长。


Binary Tries：

Compressed Binary Tries：

Compressed High Order Tries：

Multibit Tries：