Пример вызова двоичного дерева

Question

Я смотрел несколько лекций с отличным Richard Buckland и экспериментировал с бинарными деревьями, но я не совсем понимаю, как его реализовать. Ниже, насколько далеко у меня есть.

class Tree(object): 
    def __init__(self, val, left=None, right=None): 
     self.val = val 
     self.left = left 
     self.right = right 

t = Tree(4, Tree(2, Tree(1), Tree(3)), Tree(6, Tree(5), Tree(7))) 

Может ли кто-нибудь назвать меня простой проблемой, которая может быть решена с использованием двоичного дерева. Я действительно не понимаю, какие данные мне будут представлены для создания дерева или как я мог бы использовать его практически. Я боюсь, чтобы google для некоторых примеров, потому что Мне не нужен чужой исходный код. Я хочу сам реализовать эту реализацию. Но прежде чем я смогу это сделать, я чувствую, что мне нужно решить проблему. В идеале, мне бы хотелось, чтобы пара была довольно тривиальным примером проблем, а затем еще несколько промежуточных проблем.

Answer 1

Ну, попробуйте это: http://www.spoj.com/problems/TREE/

Или это: http://www.spoj.com/problems/THREECOL/

http://www.spoj.com/problems/NWERC11B/

Эти проблемы не являются тривиальными, и спросит время, но вы обязательно узнаете из этого.

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

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

Answer 2

Ваш код, приведенный выше, является «действительной» реализацией двоичного дерева ... он уже завершен. У вас есть узлы (которые вы вызываете Tree s), и каждый узел может иметь 0, 1 или 2 детей. edit На самом деле я просто понял, что вы не можете реализовать пустое дерево, используя вашу реализацию, но это небольшая нитьчка.

Это семантическая вещь, но она «важна». Бинарное дерево само по себе вообще не используется для проблем. Стандартное двоичное дерево не очень полезно - это просто дерево, где каждый узел имеет не более двух детей. Эта ссылка должна уточнить, что я говорю (и, вероятно, содержит достаточный ответ на ваш вопрос): https://stackoverflow.com/a/2159506.

Я думаю, что вас интересует «сбалансированное двоичное дерево поиска», которое имеет дополнительные свойства. В частности, он «упорядочен» слева направо (это неопределенное описание, но я не хочу быть волнообразным и говорить, что «левый ребенок меньше родителя и его брата», когда он действительно может быть равным в некоторых реализациях). Он также имеет ограниченную глубину O(log(n)) (у вас не будет деревьев с высотой n с n объектами в нем ... которые являются только связанным списком).

В любом случае, чтобы ответить на ваш вопрос: это своего рода скучно, но общее предложение - реализовать абстрактную структуру данных, такую ​​как куча или словарь. Обратите внимание на терминологию: куча может быть реализована с использованием двоичного дерева поиска. Куча, по определению, не привязана ни к какой реализации. Для этого требуется только выполнение определенных операций (например, peek(), min(), add() и т. Д.). Выбор примитивной структуры данных, такой как двоичное дерево, необходим для создания кучи (иначе это просто абстрактная вещь, плавающая в вашей голове). Выбор сбалансированного дерева двоичного поиска также дает временные сложности для этих операций (например, куча, реализованная со сбалансированным двоичным деревом поиска, имеет O(log(n)) peek(). См. Ссылку на wiki для получения дополнительной информации: http://en.wikipedia.org/wiki/Heap_(data_structure)#Comparison_of_theoretic_bounds_for_variants).

Как только вы написали кучу, вы можете посмотреть любую проблему, в алгоритме которой используется куча ... там много. Скажем, вы хотите найти k самый большой элемент в линейном времени. Куча (доказать это немного сложно). Что делать, если вы хотите реализовать алгоритм Prim? Heap. Что делать, если вы хотите сортировать произвольные объекты с наихудшим случаем O(n log(n))? Heapsort (обратите внимание, что обычно люди не используют кучу сортировки, так как это не очень быстро).