Деревья, преобразование выражений Лекция 11

Время, затрачиваемое алгоритмом, как функция от размера задачи, называется временной сложностью. Поведение этой сложности в пределе при увеличении размера задачи называется асимптотической временной сложностью. КЛАССИФИКАЦИЯ по степени сложности Линейная t(n) n [ поиск элемента в неотсортированном массиве]; Логарифмическая t(n) log n [ бинарный поиск]; t(n) n* log n [ улучшенные сортировки ]; Полиномиальные t(n) n k [ сортировки, транзит. замыкание ]; Экспоненциальная t(n) а n [ шахматные расстановки ] ; Факториальная t(n) n! [ поиск перестановок ]

Дерево (частный вид ациклического графа) Определение. (Ориентированным) деревом Т называется (ориентированный) граф G = (А,R) со специальной вершиной r А, называемый корнем, у которого степень по входу вершины r равна 0, степень по входу всех остальных вершин дерева Т равна 1, каждая вершина а А достижима из r. Дерево Т обладает следующими свойствами: Тациклический граф, для каждой вершины дерева Т существует единственный путь, ведущий из корня в эту вершину.

Поддеревом дерева Т = (А, R) называется любое дерево T' =(А', R'), у которого 1)А' непусто и содержится в A, 2)R' = (A'хA') R, 3)ни одна вершина из множества А \ А' не является потомком вершины из множества А. Ориентированный граф, состоящий из нескольких деревьев, называется лесом

Пусть Т=(A, R) – дерево, (a, b) R, тогда a – отец b, а b – сын a. Глубина или уровень вершины – длина пути от корня до этой вершины. Высота вершины – длина максимального пути от этой вершины до листа. Высота дерева – длина максимального пути от корня до листа. Глубина корня =

Бинарные деревья Упорядоченное дерево – это дерево, в котором множество сыновей каждой вершины упорядочено слева направо. Бинарное дерево – это упорядоченное дерево, в котором: 1)любой сын – либо левый либо правый, 2)любой узел имеет не более одного левого и не более одного правого сына

Бинарное дерево называется полным, если существует некоторое целое k, такое что любой узел глубины меньше k имеет как левого, так и правого сына, а если узел имеет глубину k, то он является листом

Реализация бинарного дерева typedef struсt tree { int sz;// размер int * key; // ключи struct tree *left, * right; } T_tree; T_tree * t; t = (T_tree*)malloc(sizeof(T_tree)); if(t) { t -> sz = k; t -> key =(int*)malloc(sizeof(int)*(t->sz)); t -> left = NULL; t -> right = NULL; }

Обходы дерева Обход дерева – это способ методичного исследования узлов дерева, при котором каждый узел проходится только один раз. в глубину Обходы в ширину

Обходы деревьев в глубину Пусть T – дерево, r- корень, v 1, v 2,…, v n – сыновья вершины r. 1.Прямой (префиксный ) обход: – посетить корень r; – посетить в прямом порядке поддеревья с корнями v 1, v 2,…, v n. 2.Обратный (постфиксный) обход: – посетить в обратном порядке поддеревья с корнями v 1, v 2,…, v n ; – посетить корень r. 3.Внутренний ( инфиксный) обход для бинарных деревьев: – посетить во внутреннем порядке левое поддерево корня r (если существует); – посетить корень r; – посетить во внутреннем порядке правое поддерево корня r (если существует).

Обходы деревьев в глубину. Пример 1. Прямой ОбратныйВнутренний

Обходы деревьев в глубину. Пример 2 + * a – d e / + f g c - префиксный обход a d e – * f g + c / +- постфиксный обход a * (d – e)+ (f + g) / c - инфиксный обход + * / +c d e f a g

Обход дерева в ширину - это обход вершин дерева по уровням, начиная от корня, слева направо (или справа налево). Алгоритм обхода дерева в ширину Шаг 0: Поместить в очередь корень дерева. Шаг 1: Взять из очереди очередную вершину. Поместить в очередь всех ее сыновей по порядку слева направо (справа налево). Шаг 2: Если очередь пуста, то конец обхода, иначе перейти на Шаг 1.

Обход дерева в ширину. Пример b h i jkl d ef a g bihajkldefg

Представления деревьев Определение. Левое скобочное представление дерева Т (обозначается Lrep(Т)) можно получить, применяя к нему следующие рекурсивные правила: (1)Если корнем дерева Т служит вершина а с поддеревьями T 1, Т 2,..., Т n, расположенными в этом порядке (их корни прямые потомки вершины а), то Lrep(Т) = а (Lrep (T 1 ), Lrep (Т 2 ),..., Lrep (Т n )) (2) Если корнем дерева Т служит вершина а, не имеющая прямых потомков, то Lrep (Т) = а. Определение. Правое скобочное представление Rrep(Т) дерева Т: (1)Если корнем дерева Т служит вершина а с поддеревьями T 1, Т 2,..., Т n, то Rrep(Т) = (Rrep(Т 1 ), Rrep(T 2 ),..., Rrep (Т n ))а. (2) Если корнем дерева Т служит вершина а, не имеющая прямых потомков, то Rrep(T) = а.

Скобочные представления деревьев Lrep(T) = b ( h ( a, j ( d ) ), i ( k ( e, f, g ), l ) ) Rrep(T) = ( ( a, ( d ) j ) h, ( ( e, f, g ) k, l ) i ) b b h i jkl d ef a g

Представление дерева списком прямых предков Составляется список прямых предков для вершин дерева c номерами 1, 2,..., n (именно в этом порядке). Чтобы опознать корень, будем считать, что его предокэто

Дерево двоичного поиска Определение. Деревом двоичного поиска для множества S называется помеченное двоичное дерево, каждый узел v которого помечен элементом l(v) S так, что 1)l(u) < l(v) для каждого узла u из левого поддерева узла v, 2)l(w) > l(v) для каждого узла w из правого поддерева узла v, 3)для любого элемента a S существует единственный узел v, такой что l(v) = a.

