Pascal实现AVL树时旋转触发Error 202栈溢出，原因是什么？

AI 小北

2026-5-19

排查Turbo Pascal 7.0中AVL树左旋栈溢出（Error 202）的核心思路

Error 202是栈溢出，结合你第三次插入触发的场景，几乎可以肯定是无限递归调用导致的——而非Turbo Pascal默认栈大小不足（毕竟才第三次操作）。结合AVL树的逻辑，我帮你梳理几个最可能的问题点：

1. 旋转类型判断错误，触发无效旋转

AVL树的单旋（左旋/右旋）只适用于特定平衡因子场景：当根节点平衡因子为2时，必须先检查右孩子的平衡因子：

如果右孩子平衡因子≥0：才用单左旋（rotate_l）
如果右孩子平衡因子<0：需要先右旋右孩子，再左旋根节点（即右双旋rotate_rl）

如果你跳过了右孩子平衡因子的判断，直接对根节点调用rotate_l，旋转后根节点的平衡因子可能依然异常（比如还是2），导致后续平衡检查再次触发rotate_l，形成无限递归。

2. 旋转后平衡因子更新错误

左旋操作必须严格更新原根节点和新根节点的平衡因子，否则旋转后的节点平衡因子仍会超出±1范围，反复触发旋转逻辑。比如错误的平衡因子更新可能是这样：

// 错误示例：简单递减平衡因子，未考虑子节点的原始平衡因子
procedure rotate_l(var root: TreeNodePtr);
var temp: TreeNodePtr;
begin
  temp := root^.right;
  root^.right := temp^.left;
  temp^.left := root;
  root^.bf := root^.bf - 1; // 错误：未结合temp的平衡因子计算
  temp^.bf := temp^.bf - 1; // 错误：逻辑不严谨
  root := temp;
end;

正确的左旋平衡因子计算应该结合原节点的平衡因子：

procedure rotate_l(var root: TreeNodePtr);
var
  temp: TreeNodePtr;
  bf_root, bf_temp: Integer;
begin
  temp := root^.right;
  root^.right := temp^.left;
  temp^.left := root;

  bf_root := root^.bf;
  bf_temp := temp^.bf;

  // 计算旋转后原根节点的平衡因子
  if bf_temp >= 0 then
    root^.bf := bf_root - 1 - bf_temp
  else
    root^.bf := bf_root - 1;

  // 计算旋转后新根节点的平衡因子
  if bf_root <= 0 then
    temp^.bf := bf_temp - 1 + bf_root
  else
    temp^.bf := bf_temp - 1;

  root := temp;
end;

3. 旋转后不必要的递归平衡调用

有些实现会在旋转后再次递归调用平衡函数（比如balance(root)），但AVL树的旋转本身已经完成了平衡调整。如果旋转后的平衡因子已经正常，再调用平衡函数会导致无意义的递归，甚至因为平衡因子判断错误进入循环。

4. 快速排查技巧

加调试输出：在rotate_l的开头和结尾添加writeln语句，输出当前节点的键值和平衡因子，看看是不是反复进入rotate_l而不退出——这是无限递归的直接证据。
检查指针赋值：确保旋转过程中没有出现节点指针指向自身的情况（比如root^.right := root），这种错误会导致后续遍历/平衡检查陷入死循环。
临时增大栈空间：在程序开头添加{$M 16384,0,65536}（第一个参数是栈大小，默认是8192），如果增大后依然溢出，彻底排除栈大小问题，聚焦逻辑错误。

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