Бинарное дерево

Cтраница 4

Таким образом, прошитое бинарное дерево с течки зрения его прохождения имеет бесспорные преимущества перед непрошитым. Праща, в некоторых приложениях вследствие увеличения времени, необходимого для включения и исключения узлов в прошитом дереве, эти преимущества не столь значительны. Кроме того, иногда бывает возможно сэкономить объем памяти за счет того что вместо всех одинаковых поддеревьев мы сохраняем лишь одно такое поддерево в непрошитом представлении, тогда как прошитые деревья с частично перекрывающимися поддеревьями требуют строгого сохранения всей структуры дерева. [46]

Граф FI представляет собой симметричное бинарное дерево с максимальным использован. В графе Гз, наоборот мальная и всего два полностью различающихся та. Простую линейную структуру представляет i ром число маршрутов при любых рассмотренных ления определяется числом ветвлений. При выдел по первому критерию X ] в графе Гз число марш от числа вершин и определяется повторяющ между узлами. [47]

В стандартном представлении бинарного дерева используются узлы с двумя связями: левой связью с левым поддеревом и правой связью с правым поддеревом. Нулевые связи соответствуют внешним узлам. [48]

Это рекурсивное определение бинарного дерева следует внимательно разобрать. [49]

Нумерация Штралера узлов бинарного дерева определяется следующим образом. [50]

Пример тою, как может уменьшаться длина внешних путей, если L / 4 - 2 в лемме. [51]

Лемма 2.1. У расширенного бинарного дерева с п внутренними узлами и минимальной длиной внешних путей все внешние узлы находятся на уровнях / и / 1, где / - некоторое целое число. Такое дерево называется полностью сбалансированным бинарным деревом с п внутренними узлами. [52]

К счастью, существует бинарное дерево, определенное для произвольного количества участников, которое позволяет избежать обеих этих опасностей. Соответствующие последовательные исключения порождают оптимальное по Парето, анонимное и монотонное правило голосования. Это замечательное дерево называется деревом многоэтапного исключения. [53]

Страницы: 1 2 3 4