Деревья, преобразование выражений Лекция 11. Время, затрачиваемое алгоритмом, как функция от размера задачи, называется временной сложностью. Поведение. - презентация

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

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

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

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

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

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

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

8 Реализация бинарного дерева 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; }

9

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

11 Обходы деревьев в глубину Пусть 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 (если существует).

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

13 Обходы деревьев в глубину. Пример 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

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

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

16 Представления деревьев Определение. Левое скобочное представление дерева Т (обозначается 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) = а.

17 Скобочные представления деревьев 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

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

19 Дерево двоичного поиска Определение. Деревом двоичного поиска для множества 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.

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

21 Алгоритм просмотра дерева двоичного поиска Вход: Дерево 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; }

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

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

24 Пример

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

26 Вставка элемента в сбалансированное дерево Пусть 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

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

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

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

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

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

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

33 Повороты

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

35 Пример

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

37 A B С 4 A С 4 B

38 Пример

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

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

41 Пример

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

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

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

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

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

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

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

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

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

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

52 Виды записи выражений Префиксная (операция перед операндами) Инфиксная или скобочная (операция между операндами) Постфиксная или обратная польская (операция после операндов) Примеры: 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 – / + - постфиксная

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

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

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

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

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