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内侧
  
  
• 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:

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