Расположение узла двоичного дерева и словарь помощника

Question

Спасибо за вашу помощь

Фон

У меня есть вопрос о расположении узлов в дереве.

У меня есть простое двоичное дерево. Каждый узел имеет часть данных в нем. Допустим, это выглядит так:

  a
 / \
b   c

Где a=root, b=root.left, c=root.right

Дерево не создается вручную. Допустим, я получил запрос на добавление new_data к узлу c.

Я не понимаю, как узнать, где находится c, без явного написания root.right.data=new_data.

Моя первая мысль - создать некоторый тип вспомогательного словаря со ссылками на расположение узлов, например:

helper = {
    'a'= root,
    'b'= root.left,
    'c'= root.right
}

Так что, когда я получу запрос, я могу пойти к помощнику и сказать что-то вроде:

helper.get('c').data=new_data

Вопросы

Я на правильном поле? Рекурсивный поиск по всему дереву несколько раз кажется немного сложным - этот помощник может периодически обновляться, когда дерево меняет структуру своего узла.

Я не понимаю, как на самом деле вернуть мое местоположение для каждого узла, когда я рекурсивно сканирую дерево. Как я могу создать этот помощник?

Answer 1

Ответ

Ответ - рекурсивный поиск. Мои мысли о диктаторе помощника проистекают из моей незнакомости с BST. Я добавил следующее в мои узлы для поиска предзаказа дерева:

def find_node(self, start, id):
    if start:
        if start.id == id:
            return start
        else:
            node = self.find_node(start.left, id)
            if node:
                return node
            else:
                node = self.find_node(start.right, id)
                if node:
                    return node
    else:
        return None

Это видео было очень полезно, чтобы помочь мне понять BST. Я понял, что вместо того, чтобы просто печатать обход, я мог бы возвращать фактический экземпляр самого класса, когда нашел правильное значение id.

Answer 2

Если у вас есть ссылка на узел c, вы можете использовать ее напрямую, например: c.data=new_data.

В противном случае, если вы получаете, например, строка, тогда:

1. Ваше дерево отсортировано, или оно может быть отсортировано? (т.е. это BST ?) Если так, используйте его.
2. Если это не так, то есть ли какое-либо другое свойство дерева / узлов, которое вы можете использовать для сокращения поиска? (т.е. у вас есть некоторая информация, чтобы ограничить, где искать). Если так, используйте это. Если вы не знаете, можете ли вы его использовать, вам следует указать, какие свойства имеют ваши данные в вашем вопросе.
3. Если узел может быть где угодно, то вам в большинстве случаев приходится искать по всему дереву (поскольку нужный вам узел может находиться где угодно). Если это так, есть ли смысл в древовидной структуре? Может быть, вместо этого будет полезна хеш-таблица. (Вы можете проиндексировать дерево после того, как получите его)

Кстати. Обратите внимание, что поиск по дереву должен составлять O (n) по размеру дерева, до вас, если это чрезмерно или нет.