论文《从二叉查找树到容均树》
From Binary Search Tree to Size Balanced Tree

Abstract

本文从二叉查找树开始,介绍了 2006 年由陈启峰发明的 Size Balanced Tree ,我译作容均树。文章给出了容均树的各种操作的伪代码以及相应 C++ 代码,并对其运行效率作了证明,最后介绍了其在竞赛题目中的应用。

关键字:二叉查找树, BST, Binary Search Tree, 容均树, SBT, Size Balanced Tree,节点大小平衡树


论文的PDF文件请下载


Contents

1 引子 2

2 二叉查找树 2

2.1 神马是二叉查找树 . . . . . . 2

2.2 查询二叉查找树 . . . . . . . . 3

2.3 插入和删除 . . . . . . . . . . 5

2.4 具体代码实现 . . . . . . . . . 9

3 容均树 13

3.1 几何原本 . . . . . . . . . . . 13

3.2 定义 . . . . . . . . . . . . . . 14

3.3 旋转 . . . . . . . . . . . . . . 14

3.4 插入 . . . . . . . . . . . . . . 15

3.5 删除 . . . . . . . . . . . . . . 16

3.6 维护 . . . . . . . . . . . . . . 17

3.7 查询与统计 . . . . . . . . . . 20

3.8 代码实现 . . . . . . . . . . . 22

4 分析应用 27

4.1 数学推倒 . . . . . . . . . . . 27

4.2 优势和局限性 . . . . . . . . . 30

4.3 竞赛应用 . . . . . . . . . . . 30

5 总结 38