Алгоритмы и структуры данных

Метод турниров можно использовать для решения задач, в которых информация, полученная в результате первого прохода по данным, может облегчить последующие проходы. Поиск наибольшего значения Если воспользоваться им для поиска наибольшего значения, то потребуется построение бинарного дерева, все элементы которого являются листьями. На каждом уровне два элемента объединены в пару, причем наибольший из двух элементов копируется в родительский узел. Процесс повторяется до достижения корневого узла. Полное дерево турнира для фиксированного набора данных: Алгоритм поиска второго по величине элемента списка из N значений, требующий около N сравнений В результате каждого сравнения мы получаем "победителя" и "проигравшего". Проигравших мы забываем, и вверх по дереву двигаются только победители. Всякий элемент, за исключением наибольшего, "проигрывает" в точности в одном сравнении. Поэтому для построения дерева турнира требуется N-1 сравнение. Вт...

Бинарное дерево представляет собой структуру, в которой каждый узел (или вершина) имеет не более двух узлов-потомков и в точности одного родителя. Самый верхний узел дерева является единственным узлом без родителей; он называется корневым узлом, или корнем. Бинарное дерево с N узлами имеет не меньше ⌊log 2 N + 1⌋ уровней (при максимально плотной упаковке узлов). Например, у полного бинарного дерева с 15 узлами один корень, два узла на втором уровне, четыре узла на третьем уровне и восемь узлов на четвертом уровне; наше равенство также даёт ⌊log 2 15⌋ + 1 = ⌊3,9⌋ + 1 = 4 уровня. Добавление еще одного узла к дереву приведет к появлению нового уровня, и их число станет равным ⌊log 2 16⌋ + 1 = ⌊4⌋ + 1 = 5. В самом большом бинарном дереве с N узлами N уровней: у каждого узла этого дерева в точности один потомок (и само дерево представляет собой список). Если уровни дерева занумеровать, считая, что корень лежит на уровне 1, то на уровне с номером k лежит не более чем 2 k - 1 узл...