Деревья поиска. Вставка и удаление: два простых случая и один хитрый
NULL) - именно туда добавляем новый узел. Удаление сложнее и делится на 3 случая: лист (просто убрать), один потомок (заменить узел на него) и два потомка (заменить узел на самый правый узел левого поддерева ИЛИ самый левый правого).
Деревья поиска. Вставка и удаление: включение нового ключа
Для добавления нового элемента в дерево поиска необходимо найти для него подходящее место так, чтобы не нарушилось основное свойство дерева (слева меньше, справа больше). Процедура вставки идентична процедуре поиска: мы спускаемся по дереву, пока не наткнемся на пустой указатель (NULL). Именно на это место мы выделяем память под новый узел и прикрепляем его к дереву.
/* Рекурсивная вставка (поиск с включением) */
void insert(int x, struct node** p) {
if (*p == NULL) {
/* Нашли пустое место, создаем узел */
*p = (struct node*)malloc(sizeof(struct node));
(*p)->key = x;
(*p)->l = NULL;
(*p)->r = NULL;
} else if (x < (*p)->key) {
insert(x, &(*p)->l); /* Идем влево */
} else if (x > (*p)->key) {
insert(x, &(*p)->r); /* Идем вправо */
}
/* Если x == (*p)->key, элемент уже есть (дубликат игнорируется) */
}
Удаление элемента (исключение): три случая
Удаление элемента (исключение) - значительно более сложная операция, так как она может нарушить целостность древовидной структуры. При удалении узла необходимо рассмотреть три возможных случая:
- Узел является листом (не имеет потомков): Самый простой случай. Узел просто удаляется из памяти, а указатель родителя на него устанавливается в
NULL. - Узел имеет только одного потомка: Удаляемый узел заменяется на своего единственного потомка. Мы как бы "пробрасываем" ссылку от родителя удаляемого узла напрямую к его потомку.
- Узел имеет двух потомков: Наиболее сложный случай. Удаляемый узел нельзя просто стереть, иначе мы потеряем связи с двумя ветвями дерева. Вместо него ставится узел-заместитель, который сохранит правильность дерева поиска. Таким узлом может быть либо самый правый элемент левого поддерева (максимум среди меньших), либо самый левый элемент правого поддерева (минимум среди больших).
Визуализация: Удаление узла с двумя потомками
Рассмотрим удаление корня 50 из того же дерева. Мы находим самый правый узел в левом поддереве (в данном случае это 35) и заменяем удаляемый узел на него. При этом дерево сохраняет свои свойства сортировки.
dict и set), операции удаления выполняются с помощью ключевого слова del или метода pop(), что обеспечивает удаление за время O(1). Если же вы пишете собственный класс BinarySearchTree в Python, вам придется запрограммировать алгоритм поиска узла-заместителя с помощью объектных ссылок точно так же, как это делается через указатели в языке Си.
Коротко: главное
- Вставка в дерево поиска всегда происходит на место пустого указателя (листа). Маршрут прокладывается так же, как и при поиске.
- Удаление узла без потомков или с одним потомком - тривиальная операция переброса указателя.
- Удаление узла с двумя потомками требует его замены на самый правый элемент левого поддерева (максимум среди меньших) или самый левый элемент правого поддерева (минимум среди больших).
Проверьте себя
Какой узел следует выбрать для замены, если мы удаляем узел, имеющий два потомка?