Преобразовать рекурсивный __setitem__ в итеративный в Python - PullRequest
Новая
       19

Преобразовать рекурсивный __setitem__ в итеративный в Python

0 голосов
/ 24 мая 2019

Здесь у меня есть метод setitem моего Двоичного дерева поиска. В настоящее время я получаю сообщение об ошибке «RecursionError: максимальная глубина рекурсии превышена», поэтому я хотел бы преобразовать его в итеративный метод, но я немного застрял. Есть намеки? 

class BinarySearchTreeNode:

    def __init__(self, key, item=None, left=None, right=None):
        self.key = key
        self.item = item
        self.left = left
        self.right = right

class BinarySearchTree:

    def __init__(self):
        self.root = None

    def __setitem__(self, key, item):
        self.root = self._setitem_aux_(self.root, key, item)

    # here convert this to an iterative method
    def _setitem_aux_(self, current, key, item):
        if current is None:
            current = BinarySearchTreeNode(key, item)
        elif key < current.key:
            current.left = self._setitem_aux_(current.left, key, item)
        elif key > current.key:
            current.right = self._setitem_aux_(current.right, key, item)
        else: # key == current.key
            current.item = item
        return current

И назовите это: 

bst = BinarySearchTree() 
# To set an item with key = 0, item = 1
bst[0] = 1 
# To set an item with key = "abcd", item = 10
bst["abcd"] = 10

1 Ответ

1 голос
/ 24 мая 2019

Может попробовать это? 

def __setitem__(self, key, item):
    if self.root is None:
        self.root = BinarySearchTreeNode(key, item)
    else:
        current = self.root
        found = False
        max_iter = 10000  # set this to the appropriate value for your use case
        iter_ = 1
        while not found and iter < max_iter:
            if current is None:
                raise IndexError("Index out of bounds")
            elif key < current.key:
                current = current.left
            elif key > current.key:
                current = current.right
            else:
                found = True
            iter_ += 1

        if found:
            self.root = current
        else:
            raise IndexError("Index too far from root")

Примечание: рекурсия - это мощный, но опасный паттерн. Это также может помешать удобочитаемости кода. Следует избегать, когда итеративный фрагмент кода может достичь того же результата.

...