Pull to refresh

Comments 9

Вопрос. Как сбалансировать несбалансированное бинароное дерево и обычное дерево (неотсортированное)?
UFO just landed and posted this here
UFO just landed and posted this here
Записи вида O(V + E) вполне себе осмысленны и используются когда мы говорим о произвольных графах. В случае же дерева V = E + 1, что действительно делает подобную запись абсолютно бессмысленной. И никакой квадратичности, как видим :-)
Совершенно верно. В дереве, в отличие от графа количество ребер всегда равно количеству вершин минус 1. То есть количество ребер линейно зависит от количества вершин.
«Граф – это множество вершин и ребер» — общее 0_о?! Все в одну кучу что ли?! Может хотя бы: «упорядоченная пара множеств»? Не подумайте, что я придераюсь, но воспоминания, что дискретная математика не прощает таких ошибок ( читать неточностей ) ещё свежи в голове… Я указал лишь одно место, но по тексту много таких «деталей».
На практике, для обхода дерева в глубину (ну и для балансировки тоже) удобно, чтобы были восходящие связи — от детей к родителям. Тогда можно двигаться прямо по картинке, не используя стек.
Аналогично двунаправленному списку против однонаправленного.

В терминах графов, — это означает, что каждой вершине соответствуют наборы входящих и исходящих рёбер.

А для быстрого обхода в ширину нужны списки вершин на каждом ярусе дерева.
Либо мы можем свести задачу к последовательности обходов в глубину, опускаясь каждый раз на один ярус дальше. Это, конечно, даст квадратичное время (и логарифмическую память под стек, если рекурсивно) вместо линейной памяти под очередь.

Во всех функциях preorderPrint вместо рекурсивных вызовов

Only those users with full accounts are able to leave comments. Log in, please.