Дерево двоичного поиска. Пример Пусть S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Алгоритм просмотра дерева двоичного поиска Вход: Дерево T двоичного поиска для множества S, элемент a. Выход: true если a S, false - в противном случае. Метод: Если T =, то выдать false, иначе выдать ПОИСК (a, r), где r – корень дерева T. функция ПОИСК (a, v) : boolean { если a = l(v) то выдать true иначе если a < l(v) то если v имеет левого сына w то выдать ПОИСК (a, w) иначе выдать false; иначе если v имеет правого сына w то выдать ПОИСК (a, w) иначе выдать false; }

v oid print_tree (T_tree *t) { if (!t) return; print_tree(t->left); printf ( %s\n, t->word); print_tree(t->right); }

Сбалансированные деревья (АВЛ) Теорема. Среднее число сравнений, необходимых для вставки n случайных элементов в дерево двоичного поиска, пустое в начале, равно O(n log 2 n) для n 1. Максимальное число сравнений O(n 2 ) – для вырожденных деревьев. Дерево называется сбалансированным тогда и только тогда, когда высоты двух поддеревьев каждой из его вершин отличаются не более чем на единицу. АВЛ-деревья (1964 г. - Г.М.Адельсон-Вельский, Е.М. Ландис)

Пример

Утверждение n – количество концевых вершин m – неотрицательное целое d – длина пути от корня до вершины Дерево сблалансировано, если 1)n = 2 m d = m 2)2 m < n < 2 m d = m d = m + 1 1) 2) ( 1 2)

Вставка элемента в сбалансированное дерево Пусть r – корень, L – левое поддерево, R – правое поддерево. Предположим, что включение в L приведет к увеличению высоты на 1. Возможны три случая: 1.h L = h R 2.h L < h R 3.h L > h Rнарушен принцип сбалансированности, дерево нужно перестраивать r LR hLhL 1 hRhR

Показатель сбалансированности Операции вставки и удаления узла должны постоянно отслеживать соотношение высот левого и правого поддеревьев узла. Для хранения этой информации можно добавить поле balanceFactor, которое содержит разность высот правого и левого поддеревьев. balanceFactor = height(right subtree) - height(left subtree) В AVL-дереве показатель сбалансированности должен быть в диапазоне [-1, 1]. -1: Высота левого поддерева на 1 больше высоты правого поддерева. 0: Высоты обоих поддеревьев одинаковы. +1: Высота правого поддерева на 1 больше высоты левого поддерева.

Вставка элемента (продолжение) Процесс вставки почти такой же, что и для бинарного дерева поиска. Осуществляется рекурсивный спуск по левым и правым сыновьям, пока не встретится пустое поддерево, а затем производится пробная вставка нового узла в этом месте. Поскольку процесс рекурсивный, обработка узлов ведется в обратном порядке. При этом показатель сбалансированности родительского узла можно скорректировать после изучения эффекта от добавления нового элемента в одно из поддеревьев. Необходимость корректировки определяется для каждого узла, входящего в поисковый маршрут.

