Функція Delete використовується для видалення вказаного вузла з бінарного дерева пошуку. Однак ми повинні видалити вузол із бінарного дерева пошуку таким чином, щоб властивість бінарного дерева пошуку не порушувалася. Існує три ситуації видалення вузла з бінарного дерева пошуку.
Вузол, який потрібно видалити, є листовим вузлом
Це найпростіший випадок, у цьому випадку замініть кінцевий вузол на NULL і просто звільніть виділений простір.
На наступному зображенні ми видаляємо вузол 85, оскільки вузол є кінцевим вузлом, тому вузол буде замінено на NULL, а виділений простір буде звільнено.
Вузол, який потрібно видалити, має лише одного дочірнього вузла.
У цьому випадку замініть вузол його дочірнім вузлом і видаліть дочірній вузол, який тепер містить значення, яке потрібно видалити. Просто замініть його на NULL і звільніть виділений простір.
На наступному зображенні вузол 12 потрібно видалити. Має лише одну дитину. Вузол буде замінено його дочірнім вузлом, а замінений вузол 12 (який зараз є кінцевим вузлом) буде просто видалено.
Вузол, який потрібно видалити, має двох дітей.
Це трохи складний випадок порівняно з двома іншими випадками. Однак вузол, який потрібно видалити, рекурсивно замінюється його наступником або попередником у порядку, доки значення вузла (що потрібно видалити) не буде розміщено на аркуші дерева. Після процедури замініть вузол на NULL і звільніть виділений простір.
На наступному зображенні потрібно видалити вузол 50, який є кореневим вузлом дерева. Нижче наведено порядковий обхід дерева.
6, 25, 30, 50, 52, 60, 70, 75.
замініть 50 наступним за порядком 52. Тепер 50 буде переміщено на листок дерева, який буде просто видалено.
Алгоритм
Видалити (ДЕРЕВО, ЕЛЕМЕНТ)
Напишіть «елемент не знайдено в дереві» ELSE IF ITEM DATA
Видалити (ДЕРЕВО->ЛІВО, ЕЛЕМЕНТ)
ІНШЕ, ЯКЩО ЕЛЕМЕНТ > ДЕРЕВО -> ДАНІ
Видалити (ДЕРЕВО -> ПРАВОРУЧ, ЕЛЕМЕНТ)
ІНАКШЕ, ЯКЩО ДЕРЕВО -> ЛІВОРУЧ І ДЕРЕВО -> ПРАВОРУЧ
SET TEMP = findLargestNode(TREE -> LEFT)
SET TREE -> DATA = TEMP -> DATA
Видалити (ДЕРЕВО -> ВЛІВО, TEMP -> ДАНІ)
ІНШЕ
ВСТАНОВИТИ ТЕМПЕРАТУРУ = ДЕРЕВО
ЯКЩО ДЕРЕВО -> ЛІВО = НУЛЬ І ДЕРЕВО -> ПРАВО = НУЛЬ
SET TREE = NULL
ІНШЕ, ЯКЩО ДЕРЕВО -> ВЛІВО != NULL
ВСТАНОВИТИ ДЕРЕВО = ДЕРЕВО -> ВЛІВО
ІНШЕ
ВСТАНОВИТИ ДЕРЕВО = ДЕРЕВО -> ПРАВО
[КІНЕЦЬ ЯКЩО]
ВІЛЬНА ТЕМП
[КІНЕЦЬ ЯКЩО]
функція:
void deletion(Node*& root, int item) { Node* parent = NULL; Node* cur = root; search(cur, item, parent); if (cur == NULL) return; if (cur->left == NULL && cur->right == NULL) { if (cur != root) { if (parent->left == cur) parent->left = NULL; else parent->right = NULL; } else root = NULL; free(cur); } else if (cur->left && cur->right) { Node* succ = findMinimum(cur- >right); int val = succ->data; deletion(root, succ->data); cur->data = val; } else { Node* child = (cur->left)? Cur- >left: cur->right; if (cur != root) { if (cur == parent->left) parent->left = child; else parent->right = child; } else root = child; free(cur); } } Node* findMinimum(Node* cur) { while(cur->left != NULL) { cur = cur->left; } return cur; }