Balanced Trees

todo

B-树

红黑树

已有此部分的描述，本文仅给出红黑树。这部分不再展开。

• 最有名的一种平衡二叉搜索树
• 最差：$O(log(n))$增删改查

增强搜索树

参考

• Slides:
  • Lecture Slides I
  • Condensed Slides I
  • Lecture Slides II
  • Condensed Slides II
• Readings:
  • Bayer, Rudolf and McCreight, Edward. Organization and Maintenance of Large Ordered Indices
  • Guibas, Leo and Sedgewick, Robert. A Dichromatic Framework for Balanced Trees