Общая стратегия удаления узла Z из бинарного дерева поиска T имеет три основных случая, но один из них немного сложен.
- Если у Z нет дочерних элементов, мы просто удаляем его, изменяя его родителя, заменяя Z на NIL в качестве дочернего элемента.
- Если у Z есть только один дочерний элемент, то мы повышаем уровень этого дочернего элемента, чтобы он занял позицию Z в дереве, модифицируя родителя Z, заменяя Z дочерним элементом Z.
- Если Z имеет двух потомков, то мы находим узел-преемник Z Y, который должен находиться в правом поддереве Z, и заставляем Y занимать позицию Z в дереве. Остальная часть исходного правого поддерева Z становится новым правым поддеревом Y, а левое поддерево Z становится новым левым поддеревом Y. Этот случай сложен, потому что, как мы увидим, имеет значение, является ли y правым потомком Z.
Процедура удаления данного узла Z из BST принимает в качестве аргументов указатель на узел и Z. Она организует свои случаи немного иначе, чем три описанных выше случая, рассматривая четыре случая:
- Если у Z нет левого дочернего элемента (рис. 1), то мы заменяем Z его правым дочерним элементом, который может быть или не быть NIL. Когда правым потомком Z является NIL, этот случай имеет дело с ситуацией, в которой у Z нет детей. Когда правый дочерний элемент Z не равен нулю, этот случай обрабатывает ситуацию, в которой Z имеет только одного дочернего элемента, который является правильным дочерним элементом.
2. Если у Z есть один дочерний элемент, который является левым дочерним элементом (рис. 2), то мы заменяем Z его левым дочерним элементом.
3. В противном случае у Z есть и левый, и правый потомок. Мы находим преемника Z Y, лежащего в правом поддереве Z. Мы хотим соединить Y из его текущего местоположения и заменить Z в дереве.
3.1: Если Y — правый потомок Z (рис. 3), то мы заменяем Z на Y, оставляя правого потомка Y в покое.
3.2: В противном случае Y лежит в правом поддереве Z, но не является правым потомком Z (рис. 4). В этом случае мы сначала заменяем Y его собственным правым дочерним элементом, а затем заменяем Z на Y.
Анализ:
- Время выполнения Tree-Delete на дереве высотой h равно O(h), так как мы идем по простому пути вниз по дереву.
- Плюс время работы, чтобы найти преемника в дереве, занимает O (h), так как мы либо идем по простому пути вверх по дереву, либо идем по простому пути вниз по дереву.
3. O(1) постоянное время для фактического удаления узла.
Код:
Структура узла:
struct node { int key; node *left; node *right; node *parent; node (int key) { this->key = key; left = right = nullptr; parent = nullptr; } };
Преемник дерева:
node* find_min_recursively(node *x) { if (x->left) { return find_min_recursively(x->left); } return x; } node* successor_of(node *x) { if (! x) return nullptr; if (x->right) { return find_min_recursively(x->right); } node *y = x->parent; while (y && x == y->right) { x = y; y = y->parent; } return y; }
Удалить:
void remove(node *root, int x) { node *current; current = root; while (current) { if (current->key == x) { break; } if (x < current->key) { current = current->left; } else if (x > current->key) { current = current->right; } } if (! current) { cout << "required node to delete not found...\n"; return; } //actual deletion //1. deletion with one node with empty left subtree if ( !current->left && current->right) { current->right->parent = current->parent; if (current->parent->left == current) { current->parent->left = current->right; } else if (current->parent->right == current) { current->parent->right = current->right; } } //1.1 deleting node with empty right subtree else if ( !current->right && current->left) { current->left->parent = current->parent; if (current == current->parent->left) { current->parent->left = current->left; } else if (current == current->parent->right) { current->parent->right = current->left; } } //2. deleting node which is leaf node else if ( !current->left && !current->right) { if (current == current->parent->left) { current->parent->left = nullptr; } else if (current == current->parent->right) { current->parent->right = nullptr; } } //3. deleting a node with non empty left and right subtree else { //find the successor of current node node *successor_node = this->successor_of(current); if (successor_node->parent != current) { successor_node->parent->left = successor_node->right; successor_node->right = current->right; successor_node->right->parent = successor_node; } successor_node->left = current->left; successor_node->left->parent = successor_node; successor_node->parent = current->parent; if (! current->parent) { root = successor_node; } else if (current == current->parent->left) { current->parent->left = successor_node; } else { current->parent->right = successor_node; } } delete current; }