Деревья двоичного поиска

👀 313 просмотров
📌 244 загрузки

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

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

Загружаем конспект в формате pdf

Это займет всего пару минут! А пока ты можешь прочитать работу в формате Word 👇

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

Дисциплина «Алгоритмы и структуры данных» Лекция № 15 Деревья двоичного поиска Филатов Вячеслав Валерьевич к.т.н., доцент кафедры КБ-2 «Прикладные информационные технологии» Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. n an Т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 (aN) Допустим дана последовательность 8 3 10 1 6 14 4 13 7 Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. N (aN) Допустим дана последовательность 8 3 10 1 6 14 4 13 7 Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. N (aN) Допустим дана последовательность 8 3 10 1 6 14 4 13 7 Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. N (aN) Допустим дана последовательность 8 3 10 1 6 14 4 13 7 Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. N (aN) Допустим дана последовательность 8 3 10 1 6 14 4 13 7 Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. N (aN) Допустим дана последовательность 8 3 10 1 6 14 4 13 7 Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. N (aN) Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. N (aN) Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. N (aN) Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. N (aN) В чем ошибка? Двоичное дерево поиска Двоичное дерево поиска (ДДП) организуется по принципу – для произвольного внутреннего узла в левое поддерево будем помещать меньшие значения, а в правые – большие. N (aN) Поиск элемента для ДДП Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей функцией, которая принимает в качестве параметров корень поддерева (указатель на текущий узел) и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Поиск элемента для ДДП Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей функцией, которая принимает в качестве параметров корень поддерева (указатель на текущий узел) и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Поиск элемента для ДДП Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей функцией, которая принимает в качестве параметров корень поддерева (указатель на текущий узел) и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Будет искать требуемое значение?.. Поиск элемента для ДДП Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей функцией, которая принимает в качестве параметров корень поддерева (указатель на текущий узел) и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. А ошибка будет?.. (… и когда?) Поиск элемента для ДДП Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей функцией, которая принимает в качестве параметров корень поддерева (указатель на текущий узел) и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Что произойдет, если элемент будет не найден? Поиск элемента для ДДП Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей функцией, которая принимает в качестве параметров корень поддерева (указатель на текущий узел) и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Поиск минимального и максимального элемента в поддереве Поиск максимального элемента в поддереве Поиск минимального элемента в поддереве Возможные ситуации удаления Для удаления узла из бинарного дерева поиска нужно рассмотреть три возможные ситуации: 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