某储备粮的“学习笔记” - B-Tree 2011-04-06T12:00:49+08:00 Typecho http://blog.gregwym.info/feed/atom/tag/B-Tree/ <![CDATA[CS 240复习总结之四: Dictionaries & Balanced Search Trees]]> 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 2011-04-06T12:00:49+08:00 咳嗽di小鱼 http://blog.gregwym.info AVL Tree性质:
  • BST基础性质
  • 左侧和右侧subtree的height最多差1
  • 空白Tree的高度为-1
  • Search, Insert, Delete Runtime均为Θ(log n)

AVL Insertion:
  1. 执行标准BST Insertion
  2. 从新insert的leaf开始, 从下往上更新balance factor(左右高度差)
  3. 如发现高度差超过1(即为2), 则执行fix

AVL Fix: 修复高度差为2的subtree
  • Single rotation: 当height最高的leaf位于最左侧/最右侧
    • 将subtree的root Z向height较低的方向旋转, 即以height较高的child Y为root
    • Y原内侧child, 并入Z内侧

    AVL_single_rotation.png
  • Double rotation: 当height最高的leaf位于Tree内侧
    • 将height较高的root child向外侧旋转, 将Tree变形为Single rotation的初始形式
    • 执行Single rotation

    AVL_double_rotation.png

2-3 Tree性质:
  • BST基础性质
  • 每个node包含一个KVP*和两个children, 或者包含两个KVP和三个children.
  • 所有leaf都在同一层(level)

2-3 Tree Insertion:
  1. 找到KVP应在的leaf (BST规则)
  2. 如果该leaf已经饱和 (已经包含两个KVP), 则将3个KVP排序a < b < c.
  3. 将a和c分割成两个单独的leaf, 并将b插入到parent中.
  4. 重复第2步直到符合2-3 Tree所有性质

2-3 Tree Deletion: 删除x
  1. 如果x所在的node有两个KVP, 则直接删除x
  2. 如果同parent下, 与该node相邻的child有两个KVP, 则用node与child之间的parent替代x, 并用中间值替代parent
  3. 否则 (同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/

]]>