Эффективный рекурсивный итератор: возможно?

Question

Это беспокоило меня долгое время. Мне нужен итератор для двоичного дерева (или подобной вложенной структуры), который эффективен, прост и pythoni c. Например, для таких случаев:

for value in values(root):
    do_something_with_value(value)

print(sum(values(root)))

Здесь root - это узел root дерева, а узлы имеют .value, .left и .right. И values должен дать мне желаемый итератор / итерируемый по значениям дерева.

Пусть n - количество узлов в дереве, а h - высота дерева.

Попытка 1: слишком медленно

def values(root):
    if root:
        yield from values(root.left)
        yield root.value
        yield from values(root.right)

Простой, pythoni c, ленивый и занимает только O (h) место. Это должно быть этим. Но ... это сгруппированные генераторы, и каждое отдельное значение получено через весь стек генераторов. Таким образом, вся итерация занимает время O (n ² ) в худшем случае и время O (n log n) даже в лучшем случае.

Попытка 2: слишком сложно

def values(root):
    stack = []
    while root or stack:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        yield root.value
        root = root.right

Итеративный со стеком узлов. Требуется только пространство O (h) и время O (n), но это намного сложнее, чем приведенная выше полностью естественная рекурсия.

Попытка 3: слишком большая

def values(root):
    result = []
    def collect_values(root):
        if root:
            collect_values(root.left)
            result.append(root.value)
            collect_values(root.right)
    collect_values(root)
    return result

Это собирает все значения в полуглобальном списке. Естественная рекурсия и O (n) время, но, к сожалению, O (n) пространство и не ленивый.

Попытка 4: Не могу заставить его работать

Вместо полуглобального список, который я подумал, может быть, я мог бы злоупотреблять полуглобальным генератором . Как своего рода труба изнутри рекурсии прямо наружу. Рекурсия будет send значений в нее, и внешняя сторона может получить их. Примерно так:

def values(root):
    pipe = magic_generator_pipe()
    def iterate(root):
        if root:
            iterate(root.left)
            pipe.send(root.value)
            iterate(root.right)
    iterate(root)
    yield from pipe

Но я не могу заставить его работать, и я не уверен, что это возможно.

Попытка 5: Возможно

Что-то с threading или asyncio? У меня есть еще одна идея: функция values запускает новый поток. Этот поток рекурсивно выполняет итерацию дерева и передает значения основному потоку в функции values, которая возвращает их исходному внешнему вызывающему объекту. И они блокируют друг друга соответственно. Но я не очень разбираюсь в этом.

Вопрос

Есть ли способ достичь всего, чего я хочу?

1. Pythoni c ленивый итератор
2. O (n) общее время
3. O (h) пробел
4. Естественная рекурсия

Так что по сути я хочу что-то вроде Попытки 1, но быстрый. Потому что я использовал рекурсивный yield from для нескольких задач и всегда чувствую себя плохо из-за сложности времени.

Чтобы уточнить: под «слишком сложным» я действительно подразумевал итеративный алгоритм (он не такой сложный, но по сравнению с это естественная рекурсия). Решение, которое «сложно» только «техническим» способом (например, с дополнительной нитью или идеей батута @ chepner), все равно будет интересно. Я просто настаиваю на естественной рекурсии (или что-то аналогично алгоритмически просто) и на трех других целях.

Answer 1

Мой подход может не удовлетворить вас, поскольку это инверсия того, что вы делаете, а именно использование обратного вызова. Вы передаете функции, способной выполнить итерацию структуры, метод обратного вызова, который будет вызываться для каждого встреченного значения. В этом примере функция walk вызывается с функцией callback. В этом случае структура представляет собой обходимое дерево, и для каждого значения узла вызывается функция обратного вызова.

def walk(root, callback):

    def tree_walk(node):
        if node['left']:
            tree_walk(node['left'])
        callback(node['value'])
        if node['right']:
            tree_walk(node['right'])

    tree_walk(root)


node4 = {'value': 4, 'left': None, 'right': None}
node3 = {'value': 3, 'left': node4, 'right': None}
node2 = {'value': 2, 'left': None, 'right': None}
node1 = {'value': 1, 'left': node2, 'right': node3}

def do_something_with_value(value):
    print('value:', value)

walk(node1, do_something_with_value)

Prints:

value: 2
value: 1
value: 4
value: 3