Три возможных ситуации Случай 1 Узел на поисковом маршруте изначально является сбалансированным (balanceFactor = 0). После вставки в поддерево нового элемента узел стал перевешивать влево или вправо в зависимости от того, в какое поддерево была произведена вставка. Если элемент вставлен в левое поддерево, показателю сбалансированности присваивается -1, а если в правое, то 1.

Пример Например, на пути каждый узел сбалансирован. После вставки узла 55 показатели сбалансированности изменяются.

Случай 2 Одно из поддеревьев узла перевешивает, и новый узел вставляется в более легкое поддерево. Узел становится сбалансированным.

Случай 3 Одно из поддеревьев узла перевешивает, и новый узел помещается в более тяжелое поддерево. Тем самым нарушается условие сбалансированности, так как balanceFactor выходит за пределы Чтобы восстановить равновесие, нужно выполнить поворот.

Повороты

Перебалансировка - левая ветвь перегружена A B A B 32 1

Пример

Правая ветвь левого поддерева перегружена

A B С 4 A С 4 B

Пример

Пример построения АВЛ-дерева

Красно-чёрное дерево (Red-Black-Tree, RB-Tree) Красно-чёрное дерево обладает следующими свойствами. 1) Все листья черны. 2) Все потомки красных узлов черны (запрещена ситуация с двумя красными узлами подряд). 3) На всех ветвях дерева, ведущих от его корня к листьям, число чёрных узлов одинаково. Это число называется чёрной высотой дерева. 4) Для удобства листьями красно-чёрного дерева считаются фиктивные «нулевые» узлы, не содержащие данных (NULL).

Пример

Свойства красно-чёрного дерева 1. Если h - чёрная высота дерева, то количество листьев не менее 2 h Если h - высота дерева, то количество листьев не менее 2 (h1)/2. 3. Если количество листьев N, высота дерева не больше 2log 2 N + 1

Сравнение с АВЛ-деревом Пускай высота дерева h, минимальное количество листьев N. Тогда: для АВЛ-дерева N(h) = N(h 1) + N(h 2). Поскольку N(0) = 1, N(1) = 1, N(h) растёт как последовательность Фибоначчи, следовательно, N(h) = Θ(λh), где для красно-чёрного дерева Следовательно, при том же количестве листьев красно-чёрное дерево может быть выше АВЛ-дерева, но не более чем раз.

Поиск, вставка, удаление Поиск. Поскольку красно-чёрное дерево, в худшем случае, выше, поиск в нём медленнее, но проигрыш по времени не превышает 40%. Вставка. Вставка требует до 2 поворотов в обоих видах деревьев. Однако из-за большей высоты красно-чёрного дерева вставка может занимать больше времени. Удаление. Удаление из красно-черного дерева требует до 3 поворотов, в АВЛ-дереве оно может потребовать числа поворотов до корня. Поэтому удаление из красно-чёрного дерева быстрее, чем из АВЛ-дерева. Память. АВЛ-дерева в каждом узле хранит высоту (целое число). Красно-чёрное дерево в каждом узле хранит цвет (1 бит). Таким образом, красно-чёрное дерево может быть экономичнее.

Операция вставки нового узла Чтобы вставить узел, мы сначала -ищем в дереве место, куда его следует добавить. -Новый узел всегда добавляется как лист, поэтому оба его потомка являются NULL-узлами и предполагаются черными. -После вставки красим узел в красный цвет. -После этого смотрим на предка и проверяем, не нарушается ли красно-черное свойство. Если необходимо, мы перекрашиваем узел и производим поворот, чтобы сбалансировать дерево. Вставив красный узел с двумя NULL-потомками, мы сохраняем свойство черной высоты. Однако, при этом может оказаться нарушенным свойство 3, согласно которому оба потомка красного узла обязательно черны. В нашем случае оба потомка нового узла черны по определению, поскольку они являются NULL-узлами.

Вставка нового узла Случай 1. Если отец и дядя(другой сын деда вставляемого узла) оба красные, тогда цвет отца и дяди меняется на черный, а цвет деда на красный. Таким образом проблема перемещается на 2 уровня вверх, и операция повторяется уже для деда узла. Случай 2. Если отец нового узла красный, а дядя черный, существуют два похожих подслучая. Если вставляемый узел левый сын своего отца, тогда цвет отца меняется на черный, цвет деда меняется на красный и дерево поворачивается направо вокруг отца нового узла. Таким образом нарушение полностью устраняется и алгоритм завершается. Случай 3. Если новый узел правый сын своего отца, то сначала осуществляется левый поворот вокруг отца и затем выполняется все как в случае 2. Обратите внимание на распространение влияния красного узла на верхние узлы дерева. В самом конце корень мы красим в черный цвет корень дерева. Если он был красным, то при этом увеличивается черная высота дерева.

