Удаление узла в двоичном дереве поиска

Прежде чем перейти к удалению узлов в двоичном дереве поиска, в этом разделе сначала объясняется, как найти минимальное и максимальное значения и как удалить минимальное и максимальное значения.

В качестве примера возьмём минимальное значение (максимальное значение рассматривается аналогично):

Логика кода для поиска минимального значения ключа: рекурсивно спускаемся по левому дочернему узлу:

...
// Возвращает узел с минимальным значением ключа в бинарном дереве поиска с корнем 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:

package example.binary;

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;
        }
    }
}
Другие расширения