高级搜索树-JZTXT

伸展树

局部性。如刚刚被访问的节点，极有可能很快的再次被访问，下一次要访问的节点，极有可能就在刚被访问的节点附近。
伸展树是局部性原理的应用：将刚被访问的节点，随即通过zag zig旋转操作被转移至树根。调整的过程逐层摇摆，逐渐上升--伸展树。“一步一步往上爬”。
效率问题，存在最坏情况。当伸展树退化成类似链表的结构时，旋转次数每一周期累计omiga(n2) ，分摊下来omiga(n)。
双层伸展--“点睛之笔”，一次性上升两层。在子孙异侧的情况下，伸展两层就是伸展两次；在子孙同侧的情况下，调整的时候从祖父开始而不是父节点，这会使局部的拓扑结构产生微妙的差异，这种微妙的差异将会带来全局的不同。
双层伸展，具有折叠的效果，每一次伸展树高减半。解决了最坏情况，最坏情况不致持续发生，分摊性能单趟不超过O(logn)。
对于伸展树而言，查找动作不再是一个静态操作，这是一个本质特征。插入删除因为伸展动作操作可以做的很简单。
综合评价：优点：无需记录节点高度或者平衡因子：编程简单易行--优于AVL树。分摊复杂度O(logn)与--AVL树相当。局部性强缓存命中率极高。缺点：仍不能保证单次最坏情况的出现。

B-树（多路平衡搜索树）

越来越大的数据，内存容量相对越来越小。不同容量的存储器，访问速度差异悬殊。若一次内存访问需要一秒，则一次外存访问需要一天。所以采用了多级cache，分级I/O。另外一个事实：从磁盘上读写一B，与读写1kB几乎一样快。
B树的节点可以看成二叉树每两代或多代合并后的超级节点。每d代合并：m=2^d路分支，m-1关键码。一般所谓m阶B树，即m路平衡搜索树（m>=2），深度统一。
多级存储系统中使用B-树，可针对外部查找，大大减少I/O次数。比如有1G个记录用平衡术树大约30层，每一层进行一次I/O访问，需要三十层I/O访问。而对于B树，若一个超级节点当中的关键码有256个，同样1G个记录只有4层树高。这是很大的提高。
m 给出了B树中每个超级节点的上限，也给出了每个超级节点的下限。在上限方面，每个节点的分支数都不能超过m个，即关键码不能超过m-1个；在下限方面，每个节点的分支数也不能太少，不能少于m的一半的上整。对于树根来说分支数>=2即可。用分支树的下限上限来命名B树，形如（m/2上整，m）。
B树的查找：一系列的顺序查找+I/O操作（内存+外存操作）。B树的高度上下浮动有限。复杂度：渐进意义下O(logn)，但是B树的优化关注于常系数意义下的优化，因其可以减少I/O次数。
B树的插入 O(h)。分裂，上溢：设上溢出的节点中的关键码依次为k0, ......., kn-1，取中位数，s=m/2取上整，以关键码为界ks划分为k0,...ks-1,ks,ks+1,....kn-1，关键码上升一层，并分裂以所得的两个节点作为左右孩子。上溢缺陷可能会传播，但是只会逐层向上，最坏情况，不过到根。B树增高的可能。
B树的删除 O(h)。下溢，合并。
模仿光的折射---道法自然

红黑树

无论是线性结构，半线性结构，非线形结构，每经过一次动态操作后，逻辑结构有所改变，随即完全转入新的状态，将之前的状态完全
遗忘掉。非持久性结构。在实际情况中，我们可能很看重关联性
红黑树：任何一次动态操作引发的结构变化量不致超过O(1)。持久性。
红黑树模型：树根必为黑色；外部节点均为黑色；其余节点，若为红，则只能有黑孩子；外部节点到根，途中黑节点数目相同。
红黑树经过提升变换后，红孩子与黑父亲平齐。等同视为一个（2，4）B树。红黑树 == （2，4）树。红黑树具有平衡性。
红黑树插入假设插入的时候是平凡情况，不是树根，插入的时候一定是叶子节点，我们不妨将插入的节点染红，如果该节点的父节点是黑色，则插入成功，如果该节点的父亲节点是红色，则产生双红缺陷。双红缺陷的其一情况解决，只需要交换相邻节点颜色即可，然后进行局部“3+4”重构。拓扑结构变换O(1)。双红缺陷的其二情况解决，从B树的角度来看是修复上溢的过程，对应到红黑树只是做了染色操作，双红缺陷可能向上传播，不过最多到根，尽管染色操作可能到O(logn)，拓扑结构的变化仍为O(1)。整个的修复过程中最多执行O(logn)的染色操作，最多执行一次重构操作。
红黑树删除O(logn) 删除某一节点，被某后代节点替代。被删节点和替代者之间有一个为红，只需将替代者染黑即可。被删节点和替代者都为黑，双黑缺陷。修复双黑缺陷，从B树的角度来看则是修复下溢缺陷。四种情况讨论。修复缺陷最多做O(logn)次重染色，一次“3+4”重构，一次单旋。