基于二叉搜索树的有序字典实现出现RecursionError的原因及解决

问题概述 #

尝试实现一个基于二叉搜索树（BST）的有序字典SortedDict，要求所有操作后元素始终按键排序。目前实现了Node类（处理节点插入、获取，暂未实现删除）和SortedDict类（接收有序字典，以中位数为根拼接左右子树）。但当字典规模较大时，访问远离根节点的元素会触发RecursionError，提示递归深度超过Python默认限制。

错误回溯 #

Traceback (most recent call last):
  File "main.py", line 96, in <module>
    print(dic_obj[5])
  File "main.py", line 91, in __getitem__
    return self.root.__getitem__(item)
  File "main.py", line 26, in __getitem__
    return self.left.__getitem__(item)
  File "main.py", line 26, in __getitem__
    return self.left.__getitem__(item)
  File "main.py", line 26, in __getitem__
    return self.left.__getitem__(item)
  [Previous line repeated 994 more times]
  File "main.py", line 18, in __getitem__
    if item > self.root:
RecursionError: maximum recursion depth exceeded in comparison

复现代码 #

dic = {k:k for k in range(1,10000)}
dic_obj = SortedDict(dic)
print(dic_obj[5])    

原实现代码 #

class Node():
    def __init__(self, root=None, value=None, left=None, right=None, parent=None):
        self.parent = parent
        self.root, self.value = root, value
        self.left = left
        self.right = right

    def __str__(self):
        return f'<Node Object - Root: {self.root}, Value: {self.value}, Parent: {self.parent}>'

    def __getitem__(self, item):

        if self.root is None:
            raise KeyError(item)

        if item > self.root:
            if self.right is None:
                raise KeyError(item)
            return self.right.__getitem__(item)

        if item < self.root:
            if self.left is None:
                raise KeyError(item)
            return self.left.__getitem__(item)

        if item == self.root:
            return self.value

    def __setitem__(self, key, value):
        if self.root is None:
            self.root, self.value = key, value
        else:
            if key > self.root:
                if self.right is not None:
                    self.right.__setitem__(key,value)
                else:
                    self.right = Node(root=key, value=value)
                    self.right.parent = self
            elif key < self.root:
                if self.left is not None:
                    self.left.__setitem__(key,value)
                else:
                    self.left = Node(root=key, value=value)
                    self.left.parent = self
            elif key == self.root:
                self.root = value


class SortedDict():
    def __init__(self, array: dict):
        self.root = Node()
        if array:
            keys = list(array.keys())
            for key in range(len(keys)//2):
                self.__setitem__(keys[key],array[keys[key]])
            root = Node(root=keys[key+1],value=array[keys[key+1]])
            self.root.parent = root
            root.left = self.root
            self.root = Node()
            for key in range(len(keys)//2+1,len(keys)):
                self.__setitem__(keys[key],array[keys[key]])
            self.root.parent = root
            root.right = self.root
            self.root = root


    def __setitem__(self, key, value):
        try:
            if key > self.root.root:
                if self.root.right is None and self.root.left is None:
                    node = Node(root=key, value=value)
                    self.root.parent = node
                    node.left = self.root
                    self.root = node
                else:
                    if self.root.right is None:
                        self.root.right = Node(root=key, value=value, parent=self.root)
                    else:
                        node = Node(root=key, value=value)
                        self.root.parent = node
                        node.left = self.root
                        self.root = node
        except:
            self.root.root = key
            self.root.value = value


    def __getitem__(self, item):
        return self.root.__getitem__(item)

问题原因 #

1. 递归深度超限：Python默认递归深度限制在1000左右（可通过sys.getrecursionlimit()查看）。你的Node.__getitem__用递归遍历BST，当树的高度超过这个限制时，直接触发错误。
2. BST结构退化：核心问题是SortedDict的插入逻辑完全错误，导致构建的不是平衡树，而是链式退化树。比如插入1到9999的有序键时：
   • SortedDict.__setitem__中，插入比当前根大的键时，如果右子树存在，会把当前根作为新节点的左孩子，新节点成为新根。这导致所有大键都被插到根位置，原根退化为左子树，最终左子树变成一条从大到小的长链，高度等于元素个数（近5000），远超过递归限制。
   • 初始化时插入前半部分键（1到4999），直接生成了高度4999的左子树，访问5需要递归近5000次，直接触发错误。

解决方法 #

方案1：把递归遍历改成迭代（最直接） #

修改Node.__getitem__为循环实现，彻底规避递归深度问题：

def __getitem__(self, item):
    current = self
    while current:
        if current.root is None:
            raise KeyError(item)
        if item > current.root:
            current = current.right
        elif item < current.root:
            current = current.left
        else:
            return current.value
    raise KeyError(item)

同样，Node.__setitem__也可以改成迭代实现，避免插入时的递归问题。

方案2：修复BST构建逻辑，生成平衡树 #

你的初始化思路是用中位数做根构建平衡树，但__setitem__逻辑完全破坏了这个目标。重新实现SortedDict，用分治法从有序数组构建平衡BST，同时修复插入逻辑：

class SortedDict():
    def __init__(self, array: dict):
        self.root = None
        if array:
            keys = sorted(array.keys())  # 兼容无序输入
            self.root = self._build_balanced_tree(keys, array, 0, len(keys)-1)
    
    def _build_balanced_tree(self, keys, array, start, end):
        if start > end:
            return None
        mid = (start + end) // 2
        node = Node(root=keys[mid], value=array[keys[mid]])
        node.left = self._build_balanced_tree(keys, array, start, mid-1)
        if node.left:
            node.left.parent = node
        node.right = self._build_balanced_tree(keys, array, mid+1, end)
        if node.right:
            node.right.parent = node
        return node
    
    # 迭代式插入，避免递归且保证树结构合理
    def __setitem__(self, key, value):
        if not self.root:
            self.root = Node(root=key, value=value)
            return
        current = self.root
        while True:
            if key > current.root:
                if not current.right:
                    current.right = Node(root=key, value=value, parent=current)
                    break
                current = current.right
            elif key < current.root:
                if not current.left:
                    current.left = Node(root=key, value=value, parent=current)
                    break
                current = current.left
            else:
                current.value = value
                break
    
    def __getitem__(self, item):
        current = self.root
        while current:
            if current.root is None:
                raise KeyError(item)
            if item > current.root:
                current = current.right
            elif item < current.root:
                current = current.left
            else:
                return current.value
        raise KeyError(item)

这个实现构建的平衡BST高度约为log2(n)，n=10000时高度仅14，完全不会触发递归问题，同时插入和查询都用迭代实现，更稳定。

方案3：临时调高递归限制（不推荐） #

可以用sys.setrecursionlimit()提高递归深度，但这只是临时 workaround，可能导致栈溢出，不建议生产环境使用：

import sys
sys.setrecursionlimit(100000)

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