Удаление узла в двоичном дереве поиска
Прежде чем перейти к удалению узлов в двоичном дереве поиска, в этом разделе сначала объясняется, как найти минимальное и максимальное значения и как удалить минимальное и максимальное значения.
В качестве примера возьмём минимальное значение (максимальное значение рассматривается аналогично):
Логика кода для поиска минимального значения ключа: рекурсивно спускаемся по левому дочернему узлу:
// Возвращает узел с минимальным значением ключа в бинарном дереве поиска с корнем node
private Node minimum(Node node){
if( node.left == null )
return node;
return minimum(node.left);
}
...
Чтобы удалить минимальное значение ключа в бинарном дереве поиска, если у узла нет правого поддерева, удаляем его напрямую; если правое поддерево существует, как показано на рисунке:

Удаление узла 22: у него есть правый дочерний узел, поэтому просто заменяем узел 22 на узел 33 из правого поддерева.

Это удаление минимального значения выражается в коде так:
// Удаляет минимальный узел из бинарного дерева поиска с корнем node
// Возвращает корень нового бинарного дерева поиска после удаления узла node
private Node removeMin(Node node){
if( node.left == null ){
Node rightNode = node.right;
node.right = null;
count --;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
...
Теперь давайте обсудим удаление узла в двоичном дереве поиска, которое распадается на следующие три случая:
1、Удаление узла, имеющего только левого потомка, например узла 58 на рисунке ниже.

Удаляем элемент 58 и позволяем левому поддереву напрямую занять позицию 58; свойства всего двоичного дерева поиска остаются неизменными.

2、Удаление узла, имеющего только правого потомка, например узла 58 на рисунке ниже.

Удаляем элемент 58 и позволяем правому поддереву напрямую занять позицию 58; свойства всего двоичного дерева поиска остаются неизменными.

3、Удаление узла, имеющего как левого, так и правого потомка, например узла 58 на рисунке ниже.

(1) Найдите минимальное значение в правом поддереве — это узел 59.

(2) Узел 59 заменяет удаляемый узел 58.

Основываясь на приведённых выше правилах, пример основного кода для удаления узла со значением ключа key в двоичном дереве поиска с корнем в узле node выглядит так:
Загрузка пакета исходного кода:Скачать
код файла src/example/binary/BSTRemove.java:
import java.util.LinkedList;
/**
* Удаление узла двоичного дерева поиска
*/
public class BSTRemove<Key extends Comparable<Key>, Value> {
// Узлы в дереве — приватный класс; внешнему миру не нужно знать конкретную реализацию узлов двоичного дерева поиска
private class Node {
private Key key;
private Value value;
private Node left, right;
public Node(Key key, Value value) {
this.key = key;
this.value = value;
left = right = null;
}
public Node(Node node){
this.key = node.key;
this.value = node.value;
this.left = node.left;
this.right = node.right;
}
}
private Node root; // Корневой узел
private int count; // Количество узлов в дереве
// Конструктор, по умолчанию создаёт пустое двоичное дерево поиска
public BSTRemove() {
root = null;
count = 0;
}
// Вернуть количество узлов в бинарном дереве поиска
public int size() {
return count;
}
// Вернуть, является ли бинарное дерево поиска пустым
public boolean isEmpty() {
return count == 0;
}
// Вставить новую пару данных (key, value) в бинарное дерево поиска
public void insert(Key key, Value value){
root = insert(root, key, value);
}
// Проверить, существует ли key в бинарном дереве поиска
public boolean contain⟦⟧Key(Key key){
return contain(root, key);
}
// Найти в бинарном дереве поиска значение, соответствующее key. Если значение не существует, вернуть null
public Value search(⟦⟧Key key){
return search( root , key );
}
// Прямой обход бинарного дерева поиска
public void preOrder(){
preOrder(root);
}
// Симметричный обход бинарного дерева поиска
public void inOrder(){
inOrder(root);
}
// Обратный обход бинарного дерева поиска
public void postOrder(){
postOrder(root);
}
// Обход двоичного дерева поиска в порядке уровней
public void levelOrder(){
// Мы используем LinkedList в качестве очереди
LinkedList<Node> q = new LinkedList<Node>();
q.add(root);
while( !q.isEmpty() ){
Node node = q.remove();
System.out.println(node.key);
if( node.left != null )
q.add( node.left );
if( node.right != null )
q.add( node.right );
}
}
// Найти минимальный ключ в двоичном дереве поиска
public Key minimum(){
assert count != 0;
Node minNode = minimum( root );
return minNode.key;
}
// Найти максимальный ключ в двоичном дереве поиска
public Key maximum(){
assert count != 0;
Node maxNode = maximum(root);
return maxNode.key;
}
// Удалить узел с минимальным ключом из двоичного дерева поиска
public void removeMin(){
if( root != null )
root = removeMin( root );
}
// Удалить узел с максимальным ключом из двоичного дерева поиска
public void removeMax(){
if( root != null )
root = removeMax( root );
}
// Удалить узел со значением ключа key из двоичного дерева поиска
public void remove(Key key){
root = remove(root, key);
}
//********************
//* Вспомогательные функции для бинарного дерева поиска
//********************
// Вставка узла (key, value) в бинарное дерево поиска с корнем в node с использованием рекурсивного алгоритма
// Возвращает корень двоичного дерева поиска после вставки нового узла
private Node insert(Node node, Key key, Value value){
if( node == null ){
count ++;
return new Node(key, value);
}
if( key.compareTo(node.key) == 0 )
node.value = value;
else if( key.compareTo(node.key) < 0 )
node.left = insert( node.left , key, value);
else // key > node->key
node.right = insert( node.right, key, value);
return node;
}
// Проверяет, содержит ли двоичное дерево поиска с корнем в node узел со значением ключа key, используя рекурсивный алгоритм
private boolean contain(Node node, Key key){
if( node == null )
return false;
if( key.compareTo(node.key) == 0 )
return true;
else if( key.compareTo(node.key) < 0 )
return contain( node.left , key );
else // key > node->key
return contain( node.right , key );
}
// Найти значение, соответствующее key, в двоичном дереве поиска с корнем в node, рекурсивный алгоритм
// Вернуть NULL, если значение не существует
private Value search(Node node, Key key){
if( node == null )
return null;
if( key.compareTo(node.key) == 0 )
return node.value;
else if( key.compareTo(node.key) < 0 )
return search( node.left , key );
else // key > node->key
return search( node.right, key );
}
// Выполнить прямой обход двоичного дерева поиска с корнем в node, рекурсивный алгоритм
private void preOrder(Node node){
if( node != null ){
System.out.println(node.key);
preOrder(node.left);
preOrder(node.right);
}
}
// Выполнить симметричный обход двоичного дерева поиска с корнем в node, рекурсивный алгоритм
private void inOrder(Node node){
if( node != null ){
inOrder(node.left);
System.out.println(node.key);
inOrder(node.right);
}
}
// Выполнить обход в обратном порядке двоичного дерева поиска с корнем в node, рекурсивный алгоритм
private void postOrder(Node node){
if( node != null ){
postOrder(node.left);
postOrder(node.right);
System.out.println(node.key);
}
}
// Возвращает узел с минимальным значением ключа в бинарном дереве поиска с корнем node
private Node minimum(Node node){
if( node.left == null )
return node;
return minimum(node.left);
}
// Вернуть узел с максимальным значением ключа в двоичном дереве поиска с корнем node
private Node maximum(Node node){
if( node.right == null )
return node;
return maximum(node.right);
}
// Удаляет минимальный узел из бинарного дерева поиска с корнем node
// Возвращает корень нового бинарного дерева поиска после удаления узла node
private Node removeMin(Node node){
if( node.left == null ){
Node rightNode = node.right;
node.right = null;
count --;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
// Удалить максимальный узел из двоичного дерева поиска с корнем node
// Возвращает корень нового бинарного дерева поиска после удаления узла node
private Node removeMax(Node node){
if( node.right == null ){
Node leftNode = node.left;
node.left = null;
count --;
return leftNode;
}
node.right = removeMax(node.right);
return node;
}
// Удалить узел со значением ключа key из бинарного дерева поиска с корнем в node, рекурсивный алгоритм
// Возвращает корень нового бинарного дерева поиска после удаления узла node
Node remove(Node node, Key key){
if( node == null )
return null;
if( key.compareTo(node.key) < 0 ){
node.left = remove( node.left , key );
return node;
}
else if( key.compareTo(node.key) > 0 ){
node.right = remove( node.right, key );
return node;
}
else{ // key == node->key
// Случай, когда левое поддерево удаляемого узла пусто
if( node.left == null ){
Node rightNode = node.right;
node.right = null;
count --;
return rightNode;
}
// Случай, когда правое поддерево удаляемого узла пусто
if( node.right == null ){
Node leftNode = node.left;
node.left = null;
count--;
return leftNode;
}
// Случай, когда и левое, и правое поддеревья удаляемого узла не пусты
// Найти наименьший узел, который больше удаляемого узла, то есть минимальный узел в правом поддереве удаляемого узла
// Заменить удаляемый узел этим узлом
Node successor = new Node(minimum(node.right));
count ++;
successor.right = removeMin(node.right);
successor.left = node.left;
node.left = node.right = null;
count --;
return successor;
}
}
}