Поговаривали, будто давным-давно кто-то из Туков взял себе жену из эльфов. Глупости, конечно, но и до сих пор во всех Туках и в самом деле проскальзывало что-то не совсем хоббитовское: время от времени кто-нибудь из клана Туков пускался на поиски приключений. Вот и Бильбо, единственный сын Беладонны Тук, в замужестве Бэггинс, по виду и всем повадкам точная копия своего солидного благопристойного папаши, получил от Туков в наследство какую-то странность, которая только ждала случая себя проявить. Напишите программу, которая будет искать во введенных строках странность в любом виде (достаточно проверить подстроку странност А если найдет, то выведет среднее арифметическое их длин. Формат ввода Вводятся строки, пока не будет введена строка ЭЛЬФ. Формат вывода Вывести среднее значений длин строк, в которых есть странность. Если таких строк нет, вывести 0. Ничего округлять не нужно. ПИТОН

До сих пор мы рассматривали структуры данных, данные в которых располагаются линейно. В связном списке — от первого узла к единственному последнему. В динамическом массиве — в виде непрерывного блока.

В этой части мы рассмотрим совершенно новую структуру данных — дерево. А точнее, двоичное (бинарное) дерево поиска (binary search tree). Бинарное дерево поиска имеет структуру дерева, но элементы в нем расположены по определенным правилам.

Также смотрите другие материалы этой серии: стеки и очереди, динамический массив, связный список, оценка сложности алгоритма, сортировка и множества.

Для начала мы рассмотрим обычное дерево.

Деревья

Дерево — это структура, в которой у каждого узла может быть ноль или более подузлов — «детей». Например, дерево может выглядеть так:



Структура организации

Это дерево показывает структуру компании. Узлы представляют людей или подразделения, линии — связи и отношения. Дерево — это самый эффективный представления и хранения такой информации.