| title | date | tags | author | comments |
|---|---|---|---|---|
算法导论研读与分析（九） |
2013-09-18 03:00:00 -0700 |
数据结构，二叉搜索树 |
maclaon |
false |
搜索树数据结构可以支持多动态集合的操作，可以使用一颗搜索树既可以作为一个字典又可以作为一个优先级队列。比如根据单词词频出现的概率，来构造最优二叉搜索树来设计对应的翻译系统以及搜狗输入法的联想记忆等。二叉搜索树在基本操作所花费的时间与这棵树的高度成正比，对于有$$n$$个节点完全二叉树，操作最坏的运行时间为$$\Theta(\lg n)$$可以设计二叉搜索树的变体，来保证基本操作具有好的最坏情况的性能，比如后续介绍的：红黑树和$$B$$树，其中$$B$$树特别适合用于二级（磁盘）存储器上的数据库维护。
它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 最早的平衡二叉树: windows对进程地址空间管理
一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的，能保证在最坏情况下，基本的动态几何操作的时间均为$$\Theta(\lg n)$$
一般的，红黑树，满足以下性质，即只有满足以下全部性质的树，我们才称之为红黑树：
- 每个结点要么是红的，要么是黑的
- 根结点是黑的
- 每个叶结点，即空结点（NIL）是黑的
- 如果一个结点是红的，那么它的俩个儿子都是黑的
- 对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点
- 广泛应用于C++的STL中，map和set都是用红黑树实现的。
- linux进程调度，用红黑树管理进程控制块
- epoll在内核中的实现，用红黑树管理事件块
- nginx中，用红黑树管理timer等
- java中的TreeMap实现
"在计算机科学中，B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。"
B树可以看作是对二叉查找树的一种扩展，即他允许每个节点有M-1个子节点。
- 根节点至少有两个子节点
- 每个节点有M-1个key，并且以升序排列
- 位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间
- 其它节点至少有M/2个子节点
下图是一个M=4 阶的B树:
下面是往B树中依次插入
6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4
的演示动画：
- 主要用在文件系统以及数据库中做索引等
B+树是对B树的一种变形树，它与B树的差异在于：
- 有k个子结点的结点必然有k个关键码；
- 非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。
- 树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。
如下图，是一个B+树:
下图是B+树的插入动画：
B和B+树的区别在于，B+树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。 B+树的优点在于:
- 由于B+树在内部节点上不好含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子几点上关联的数据也具有更好的缓存命中率。
- B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。
但是B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。
- 和B树一样，主要用在文件系统以及数据库中做索引等