http://blog.gregwym.info/tag/BST/ http://blog.gregwym.info/cs-240-fu-xi-zong-jie-zhi-si--dictionaries-and-balanced-search-trees.html 2011-04-06T12:00:49+08:00 AVL Tree性质: BST基础性质 左侧和右侧subtree的height最多差1 空白Tree的高度为-1 Search, Insert, Delete Runtime均为Θ(log n) AVL Insertion: 执行标准BST Insertion 从新insert的leaf开始, 从下往上更新balance factor(左右高度差) 如发现高度差超过1(即为2), 则执行fix AVL Fix: 修复高度差为2的subtree Single rotation: 当height最高的leaf位于最左侧/最右侧 将subtree的root Z向height较低的方向旋转, 即以height较高的child Y为root Y原内侧child, 并入Z内侧 Double rotation: 当height最高的leaf位于Tree内侧 将height较高的root child向外侧旋转, 将Tree变形为Single rotation的初始形式 执行Single rotation 2-3 Tree性质: BST基础性质 每个node包含一个KVP*和两个children, 或者包含两个KVP和三个children. 所有leaf都在同一层(level) 2-3 Tree Insertion: 找到KVP应在的leaf (BST规则) 如果该leaf已经饱和 (已经包含两个KVP), 则将3个KVP排序a < b < c. 将a和c分割成两个单独的leaf, 并将b插入到parent中. 重复第2步直到符合2-3 Tree所有性质 2-3 Tree Deletion: 删除x 如果x所在的node有两个KVP, 则直接删除x 如果同parent下, 与该node相邻的child有两个KVP, 则用node与child之间的parent替代x, 并用中间值替代parent 否则 (同parent下, node相邻child均只有一个KVP), 将相邻child与parent(中间值)合并. 重复直到Tree符合要求. B-Tree性质: 扩展版的2-3 Tree 每个node包含最多2d个KVP 非root的node最少包含d个KVP 2-3 Tree的d = 1 Insertion和Deletion与2-3 Tree大同小异注: 此B-Tree定义不完全符合11W Slide备注: KVP意为Key-Value Pair, 即Key与Value的一对, 为一个KVP.今天先到这里了...明天总结后半部分`= =更多CS 240总结请看: http://blog.gregwym.info/tag/cs240/