Красный предок, красный "дядя" Простое перекрашивание избавляет нас от красно-красного нарушения. После перекраски нужно проверить "дедушку" нового узла (узел B), поскольку он может оказаться красным.

Красный предок, черный "дядя"

Удаление узла Если удаляемый узел красный все правила сохраняются и все прекрасно. Если же удаляемый узел черный, требуется значительное количество кода, для поддержания дерева частично сбалансированным. Как и в случае вставки в красно-черное дерево, здесь также существует несколько различных случаев.

Библиотека С++ Класс AVL-деревьев исторически был первым примером использования сбалансированных деревьев. В настоящее время, однако, более популярен класс красно-черных деревьев. Именно красно-черные деревья используются, например, в реализации множества и нагруженного множества (классы set и map), которая входит в стандартную библиотеку классов языка C++.

Связь с B-деревьями RB- дерево можно рассматривать как двоичное дерево, построенное из B-дерева с максимальным количеством потомков у любой вершины = 4, по следующим правилам: 1) Каждый узел окрашен либо в красный, либо в чёрный цвет. 2) Вершина с количеством потомков 2 переносится в бинарное дерево без изменений и окрашивается в чёрный цвет. 3) В вершине с количеством потомков = 3 первый потомок присоединяется непосредственно, а другие два - через соединительный узел, соединительные узлы окрашиваются в красный цвет, остальные остаются чёрными. 4) К вершине с количеством потомков = 4 потомки присоединяются через два Соединительных узла красного цвета (по два к каждому). Таким образом получаем бинарное дерево, являющееся моделью B-дерева с максимальным количеством потомков у вершины = 4. В исходном B-дереве (так как оно сбалансировано) все пути от корня до любого листа имеют одинаковую длину. По построению очевидно, что любой путь в RB- дереве возрастает не более чем в два раза. Таким образом, можем получить минимальный путь, равным по длине пути в исходном дереве, и максимальный, превышающий по длине путь в исходном дереве в два раза.

Виды записи выражений Префиксная (операция перед операндами) Инфиксная или скобочная (операция между операндами) Постфиксная или обратная польская (операция после операндов) Примеры: a + (f – b * c / (z – x) + y) / (a * r – k) - инфиксная +a / + – f /*b c – z x y –*a r k - префиксная a f b c * z x – / – y + a r * k – / + - постфиксная

Перевод из инфиксной формы в постфиксную Вход: строка, содержащая арифметическое выражение, записанное в инфиксной форме Выход: строка, содержащая то же выражение, записанное в постфиксной форме (обратной польской записи). Обозначения: числа, строки (идентификаторы) – операнды; Знаки операцийПриоритеты операций ( 1 ) 2 = 3 +, – 4 *, / 5

Алгоритм Шаг 0: Взять первый элемент из входной строки и поместить его в X. Выходная строка и стек пусты. Шаг 1: Если X – операнд, то дописать его в конец выходной строки. Если X = (, то поместить его в стек. Если X = ), то вытолкнуть из стека и поместить в конец выходной строки все элементы до первой встреченной открывающей скобки. Эту скобку вытолкнуть из стека. Если X – знак операции, отличный от скобок, то пока стек не пуст, и верхний элемент стека имеет приоритет, больший либо равный приоритету X, вытолкнуть его из стека и поместить в выходную строку. Затем поместить X в стек. Шаг 2: Если входная строка не исчерпана, то поместить в X очередной элемент входной строки и перейти на Шаг 1, иначе пока стек не пуст, вытолкнуть из стека содержимое в выходную строку.

Пример Входная строка: a + ( f – b * c / ( z – x ) + y ) / ( a * r – k ) Выходная строка: Стек: a+(fb*c/(z x )+y) /( a*rk) X =

Вычисления на стеке Вход: строка, содержащая выражение, записанное в постфиксной форме. Выход: число - значение заданного выражения. Алгоритм: Шаг 0: Стек пуст. Взять первый элемент из входной строки и поместить его в X. Шаг 1: Если X – операнд, то поместить его в стек. Если X – знак операции, то вытолкнуть из стека два верхних элемента, применить к ним соответствующую операцию, результат положить в стек. Шаг 2: Если входная строка не исчерпана, то поместить в X очередной элемент входной строки и перейти на Шаг 1, иначе вытолкнуть из стека результат вычисления выражения.

Пример Входная строка: * 4 2 / 4 / + 1 Стек: 52*234/1+ / 4 =