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

Структура данных ЛЕКЦИЯ 9 А.Асланян hayk.aslanian@gmail.com 2 Бинарные деревья поиска   Бинарное дерево поиска представляют собой структуру данных поддерживающий следующие операции  Поиск  Вставка  Удаление  Минимальный элемент  Максимальный элемент  Следующий элемент  Предыдущий элемент Основные операции в бинарном дереве поиска выполняются за время, пропорциональное его высоте 3 Бинарные деревья поиска  Бинарное дерево поиска является бинарным деревом  Каждый узел является объектом и содержит  Ключ  Сопутствующие данные  Указатель на левое поддерево  Указатель на правое поддерево  Указатель на родитель  Для каждого узла, ключ больше всех ключей левого поддерева и меньше всех ключей правого поддерева  Если дочерний или родительский узел отсутствуют, соответствующее поле содержит значение NIL 4 Примеры 5 Бинарные деревья поиска  Мы будем предполагать, что в любом двоичном дереве мы не храним повторяющиеся значения, если не указано иное  Свойство бинарного дерева поиска позволяет вывести все ключи в отсортированном порядке с помощью симметричного обхода дерева  Пример - 3 15 22 23 29 40 42 46 50 57 59 65 73 88 91 6 Бинарные деревья поиска  Обратите внимание, что мы уже можем использовать эту структуру для поиска: изучить корневой узел и, если ключ не совпадает тем, что ищем:  Если объект меньше ключа корневого узла, продолжать поиск в левом поддереве  В противном случае, продолжать поиск в правом поддереве 7 Бинарные деревья поиска  К сожалению, можно построить такое бинарное дерево поиска, что поиск займет линейное время от количества элементов 8 Бинарные деревья поиска  Все эти двоичные деревья поиска хранят одни и те же данные 9 Поиск минимального элемента  Самый «левый» элемент  Вычислительная сложность O(h) 10 Поиск максимального элемента  Самый «правый» элемент  Вычислительная сложность O(h) 11 Поиск  Поиск ключа 𝑘  𝑥 = 𝑟𝑜𝑜𝑡  Пока 𝑥 ≠ 𝑁𝐼𝐿 и 𝑘 ≠ 𝑥. 𝑘𝑒𝑦   Если 𝑘 < 𝑥. 𝑘𝑒𝑦 ⇒ 𝑥 = 𝑥. 𝑙𝑒𝑓𝑡  В противном случае 𝑥 = 𝑥. 𝑟𝑖𝑔ℎ𝑡 return 𝑥 12 Поиск  Поиск ключа 𝑘  𝑥 = 𝑟𝑜𝑜𝑡  Пока 𝑥 ≠ 𝑁𝐼𝐿 и 𝑘 ≠ 𝑥. 𝑘𝑒𝑦   Если 𝑘 < 𝑥. 𝑘𝑒𝑦 ⇒ 𝑥 = 𝑥. 𝑙𝑒𝑓𝑡  В противном случае 𝑥 = 𝑥. 𝑟𝑖𝑔ℎ𝑡 return 𝑥  Поиск 81  Вычислительная сложность O(h) 13 Поиск  Поиск ключа 𝑘  𝑥 = 𝑟𝑜𝑜𝑡  Пока 𝑥 ≠ 𝑁𝐼𝐿 и 𝑘 ≠ 𝑥. 𝑘𝑒𝑦    Если 𝑘 < 𝑥. 𝑘𝑒𝑦 ⇒ 𝑥 = 𝑥. 𝑙𝑒𝑓𝑡  В противном случае 𝑥 = 𝑥. 𝑟𝑖𝑔ℎ𝑡 return 𝑥 Поиск 35 14 Вставка   Как поиск, мы пройдем через дерево  Если мы найдем объект уже в дереве, возврат  В противном случае мы получим пустой узел  Объект будет вставлен в это место Вычислительная сложность – O(h) 15 Вставка  Вставить 52 16 Вставка  Вставить 52 17 Вставка  Вставить 40 18 Вставка  Вставить 40 19 Удаление  Удаляемый узел не всегда будет листом  Сначала нужно найти удаляемый узел  Есть три возможных сценария:  Узел является листовым узлом  У него ровно один дочерний узел  У него два дочерних узлов 20 Удаление  Стратегия удаления узла 𝑧  Если у 𝑧 нет дочериных узлов (лист), то мы удаляем его, и заменяем 𝑧 на NIL  Если у 𝑧 только один дочерний узел, то мы удаляем 𝑧 создавая новую связь между родительским и дочерним узлами узла 𝑧  Если у 𝑧 два дочерних узла, то мы находим следующий за ним узел 𝑦 (самый «левый» элемент в правом поддереве). Заменяем ключ и сопутствующие данные 𝑧-а на 𝑦. Остаток исходного правого поддерева 𝑧 становится новым поддеревом 𝑦, а левое поддерево 𝑧 становится новым левым поддеревом 𝑦 21 Удаление  Удалить 75 22 Удаление  Удалить 75 23 Удаление  Удалить 40 24 Удаление  Удалить 40 25 Удаление  Удалить 8 26 Удаление  Удалить 8 27 Удаление  Удалить 39  Нет разницы в продвижении одного узла или поддерева 28 Удаление  Удалить 39  Обратите внимание, что порядок все еще поддерживается 29 Удаление  Удалить 99 30 Удаление  Удалить 99 31 Удаление  Удалить 42  Заменить 42 минимальным объектом в правом поддереве  Удалить этот объект 32 Удаление  Удалить 42  Заменить 42 минимальным объектом в правом поддереве  Удалить этот объект 33 Удаление  Удалить 42  Заменить 42 минимальным объектом в правом поддереве  Удалить этот объект 34 Удаление  Удалить 42  Заменить 42 минимальным объектом в правом поддереве  Удалить этот объект 35 Удаление  Обратим внимание, что дерево остается бинарным деревом поиска 36 Удаление  Удалить 47  Заменить 47 минимальным объектом в правом поддереве  Удалить этот объект 37 Удаление  Удалить 47  Заменить 47 минимальным объектом в правом поддереве  Удалить этот объект 38 Удаление  Удалить 47  Заменить 47 минимальным объектом в правом поддереве  Удалить этот объект 39 Удаление  Удалить 47  Заменить 47 минимальным объектом в правом поддереве  Удалить этот объект 40 Следующий элемент  Найти следующий элемент 𝑥-а  Если 𝑥 имеет правое поддерево, то найти минимальный элемент в правом поддереве (самый «левый»)  В противном случае  𝑦 = 𝑥. 𝑝  Пока 𝑦 ≠ 𝑁𝐼𝐿 и 𝑥 == 𝑦. 𝑟𝑖𝑔ℎ𝑡    𝑥=𝑦  𝑦 = 𝑦. 𝑝 Возвращать 𝑦 Вычислительная сложность – O(h) 41 Следующий элемент  Если существует правое поддерево 42 Следующий элемент  Если не существует правое поддерево то следующий элемент находится в пути от рассматриваемого элемента до корня 43 Предыдущий элемент  Найти предыдущий элемент 𝑥-а  Если 𝑥 имеет левое поддерево, то найти максимальный элемент в левом поддереве (самый «правый»)  В противном случае  𝑦 = 𝑥. 𝑝  Пока 𝑦 ≠ 𝑁𝐼𝐿 и 𝑥 == 𝑦. 𝑙𝑒𝑓𝑡    𝑥=𝑦  𝑦 = 𝑦. 𝑝 Возвращать 𝑦 Вычислительная сложность – O(h) 44 Вычислительная сложность - O(h)  Основные операции бинарного дерева поиска имеют вычислительную сложность O(h)  Если дерево «похоже» связанного списка вычислительная сложность - O(n)  Наша цель – умешить вычислительную сложность в наихудшем случае в О(log 2 𝑛)