До сих пор мы рассматривали структуры данных, данные в которых располагаются линейно. В связном списке — от первого узла к единственному последнему. В динамическом массиве — в виде непрерывного блока.
В этой части мы рассмотрим совершенно новую структуру данных — дерево. А точнее, двоичное (бинарное) дерево поиска (binary search tree). Бинарное дерево поиска имеет структуру дерева, но элементы в нем расположены по определенным правилам.
Также смотрите другие материалы этой серии: стеки и очереди, динамический массив, связный список, оценка сложности алгоритма, сортировка и множества.
Для начала мы рассмотрим обычное дерево.
Деревья
Дерево — это структура, в которой у каждого узла может быть ноль или более подузлов — «детей». Например, дерево может выглядеть так:

Структура организации
Это дерево показывает структуру компании. Узлы представляют людей или подразделения, линии — связи и отношения. Дерево — это самый эффективный представления и хранения такой информации.
Для решения определим 1. Время передачи по высокоскоростному каналу 2. Время передачи по низкоскоростному каналу 3. Время для получения первых 1024 Кб 4. Всё сложим.
До сих пор мы рассматривали структуры данных, данные в которых располагаются линейно. В связном списке — от первого узла к единственному последнему. В динамическом массиве — в виде непрерывного блока.
В этой части мы рассмотрим совершенно новую структуру данных — дерево. А точнее, двоичное (бинарное) дерево поиска (binary search tree). Бинарное дерево поиска имеет структуру дерева, но элементы в нем расположены по определенным правилам.
Также смотрите другие материалы этой серии: стеки и очереди, динамический массив, связный список, оценка сложности алгоритма, сортировка и множества.
Для начала мы рассмотрим обычное дерево.
Деревья
Дерево — это структура, в которой у каждого узла может быть ноль или более подузлов — «детей». Например, дерево может выглядеть так:

Структура организации
Это дерево показывает структуру компании. Узлы представляют людей или подразделения, линии — связи и отношения. Дерево — это самый эффективный представления и хранения такой информации.
1. Время передачи по высокоскоростному каналу
2. Время передачи по низкоскоростному каналу
3. Время для получения первых 1024 Кб
4. Всё сложим.
2^20 бит/с = 2^20 / 8 / 1024 Кбайт/с = 2^20 / 2^3 / 2^10 = 2^7 Кбайт/с
2^13 бит/с = 2^13 / 8 / 1024 Кбайт/с = 2^13 / 2^3 / 2^10 = 2^0 = 1 Кбайт/с
10 Мб равно 10*1024 Кбайт = 10*2^10 Кбайт.
По высокоскоростному каналу файл будет передаваться
(10*2^10) / 2^7 = 10*2^3 = 80 секунд
По низкоскоростному каналу файл будет передаваться
(10*2^10) / 1 = 10*2^10 = 10240 секунд.
Первые 1024 Кбайт будут передаваться
2^10 / 2^7 = 8 секунд
Общее время 80+10240+8 = 10328 секунд.