Бинарные деревья поиска и рекурсия – это просто

Вопрос. Как сбалансировать несбалансированное бинароное дерево и обычное дерево (неотсортированное)?

Записи вида O(V + E) вполне себе осмысленны и используются когда мы говорим о произвольных графах. В случае же дерева V = E + 1, что действительно делает подобную запись абсолютно бессмысленной. И никакой квадратичности, как видим :-)

«Граф – это множество вершин и ребер» — общее 0_о?! Все в одну кучу что ли?! Может хотя бы: «упорядоченная пара множеств»? Не подумайте, что я придераюсь, но воспоминания, что дискретная математика не прощает таких ошибок ( читать неточностей ) ещё свежи в голове… Я указал лишь одно место, но по тексту много таких «деталей».

На практике, для обхода дерева в глубину (ну и для балансировки тоже) удобно, чтобы были восходящие связи — от детей к родителям. Тогда можно двигаться прямо по картинке, не используя стек.
Аналогично двунаправленному списку против однонаправленного.

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

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

Спасибо) разобрался благодаря вам в базовых вещах.