Task 1 - Extending the Humble BST [27.5 Marks]b

Cs, Go!

||最后更新: 2025-10-17|

任务概览

在 better_bst.py 中扩展 BinarySearchTree，实现三个递归方法：
  1. range_query(low, high)：区间查询
  1. balance_score()：计算平衡度
  1. rebalance()：重构为平衡树
 
1️⃣
Task 1.1 - Range Queries

🧩 一、range_query(low, high)

目标：
返回所有键在 [low, high] 范围内的节点值（升序）。
思路：
递归遍历树，利用 BST 性质“左小右大”，剪枝不必要的子树。
只在 low ≤ key ≤ high 时保存当前节点。
伪代码：
📈 时间复杂度：
  • 最好情况：O(log n + k)
  • 最坏情况：O(n)
 
 
1️⃣
Task 1.2 - Balance Score
⚖️ 目标：
衡量 BST 的平衡程度。
定义：
平衡度 = 实际高度 − 理想高度
其中理想高度 = ⌈log₂(n + 1)⌉
思路：
  1. 用递归求树的实际高度（左右子树取最大深度）；
  1. 计算节点总数；
  1. 根据公式求平衡度差值。
伪代码：
📈 时间复杂度： O(n)
 
 
1️⃣
Task 1.3 - Rebalancing the BST
目标：
将任意不平衡的 BST 重新构建为平衡树。
思路：
  1. 通过中序遍历获得有序节点列表（保持键的顺序）；
  1. 取中点作为新根，递归构建左右子树；
  1. 最后替换原树根。
伪代码：
📈 时间复杂度： O(n)
 
Loading...