Справочник от Автор24
Высшая математика

Конспект лекции
«Деревья двоичного поиска»

Справочник / Лекторий Справочник / Лекционные и методические материалы по высшей математике / Деревья двоичного поиска

Выбери формат для чтения

pdf

Конспект лекции по дисциплине «Деревья двоичного поиска», pdf

Файл загружается

Файл загружается

Благодарим за ожидание, осталось немного.

Конспект лекции по дисциплине «Деревья двоичного поиска». pdf

txt

Конспект лекции по дисциплине «Деревья двоичного поиска», текстовый формат

Дисциплина «Алгоритмы и структуры данных» Лекция № 15 Деревья двоичного поиска Филатов Вячеслав Валерьевич к.т.н., доцент кафедры КБ-2 «Прикладные информационные технологии» Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. n a<n b>n Т2 Т1 Допустим дана последовательность 8 3 10 1 6 14 4 13 для неё дерево двоичного поиска будет выглядеть так: 7 Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. n (a < n) (b > n) Допустим дана последовательность 8 3 10 1 6 14 4 13 7 Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. n (a < n) (b > n) Допустим дана последовательность 8 3 10 1 6 14 4 13 7 Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. n (a < n) (b > n) Допустим дана последовательность 8 3 10 1 6 14 4 13 7 Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. n (a < n) (b > n) Допустим дана последовательность 8 3 10 1 6 14 4 13 7 Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. n (a < n) (b > n) Допустим дана последовательность 8 3 10 1 6 14 4 13 7 Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. n (a < n) (b > n) Допустим дана последовательность 8 3 10 1 6 14 4 13 7 Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. n (a < n) (b > n) Допустим дана последовательность 8 3 10 1 6 14 4 13 7 Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. n (a < n) (b > n) Допустим дана последовательность 8 3 10 1 6 14 4 13 7 Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. N (a<N) (a>N) Допустим дана последовательность 8 3 10 1 6 14 4 13 7 Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. N (a<N) (a>N) Допустим дана последовательность 8 3 10 1 6 14 4 13 7 Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. N (a<N) (a>N) Допустим дана последовательность 8 3 10 1 6 14 4 13 7 Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. N (a<N) (a>N) Допустим дана последовательность 8 3 10 1 6 14 4 13 7 Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. N (a<N) (a>N) Допустим дана последовательность 8 3 10 1 6 14 4 13 7 Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. N (a<N) (a>N) Допустим дана последовательность 8 3 10 1 6 14 4 13 7 Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. N (a<N) (a>N) Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. N (a<N) (a>N) Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. N (a<N) (a>N) Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. N (a<N) (a>N) В чем ошибка? Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. N (a<N) (a>N) Поиск элемента для ДДП Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей функцией, которая принимает в качестве параметров корень поддерева (указатель на текущий узел) и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Поиск элемента для ДДП Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей функцией, которая принимает в качестве параметров корень поддерева (указатель на текущий узел) и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Поиск элемента для ДДП Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей функцией, которая принимает в качестве параметров корень поддерева (указатель на текущий узел) и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Будет искать требуемое значение?.. Поиск элемента для ДДП Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей функцией, которая принимает в качестве параметров корень поддерева (указатель на текущий узел) и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. А ошибка будет?.. (… и когда?) Поиск элемента для ДДП Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей функцией, которая принимает в качестве параметров корень поддерева (указатель на текущий узел) и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Что произойдет, если элемент будет не найден? Поиск элемента для ДДП Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей функцией, которая принимает в качестве параметров корень поддерева (указатель на текущий узел) и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Поиск минимального и максимального элемента в поддереве Поиск максимального элемента в поддереве Поиск минимального элемента в поддереве Возможные ситуации удаления Для удаления узла из бинарного дерева поиска нужно рассмотреть три возможные ситуации: 1) Если у узла нет сыновей (дочерних узлов), то у его родителя нужно просто заменить указатель на null, а сам узел удаляем из памяти. 2) Если у узла есть только один сын, то нужно создать новую связь между родителем удаляемого узла и его сыном, а сам узел физически удалить из памяти. 3) Если у узла (node_t* Node) есть два сына, то не удаляя узел из структуры дерева, надо заменить удаляемое значение либо на максимальное значение в левом поддереве рассматриваемого узла (то есть (*Node)->value = MaxValue((*Node)->left), либо на минимальное значение в правом поддереве рассматриваемого узла (*Node)->value = MinValue((*Node)->rigth), а сам узел, содержащий минимальное (или максимальное) значение физически удалить из дерева, согласно шагам 1 или 2 (так гарантированно у узла с таким значением нет либо одного, либо обоих сыновей). Возможные ситуации удаления Рандомизированное двоичное дерево поиска Сбалансированное двоичное дерево поиска Сбалансированное двоичное дерево поиска — это двоичное дерево поиска с логарифмической высотой. В сбалансированном двоичном дереве поиска операции поиска, вставки и удаления выполняются за логарифмическое время (так как путь к любому листу от корня не более логарифма). Сбалансированное двоичное дерево поиска В вырожденном случае несбалансированного двоичного дерева поиска, например, когда в пустое дерево вставлялась отсортированная последовательность, дерево превратится в линейный список, и операции поиска, вставки и удаления будут выполняться за линейное время. Поэтому балансировка дерева крайне важна. Технически балансировка осуществляется поворотами частей дерева при вставке нового элемента, если вставка данного элемента нарушила условие сбалансированности. 10 20 30 40 50 Повороты Необходимой составляющей рандомизации является применение специальной вставки нового ключа, в результате которой новый ключ оказывается в корне поддерева. Для реализации вставки в корень нам потребуется функция поворота, которая производит локальное преобразование дерева. y x y x C A A B B A<x<B<y<C C Левый поворот X y y x A C B C A A<x<B<y<C B Правый поворот x y y x A C B C A A<x<B<y<C B Рандомизированная вставка Известно, что если заранее перемешать все ключи и потом построить из них дерево (ключи вставляются по стандартной схеме в полученном после перемешивания порядке), то построенное дерево окажется неплохо сбалансированным (его высота будет порядка 2log2n против log2n для идеально сбалансированного дерева). Заметим, что в этом случае корнем может с одинаковой вероятностью оказаться любой из исходных ключей. Что делать, если мы заранее не знаем, какие у нас будут ключи (например, они вводятся в систему в процессе использования дерева)? Ответ Любой ключ (в том числе и тот, который мы сейчас должны вставить в 1 дерево) может оказаться корнем с вероятностью 𝑛+1 (n — размер дерева до вставки), то мы выполняем с указанной вероятностью вставку в корень, а с вероятностью 1 − 1 𝑛+1 — рекурсивную вставку в правое или левое поддерево в зависимости от значения ключа в корне в подходящее место (обвчное добавление узла в дерево двоичного поиска). Вставка в корень Сначала рекурсивно вставляем новый ключ в корень левого или правого поддеревьев (в зависимости от результата сравнения с корневым ключом) и выполняем правый (левый) поворот, который поднимает нужный нам узел в корень дерева. k x x k Правый поворот k x Удаление узлов Удалять будем по ключу — ищем узел с заданным ключом (все ключи различны) и удаляем этот узел из дерева. Сначала ищем, а дальше делаем так — объединяем левое и правое поддеревья найденного узла, удаляем узел, возвращаем корень объединенного дерева. X A Y B A+ B Объединение деревьев Пусть даны два дерева поиска с корнями X и Y, причем любой ключ первого дерева меньше любого ключа во втором дереве. Требуется объединить эти два дерева в одно. В качестве корня нового дерева можно взять любой из двух корней, пусть это будет X. Тогда левое поддерево X можно оставить как есть, а справа к X подвесить объединение двух деревьев — правого поддерева x и всего дерева Y (они удовлетворяют всем условиям задачи). С другой стороны, с тем же успехом мы можем сделать корнем нового дерева узел Y. В рандомизированной реализации выбор между этими альтернативами делается случайным образом. Пусть размер левого дерева равен n, правого — m. Тогда X выбирается новым корнем с вероятностью 𝑛 𝑚 , а Y — с вероятностью . 𝑛+𝑚 𝑛+𝑚 X A Y C B X A A<x<B<C B+ C Оптимальные ДДП Понятие оптимального дерева двоичного поиска В двоичном дереве поиск одних элементов может происходить чаще, чем других, то есть существуют вероятности pk поиска k -го элемента и для различных элементов эти вероятности неодинаковы. Можно предположить, что поиск в дереве в среднем будет более быстрым, если те элементы, которые ищут чаще, будут находиться ближе к корню дерева. Пусть даны 2n+1 вероятностей p1,p2,...,pn, q0,q1,...,qn, где pi – вероятность того, что аргументом поиска является Ki элемент; qi – вероятность того, что аргумент поиска лежит между вершинами Ki и Ki+1 ; q0 – вероятность того, что аргумент поиска меньше, чем значение элемента K1 ; qn – вероятность того, что аргумент поиска больше, чем Kn. Тогда цена дерева поиска C будет определяться следующим образом: где – уровень узла j, а – уровень листа K Оптимальные деревья поиска Дерево поиска называется оптимальным, если его цена минимальна. То есть оптимальное бинарное дерево поиска – это бинарное дерево поиска, построенное в расчете на обеспечение максимальной производительности при заданном распределении вероятностей поиска требуемых данных. Существует подход построения оптимальных деревьев поиска, при котором элементы вставляются в порядке уменьшения частот, что дает в среднем неплохие деревья поиска. Однако этот подход может дать вырожденное дерево поиска, которое будет далеко от оптимального. Еще один подход состоит в выборе корня k таким образом, чтобы максимальная сумма вероятностей для вершин левого поддерева или правого поддерева была настолько мала, насколько это возможно. Такой подход также может оказаться плохим в случае выбора в качестве корня элемента с малым значением pk. Оптимальные деревья поиска Припишем каждой вершине дерева Vi вес wi, пропорциональный частоте поиска этой вершины. Сумма весов всех вершин дает вес дерева W. Каждая вершина Vi расположена на высоте hi, корень расположен на высоте 1. Высота вершины равна количеству операций сравнения, необходимых для поиска этой вершины. Определим средневзвешенную высоту дерева с n вершинами следующим образом: hср=(w1h1+w2h2+…+wnhn)/W. Дерево поиска, имеющее минимальную средневзвешенную высоту, называется деревом оптимального поиска. Оптимальные деревья поиска Пример. Рассмотрим множество из трех ключей V1=1, V2=2, V3=3 со следующими весами: w1=60, w2=30, w3=10, W=100. Эти три ключа можно расставить в дереве поиска пятью различными способами. Легко видеть, что минимальной средневзвешенной высотой обладает дерево 1, которое представляет собой список или вырожденное дерево. Дерево 3 не является деревом оптимального поиска, хотя представляет собой идеально сбалансированное дерево. Очевидно, для минимизации средней длины пути поиска нужно стремится располагать наиболее часто используемые вершины ближе к корню дерева. Пример построения оптимального деревья поиска Рассмотрим пример построения дерева оптимального бинарного поиска для символов строки РОВПОВАЕЕКУВИЛРКТОАНАНА. • Всего символов в строке 23, т.е. W=23. • Различные символы определяют различные вершины дерева. • Частоты вхождения символов (веса) приведены в таблице. keyТаблица. К У РЧастоты А П вхождения О В Е символов Л Н И вТ wстроку 2 1 2 4 1 3 3 2 1 2 1 1 Пример построения оптимального деревья поиска Рассмотрим пример построения дерева оптимального бинарного поиска для символов строки РОВПОВАЕЕКУВИЛРКТОАНАНА. • Всего символов в строке 23, т.е. W=23. • Различные символы определяют различные вершины дерева. • Частоты вхождения символов (веса) приведены в таблице. keyТаблица. К У РЧастоты А П вхождения О В Е символов Л Н И вТ wстроку 2 1 2 4 1 3 3 2 1 2 1 1 Пример построения оптимального деревья поиска Рассмотрим пример построения дерева оптимального бинарного поиска для символов строки РОВПОВАЕЕКУВИЛРКТОАНАНА. • Всего символов в строке 23, т.е. W=23. • Различные символы определяют различные вершины дерева. • Частоты вхождения символов (веса) приведены в таблице. keyТаблица. К У РЧастоты А П вхождения О В Е символов Л Н И вТ wстроку 2 1 2 4 1 3 3 2 1 2 1 1 Вычислим средневзвешенную высоту построенного дерева P=4.1+3.2+3.3+2.3+2.4+1.4+1.4+2.5+2.5+1.5+1.6+1.6=78 hср=P/W=78/23=3,39 АВЛ-дерево Определение Идеально сбалансированным называется дерево, у которого для каждой вершины выполняется требование: число вершин в левом и правом поддеревьях различается не более чем на 1. Однако идеальную сбалансированность довольно трудно поддерживать. В некоторых случаях при добавлении/удалении может потребоваться значительная перестройка дерева, не гарантирующая логарифмической сложности. Поэтому в 1962 году два советских математика Г.М. Адельсон-Вельский и Е.М. Ландис ввели менее строгое определение сбалансированности и доказали, что при таком определении можно написать программы добавления/удаления, имеющие логарифмическую сложность и сохраняющие дерево сбалансированным. Такое дерево получило название АВЛ-дерево (AVL-дерево) по первым буквам фамилий авторов. • Дерево считается сбалансированным по АВЛ (в дальнейшем просто «сбалансированным»), если для каждой вершины выполняется требование: высота левого и правого поддеревьев различаются не более, чем на 1. • Не всякое сбалансированное дерево идеально сбалансировано, но всякое идеально сбалансированное дерево сбалансировано. Вращение и балансировка При операциях добавления и удаления может произойти нарушение сбалансированности дерева. В этом случае потребуются некоторые преобразования, не нарушающие упорядоченности дерева и способствующие лучшей сбалансированности. Различают малое (левое/правое) и большое (левое/правое) вращения. Предварительно договоримся, что в каждой вершине дерева помимо значения элемента будем хранить показатель сбалансированности в данной вершине. Показатель сбалансированности вершины – это разница между высотами правого и левого поддеревьев данной вершины. Малое вращение Пусть вершина a имеет правого потомка b. Обозначим через P левое поддерево вершины a, через Q и R – левое и правое поддеревья вершины b. Упорядоченность дерева требует, чтобы P < a < Q < b < R. Точно того же требует упорядоченность дерева с корнем b, его левым потомком a, в котором P и Q – левое и правое поддеревья a, R – правое поддерево b. Поэтому первое дерево можно преобразовать во второе, не нарушая упорядоченности. Такое преобразование называется малым правым вращением. Аналогично определяется симметричное ему малое левое вращение. После вращения, необходимо актуализировать высоты поддеревьев (функция FIXHeight()). a b a b P R Q R P Q Большое вращение Пусть b – правый потомок a, c – левый потомок b, P – левое поддерево a, Q и R – левое и правое поддеревья c, S – правое поддерево b. Тогда P < a < Q < c < R < b < S. Такой же порядок соответствует дереву с корнем c, имеющим левого потомка a и правого потомка b, для которого P и Q – поддеревья вершины a, а R и S – поддеревья вершины b. Соответствующее преобразование будем называть большим правым вращением. Аналогично определяется симметричное ему большое левое вращение. a c a b b P c S Q R P Q R S Красно-черное дерево Определение Красно-черное дерево представляет собой бинарное дерево поиска с одним дополнительным битом цвета в каждом узле: цвет узла может быть либо красным, либо черным. В соответствии с накладываемыми на узлы ограничениями, ни один путь в красно-черном дереве не отличается от другого по длине более чем в два раза, так что красно-черные деревья являются приближенно сбалансированными. Каждый узел дерева содержит поля – – – – – nodeColor, left, right, parent, data. Если не существует дочернего или родительского узла по отношению к данному, соответствующий указатель принимает значение leaf (null, nullptr). Мы будем рассматривать эти значения leaf (null, nullptr) как указатели на внешние узлы (листья) бинарного дерева поиска. При этом все узлы, содержащие поле ключа, становятся внутренними узлами дерева. Принцип формирования КЧД Бинарное дерево поиска является красно-черным деревом, если оно удовлетворяет следующим красно-черным свойствам: 1. 2. 3. 4. 5. Каждый узел является красным или черным. Корень дерева является черным. Каждый лист дерева (leaf) является черным. Если узел – красный, то оба его дочерние узла – черные. Для каждого узла все пути от него до листьев, являющихся потомками данного узла, содержат одно и то же количество черных узлов. АТД «Красно-черное дерево» АТД «Красно-черное дерево» АТД «Красно-черное дерево» АТД «Красно-черное дерево» АТД «Красно-черное дерево» Спасибо за внимание!

Рекомендованные лекции

Смотреть все
Информатика

Предметная область теоретической информатики

Теоретические основы информационных процессов И СИСТЕМ введение из истории науки. В 1948 году вышла в свет работа Клода Шеннона «Математическая теория...

Информатика

Теоретические основы информационных процессов и систем

Теоретические основы информационных процессов И СИСТЕМ введение из истории науки. В 1948 году вышла в свет работа Клода Шеннона «Математическая теория...

Программирование

Динамические структуры данных: деревья. Двоичные упорядоченные деревья. Алгоритмы обхода дерева

Лекция 6. Динамические структуры данных (продолжение) План лекции: • Деревья. Двоичные упорядоченные деревья • Алгоритмы обхода дерева • Операции с уп...

Программирование

Динамические структуры данных

Лекция 5. Динамические структуры данных План лекции: • Списки. Операции со списком. • Стеки. Очереди. Деки. • Деревья. Реализация деревьев. Динамическ...

Информатика

Технологии поиска информации

Технологии обработки информации. Лекция 10. Технологии поиска информации Содержание  Понятие поиска  Виды поиска  Оценка эффективности  Методы и с...

Информатика

Информатика

Оглавление Лекция.1. Язык Си 3 Технология разработки программ 3 Базовые элементы языка Си 4 Представление данных в Си 5 Лекция.2. Встроенные типы данн...

Информатика

Бинарные деревья поиска

Бинарные деревья поиска Лекция 7 АТД «Словарь» (dictionary) ▪ Словарь (dictionary) – структура данных для хранения пар вида «ключ» – «значение» (key –...

Информационные технологии

Технология программирования. Проектирование программного обеспечения

Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образ...

Автор лекции

Бугаков П. Ю.

Авторы

Программирование

Бинарные деревья поиска

Структура данных ЛЕКЦИЯ 9 А.Асланян [email protected] 2 Бинарные деревья поиска   Бинарное дерево поиска представляют собой структуру данных п...

Программирование

Функциональное и логическое программирование

Федеральное агентство связи Сибирский государственный университет телекоммуникаций и информатики М.Ю. Галкина Функциональное и логическое программиров...

Автор лекции

Галкина М. Ю.

Авторы

Смотреть все