Day 45:二叉搜索树(BST)
18年10月17日 · 吴超 1156 人阅读
BST 的意义
二叉搜索树(BST):如果一个二叉树满足:对于任意一个节点,其值不小于左子树的任何节点,且不大于右子树的任何节点(反之亦可),则为二叉搜索树。
BST 是一个很强大的数据结构。它允许在 O(log n) 时间内快速查找、插入和删除元素。更重要的是,BST 可以保持数据有序并且支持对 k 项数据进行区间检索而且时间复杂度是 O(k + log n)。这使得二叉搜索树成为关系型数据库管理系统的关键工具。
对基本二叉树有很多改进,我们知道的有 2-3 树、红黑树、B 树、B+ 树、B* 树。但是,在学习时,不要感到困惑。这些改进都只是具有额外约束、调整和优化的基本 BST。当你用基本的二元树来思考 BST 时,学习起来就容易得多。
- 2-3 树是一个几乎完全平衡的 BST
- LLRB 树是具有路径着色约束的 2-3 树的 BST 实现
- RB 树是具有路径着色约束的 2-3-4 树的 BST 实现
- B 树是一个完全平衡的 BST 与子树块对齐
BST 的一个特性
除了通常的实现,今天我要重点介绍一个有趣的特性:当向不平衡 BST 中添加均匀分布的数据时,树的高度是 O(log n)。
我已经实现了不平衡 BST,并进行了模拟和输出。我们建造100 棵包含特定元素数目的树并进行取样。通过数据收集,我们可以验证树的高度是否真的符合对数函数。理论上这些树的高度分布应该符合对数函数。模拟和统计结果如下,表中包含树的最小最大和平均值:
BST 的实现
实现
模拟
统计
Python3Turtle