Approaches to Balanced Binary Search Trees平衡树的方法
- Instance simplification approaches: Self-balancing trees:
– AVL trees
– Red-black trees
– Splay trees - Representational changes:
– 2-3 trees
– 2-3-4 trees
– B-trees
8.1 AVL Trees
For a binary (sub-) tree, let the balance factor be the difference between the height of its left sub-tree and that of its right sub-tree.
An AVL tree is a BST in which the balance factor is -1, 0, or 1, for every sub-tree.
主要考察平衡因子，即左右两子数高的差值，AVL tree的每个节点的平衡因子只能是1，0，-1
8.1.1 Building an AVL Tree
- 从最低的不平衡子数开始re-balance构建AVL tree
- 在将数组中的数插入AVL tree时，每一步只要不满足平衡就立即rotation，不是等到所有插入结束再调整为AVL
8.1.2 The Single Rotation
AVL tree总结
1.t the depth of an AVL tree with n nodes is Θ(log n) .
2.深度为log2(n)
3.在最坏的情况下，搜索最多需要比完美平衡的BST多45%的比较。
4.删除很难实现但插入的复杂度为Θ(log n)。
8.1.3 Other Kinds of Balanced Trees
red-black：红黑树是一种BST，它的“平衡”概念略有不同。它的结点是红色或黑色的，所以:
- 没有红色节点有红色子节点。
- 从根到边缘的每条路径都有相同数量的黑节点。
最坏情况：最长的路径是最短路径的两倍长
splay tree：伸展树是一种既能自我调节又能自适应的BST。频繁访问的项更靠近根，因此访问它们的成本更低。
8.2 2-3 Trees
一个树节点存储2-3个项目
BST是一个节点拥有一个项目和最多两个子节点
2-3 tree是一个节点（称为3-node）拥有2个项目和最多3个子节点
2-3-4 tree 是一个节点拥有3个项目和最多4个子节点
一个节点在拥有三个项目时会拆分，中间的项目promote给父节点，其余两个分割为两个子节点
2-3 tree 总结
1.最差的搜索时间是当所有节点都是2-nodes时，即二叉树，n=2(h+1)-1
2.最好的搜索时间是当所有节点都是 3-nodes时，n=3(h+1)-1
8.3Time/Space Tradeoffs -16
用表(增加空间)来减少时间
8.3.1Fibonacci Numbers with Tabulation
8.3.2Sorting by Counting
找出每个数字的频率并建立对应的索引表
遍历数组A，在索引表中找到当前数字的最后一个索引，填入数字并将最后一个索引往前移动
此方法复杂度为Θ(n)，不涉及 key-to-key comparison，key-comparison based sorting的复杂度为Ω(nlogn).
8.3.3String Matching-Horspool’s String Search Algorithm
1.建立shift table
[T A A C G]的shift table为[A T G C]=[2,4,5,1]
若pattern里有相同字母以最小的shift为最终结果
2.运行Horspool’s String Search Algorithm
