Структуры данных Python: дерево предоставления

Деревья Python во многом похожи на связанные списки, но с иерархическим порядком. Деревья состоят из узлов, которые связаны с другими узлами. Нижний узел, не имеющий ссылки, называется листьями . Узел, связанный с другим узлом, называется родительским, а связанный с ним - дочерними.

Дерево обычно строится с широким набором узлов или каскадной глубокой структурой. Итак, вы можете сказать, что дерево широкое или глубокое .

Эффективная версия древовидной структуры известна как двоичное дерево поиска. Вот где вы разрешаете родительскому узлу иметь два дочерних узла. Узел слева имеет меньшее значение, чем узел справа. Построение такого дерева позволяет очень эффективно перемещаться и находить определенное значение.

В приведенном выше примере, если бы я хотел найти значение 98 из 39, я бы двинулся вправо как 98> 39 - из 70 снова вправо - из 97 двигаться вправо, и за три хода я нашел желаемый узел.

Итак, давайте создадим узел дерева на Python и посмотрим, как он работает. Все, что нам нужно для создания узла дерева, - это имя. Мы автоматически назначим ему пустой список для всех последующих дочерних узлов.

Если вы читали мои предыдущие статьи о структуре данных Python, это должно показаться вам знакомым.

Теперь, как и с любой структурой данных, мы должны помнить о практических функциях, которые мы хотим иметь в нашем дереве. Добавление и удаление узла - очевидный выбор, который также легко реализовать.

Для добавления я использую метод append () , а для удаления я просто перебираю список self.children и повторно добавляю все узлы, за исключением узла, который я хочу удалить.

Затем мы захотим пройти по дереву, чтобы найти нужную информацию. Чтобы создать этот метод, мы начнем с пустого списка, который будет заполняться каждым посещаемым узлом. Пока у этого узла есть дочерние узлы, мы вытащим его и добавим в список узлов для посещения.

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

Деревья данных - отличный и широко используемый инструмент в мире программирования. Я надеюсь, что это краткое введение, по крайней мере, дало представление о том, почему вы хотите знать об этих структурах.