如何修复Python自平衡二叉搜索树（SBBST）根节点值错误问题？

问题现象 #

使用self_balancing_binary_search_tree库的SBBST类，传入序列[80,3,20,95,70]初始化树后，打印发现根节点为20，而非预期的80；怀疑问题出在库的第297行附近，但不确定修复方式。

相关代码：

from self_balancing_binary_search_tree import SBBST

nums = [80,3,20,95,70] 
ST = SBBST(nums)
print(ST)

核心排查与修复方向 #

平衡BST（如AVL、红黑树）的根节点由插入后的平衡调整逻辑决定，80未成为根，说明初始化阶段的插入或平衡逻辑存在错误，可按以下步骤排查：

1. 验证库的初始化逻辑 #

首先确认SBBST的__init__方法是逐个插入序列元素，还是采用了批量构建（如先建普通BST再批量平衡）。如果是逐个插入，问题大概率出在后续元素插入时的旋转调整逻辑错误，导致根节点被错误替换。

2. 定位第297行的关键逻辑 #

假设第297行属于平衡调整（旋转、平衡因子计算、红黑树颜色处理）代码，重点检查：

• 平衡因子的计算是否正确（比如AVL树中左右子树的高度差是否算反）
• 旋转操作的触发条件是否匹配场景（比如该左旋时误用了右旋）
• 旋转后节点的父指针、左右子指针是否正确更新，是否遗漏了高度或颜色的同步

3. 手动模拟插入过程验证 #

以AVL树为例，正常插入序列[80,3,20,95,70]的过程应为：

1. 插入80 → 根为80
2. 插入3 → 根仍为80（左子节点3，平衡因子1，无需旋转）
3. 插入20 → 3的右子树导致左子树平衡因子达2，需左旋3所在子树，调整后80的左子节点为20，根仍为80
4. 插入95 → 右子节点95，平衡因子-1，无需旋转
5. 插入70 → 插入到20的右子树，此时80的左子树平衡因子达2，需右旋调整，但根仍应保持为80

如果库代码在这一步错误计算了平衡因子，或旋转逻辑错误，就会把20推为根节点。

4. 临时替代方案 #

若暂时无法修改库代码，可尝试手动逐个插入元素，验证是否能得到正确根节点：

from self_balancing_binary_search_tree import SBBST

ST = SBBST()
ST.insert(80)
ST.insert(3)
ST.insert(20)
ST.insert(95)
ST.insert(70)
print(ST)

若此方式根节点为80，说明库的批量初始化逻辑存在问题（比如未按顺序插入，或批量平衡逻辑错误）。

内容的提问来源于stack exchange，提问作者Natanael Gonzalez