Рубрики

Двоичное дерево поиска | Набор 2 (Удалить)

Мы обсудили поиск и вставку BST . В этом посте операция удаления обсуждается. Когда мы удаляем узел, возникают три возможности.
1) Узел, который нужно удалить, это лист: просто удалите из дерева.

              50                            50
           /     \         delete(20)      /   \
          30      70       --------->    30     70 
         /  \    /  \                     \    /  \ 
       20   40  60   80                   40  60   80

2) У удаляемого узла есть только один дочерний: скопируйте дочерний узел и удалите дочерний.

              50                            50
           /     \         delete(30)      /   \
          30      70       --------->    40     70 
            \    /  \                          /  \ 
            40  60   80                       60   80

3) У удаляемого узла есть два потомка : Найти преемника наследника узла. Скопируйте содержимое преемника Inorder в узел и удалите преемника Inorder. Обратите внимание, что inorder предшественник также может быть использован.

              50                            60
           /     \         delete(50)      /   \
          40      70       --------->    40    70 
                 /  \                            \ 
                60   80                           80

Важно отметить, что наследник-преемник необходим только тогда, когда правильный ребенок не пуст. В этом конкретном случае преемник преемника может быть получен путем нахождения минимального значения в правом дочернем узле.

C / C ++

// C программа для демонстрации операции удаления в бинарном дереве поиска
#include<stdio.h>
#include<stdlib.h>

  

struct node

{

    int key;

    struct node *left, *right;

};

  
// Вспомогательная функция для создания нового узла BST

struct node *newNode(int item)

{

    struct node *temp =  (struct node *)malloc(sizeof(struct node));

    temp->key = item;

    temp->left = temp->right = NULL;

    return temp;

}

  
// Утилита для обхода порядка следования BST

void inorder(struct node *root)

{

    if (root != NULL)

    {

        inorder(root->left);

        printf("%d ", root->key);

        inorder(root->right);

    }

}

  
/ * Утилита для вставки нового узла с заданным ключом в BST * /

struct node* insert(struct node* node, int key)

{

    / * Если дерево пустое, вернуть новый узел * /

    if (node == NULL) return newNode(key);

  

    / * В противном случае вернемся вниз по дереву * /

    if (key < node->key)

        node->left  = insert(node->left, key);

    else

        node->right = insert(node->right, key);

  

    / * вернуть (неизмененный) указатель узла * /

    return node;

}

  
/ * Если дано непустое двоичное дерево поиска, вернуть узел с минимальным

   значение ключа найдено в этом дереве. Обратите внимание, что все дерево не

   нужно искать. * /

struct node * minValueNode(struct node* node)

{

    struct node* current = node;

  

    / * зациклиться, чтобы найти самый левый лист * /

    while (current && current->left != NULL)

        current = current->left;

  

    return current;

}

  
/ * Учитывая бинарное дерево поиска и ключ, эта функция удаляет ключ

   и возвращает новый корень * /

struct node* deleteNode(struct node* root, int key)

{

    // базовый вариант

    if (root == NULL) return root;

  

    // Если удаляемый ключ меньше ключа root,

    // тогда он лежит в левом поддереве

    if (key < root->key)

        root->left = deleteNode(root->left, key);

  

    // Если удаляемый ключ больше ключа root,

    // тогда оно лежит в правом поддереве

    else if (key > root->key)

        root->right = deleteNode(root->right, key);

  

    // если ключ совпадает с ключом root, то это узел

    // быть удаленным

    else

    {

        // узел только с одним дочерним элементом или без него

        if (root->left == NULL)

        {

            struct node *temp = root->right;

            free(root);

            return temp;

        }

        else if (root->right == NULL)

        {

            struct node *temp = root->left;

            free(root);

            return temp;

        }

  

        // узел с двумя дочерними элементами: Получить преемника по порядку (наименьший

        // в правом поддереве)

        struct node* temp = minValueNode(root->right);

  

        // Копируем содержимое преемника inorder в этот узел

        root->key = temp->key;

  

        // Удалить наследник преемника

        root->right = deleteNode(root->right, temp->key);

    }

    return root;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    / * Давайте создадим следующий BST

              50

           / /

          30 70

         / / / /

       20 40 60 80 *

    struct node *root = NULL;

    root = insert(root, 50);

    root = insert(root, 30);

    root = insert(root, 20);

    root = insert(root, 40);

    root = insert(root, 70);

    root = insert(root, 60);

    root = insert(root, 80);

  

    printf("Inorder traversal of the given tree \n");

    inorder(root);

  

    printf("\nDelete 20\n");

    root = deleteNode(root, 20);

    printf("Inorder traversal of the modified tree \n");

    inorder(root);

  

    printf("\nDelete 30\n");

    root = deleteNode(root, 30);

    printf("Inorder traversal of the modified tree \n");

    inorder(root);

  

    printf("\nDelete 50\n");

    root = deleteNode(root, 50);

    printf("Inorder traversal of the modified tree \n");

    inorder(root);

  

    return 0;

}

Джава

// Java-программа для демонстрации операции удаления в бинарном дереве поиска

class BinarySearchTree

{

    / * Класс, содержащий левого и правого потомка текущего узла и значения ключа * /

    class Node

    {

        int key;

        Node left, right;

  

        public Node(int item)

        {

            key = item;

            left = right = null;

        }

    }

  

    // Корень BST

    Node root;

  

    // Конструктор

    BinarySearchTree()

    {

        root = null;

    }

  

    // Этот метод в основном вызывает deleteRec ()

    void deleteKey(int key)

    {

        root = deleteRec(root, key);

    }

  

    / * Рекурсивная функция для вставки нового ключа в BST * /

    Node deleteRec(Node root, int key)

    {

        / * Базовый случай: если дерево пусто * /

        if (root == nullreturn root;

  

        / * В противном случае вернемся вниз по дереву * /

        if (key < root.key)

            root.left = deleteRec(root.left, key);

        else if (key > root.key)

            root.right = deleteRec(root.right, key);

  

        // если ключ совпадает с ключом root, то это узел

        // быть удаленным

        else

        {

            // узел только с одним дочерним элементом или без него

            if (root.left == null)

                return root.right;

            else if (root.right == null)

                return root.left;

  

            // узел с двумя дочерними элементами: Получить преемника по порядку (наименьший

            // в правом поддереве)

            root.key = minValue(root.right);

  

            // Удалить наследник преемника

            root.right = deleteRec(root.right, root.key);

        }

  

        return root;

    }

  

    int minValue(Node root)

    {

        int minv = root.key;

        while (root.left != null)

        {

            minv = root.left.key;

            root = root.left;

        }

        return minv;

    }

  

    // Этот метод в основном вызывает insertRec ()

    void insert(int key)

    {

        root = insertRec(root, key);

    }

  

    / * Рекурсивная функция для вставки нового ключа в BST * /

    Node insertRec(Node root, int key)

    {

  

        / * Если дерево пустое, вернуть новый узел * /

        if (root == null)

        {

            root = new Node(key);

            return root;

        }

  

        / * В противном случае вернемся вниз по дереву * /

        if (key < root.key)

            root.left = insertRec(root.left, key);

        else if (key > root.key)

            root.right = insertRec(root.right, key);

  

        / * вернуть (неизмененный) указатель узла * /

        return root;

    }

  

    // Этот метод в основном вызывает InorderRec ()

    void inorder()

    {

        inorderRec(root);

    }

  

    // Утилита для обхода порядка следования BST

    void inorderRec(Node root)

    {

        if (root != null)

        {

            inorderRec(root.left);

            System.out.print(root.key + " ");

            inorderRec(root.right);

        }

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String[] args)

    {

        BinarySearchTree tree = new BinarySearchTree();

  

        / * Давайте создадим следующий BST

              50

           / /

          30 70

         / / / /

        20 40 60 80 *

        tree.insert(50);

        tree.insert(30);

        tree.insert(20);

        tree.insert(40);

        tree.insert(70);

        tree.insert(60);

        tree.insert(80);

  

        System.out.println("Inorder traversal of the given tree");

        tree.inorder();

  

        System.out.println("\nDelete 20");

        tree.deleteKey(20);

        System.out.println("Inorder traversal of the modified tree");

        tree.inorder();

  

        System.out.println("\nDelete 30");

        tree.deleteKey(30);

        System.out.println("Inorder traversal of the modified tree");

        tree.inorder();

  

        System.out.println("\nDelete 50");

        tree.deleteKey(50);

        System.out.println("Inorder traversal of the modified tree");

        tree.inorder();

    }

}

питон

# Python программа для демонстрации операции удаления
# в бинарном дереве поиска

  
# Узел двоичного дерева

class Node:

  

    # Конструктор для создания нового узла

    def __init__(self, key):

        self.key = key 

        self.left = None

        self.right = None

  

  
# Полезная функция для выполнения обхода BST

def inorder(root):

    if root is not None:

        inorder(root.left)

        print root.key,

        inorder(root.right)

  

  
# Полезная функция для вставки нового узла с заданным ключом в BST

def insert( node, key):

  

    # Если дерево пусто, вернуть новый узел

    if node is None:

        return Node(key)

  

    # В противном случае повторить вниз по дереву

    if key < node.key:

        node.left = insert(node.left, key)

    else:

        node.right = insert(node.right, key)

  

    # вернуть (неизмененный) указатель узла

    return node

  
# Если дано непустое двоичное дерево поиска, вернуть узел
# с минимальным значением ключа, найденным в этом дереве. Обратите внимание, что
# все дерево не нужно искать

def minValueNode( node):

    current = node

  

    # цикл, чтобы найти самый левый лист

    while(current.left is not None):

        current = current.left 

  

    return current 

  
# Учитывая бинарное дерево поиска и ключ, эта функция
# удалить ключ и вернуть новый корень

def deleteNode(root, key):

  

    # Базовый вариант

    if root is None:

        return root 

  

    # Если удаляемый ключ меньше корневого

    # ключ, то он лежит в левом поддереве

    if key < root.key:

        root.left = deleteNode(root.left, key)

  

    # Если удаляемый ключ больше ключа root

    # тогда оно лежит в правильном поддереве

    elif(key > root.key):

        root.right = deleteNode(root.right, key)

  

    # Если ключ совпадает с ключом root, то это узел

    # быть удаленным

    else:

          

        # Узел только с одним ребенком или без ребенка

        if root.left is None :

            temp = root.right 

            root = None 

            return temp 

              

        elif root.right is None :

            temp = root.left 

            root = None

            return temp

  

        # Узел с двумя детьми: получить преемника

        # (самое маленькое в правом поддереве)

        temp = minValueNode(root.right)

  

        # Скопируйте содержимое преемника inorder в этот узел

        root.key = temp.key

  

        # Удалить наследник преемника

        root.right = deleteNode(root.right , temp.key)

  

  

    return root 

  
# Драйверная программа для проверки вышеуказанных функций
"" "Давайте создадим следующий BST

              50

           / /

          30 70

         / / / /

       20 40 60 80 "" "

  

root = None

root = insert(root, 50)

root = insert(root, 30)

root = insert(root, 20)

root = insert(root, 40)

root = insert(root, 70)

root = insert(root, 60)

root = insert(root, 80)

  

print "Inorder traversal of the given tree"

inorder(root)

  

print "\nDelete 20"

root = deleteNode(root, 20)

print "Inorder traversal of the modified tree"

inorder(root)

  

print "\nDelete 30"

root = deleteNode(root, 30)

print "Inorder traversal of the modified tree"

inorder(root)

  

print "\nDelete 50"

root = deleteNode(root, 50)

print "Inorder traversal of the modified tree"

inorder(root)

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// C # программа для демонстрации удаления
// операция в двоичном дереве поиска

using System;

  

public class BinarySearchTree 

    / * Класс, содержащий левый и правый

    дочерний элемент текущего узла и значение ключа * /

    class Node 

    

        public int key; 

        public Node left, right; 

  

        public Node(int item) 

        

            key = item; 

            left = right = null

        

    

  

    // Корень BST

    Node root; 

  

    // Конструктор

    BinarySearchTree() 

    

        root = null

    

  

    // Этот метод в основном вызывает deleteRec ()

    void deleteKey(int key) 

    

        root = deleteRec(root, key); 

    

  

    / * Рекурсивная функция для вставки нового ключа в BST * /

    Node deleteRec(Node root, int key) 

    

        / * Базовый случай: если дерево пусто * /

        if (root == null) return root; 

  

        / * В противном случае вернемся вниз по дереву * /

        if (key < root.key) 

            root.left = deleteRec(root.left, key); 

        else if (key > root.key) 

            root.right = deleteRec(root.right, key); 

  

        // если ключ совпадает с ключом root, то это узел

        // быть удаленным

        else

        

            // узел только с одним дочерним элементом или без него

            if (root.left == null

                return root.right; 

            else if (root.right == null

                return root.left; 

  

            // узел с двумя детьми: Получить

            // наследник преемника (наименьший

            // в правом поддереве)

            root.key = minValue(root.right); 

  

            // Удалить наследник преемника

            root.right = deleteRec(root.right, root.key); 

        

        return root; 

    

  

    int minValue(Node root) 

    

        int minv = root.key; 

        while (root.left != null

        

            minv = root.left.key; 

            root = root.left; 

        

        return minv; 

    

  

    // Этот метод в основном вызывает insertRec ()

    void insert(int key) 

    

        root = insertRec(root, key); 

    

  

    / * Рекурсивная функция для вставки нового ключа в BST * /

    Node insertRec(Node root, int key) 

    

  

        / * Если дерево пустое, вернуть новый узел * /

        if (root == null

        

            root = new Node(key); 

            return root; 

        

  

        / * В противном случае вернемся вниз по дереву * /

        if (key < root.key) 

            root.left = insertRec(root.left, key); 

        else if (key > root.key) 

            root.right = insertRec(root.right, key); 

  

        / * вернуть (неизмененный) указатель узла * /

        return root; 

    

  

    // Этот метод в основном вызывает InorderRec ()

    void inorder() 

    

        inorderRec(root); 

    

  

    // Утилита для обхода порядка следования BST

    void inorderRec(Node root) 

    

        if (root != null

        

            inorderRec(root.left); 

            Console.Write(root.key + " "); 

            inorderRec(root.right); 

        

    

  

    // Код драйвера

    public static void Main(String[] args) 

    

        BinarySearchTree tree = new BinarySearchTree(); 

  

        / * Давайте создадим следующий BST

            50

        / /

        30 70

        / / / /

        20 40 60 80 *

        tree.insert(50); 

        tree.insert(30); 

        tree.insert(20); 

        tree.insert(40); 

        tree.insert(70); 

        tree.insert(60); 

        tree.insert(80); 

  

        Console.WriteLine("Inorder traversal of the given tree"); 

        tree.inorder(); 

  

        Console.WriteLine("\nDelete 20"); 

        tree.deleteKey(20); 

        Console.WriteLine("Inorder traversal of the modified tree"); 

        tree.inorder(); 

  

        Console.WriteLine("\nDelete 30"); 

        tree.deleteKey(30); 

        Console.WriteLine("Inorder traversal of the modified tree"); 

        tree.inorder(); 

  

        Console.WriteLine("\nDelete 50"); 

        tree.deleteKey(50); 

        Console.WriteLine("Inorder traversal of the modified tree"); 

        tree.inorder(); 

    

  
// Этот код был добавлен
// by PrinciRaj1992


Выход:

Inorder traversal of the given tree
20 30 40 50 60 70 80
Delete 20
Inorder traversal of the modified tree
30 40 50 60 70 80
Delete 30
Inorder traversal of the modified tree
40 50 60 70 80
Delete 50
Inorder traversal of the modified tree
40 60 70 80

Иллюстрация:

Сложность по времени: временная сложность операции удаления в наихудшем случае — O (h), где h — высота дерева двоичного поиска. В худшем случае нам, возможно, придется пройти от корня до самого глубокого листового узла. Высота перекошенного дерева может стать n, а временная сложность операции удаления может стать O (n).

Оптимизация для вышеприведенного кода для случая с двумя детьми:
В приведенном выше рекурсивном коде мы рекурсивно вызываем delete () для преемника. Мы можем избежать рекурсивного вызова, отслеживая родительский узел преемника, так что мы можем просто удалить преемника, сделав child of parent равным NULL. Мы знаем, что преемником всегда будет листовой узел.

// C ++ программа для реализации оптимизированного удаления в BST.
#include <bits/stdc++.h>

using namespace std;

  

struct Node {

    int key;

    struct Node *left, *right;

};

  
// Вспомогательная функция для создания нового узла BST

Node* newNode(int item)

{

    Node* temp = new Node;

    temp->key = item;

    temp->left = temp->right = NULL;

    return temp;

}

  
// Утилита для обхода порядка следования BST

void inorder(Node* root)

{

    if (root != NULL) {

        inorder(root->left);

        printf("%d ", root->key);

        inorder(root->right);

    }

}

  
/ * Утилита для вставки нового узла с заданным ключом в BST * /

Node* insert(Node* node, int key)

{

    / * Если дерево пустое, вернуть новый узел * /

    if (node == NULL)

        return newNode(key);

  

    / * В противном случае вернемся вниз по дереву * /

    if (key < node->key)

        node->left = insert(node->left, key);

    else

        node->right = insert(node->right, key);

  

    / * вернуть (неизмененный) указатель узла * /

    return node;

}

  
/ * Учитывая бинарное дерево поиска и ключ, эта функция удаляет ключ

   и возвращает новый корень * /

Node* deleteNode(Node* root, int k)

{

    // Базовый вариант

    if (root == NULL)

        return root;

  

    // Рекурсивные вызовы для предков

    // удаляемый узел

    if (root->key > k) {

        root->left = deleteNode(root->left, k);

        return root;

    }

    else if (root->key < k) {

        root->right = deleteNode(root->right, k);

        return root;

    }

  

    // Мы достигаем здесь, когда корень является узлом

    // быть удаленным.

  

    // Если один из детей пуст

    if (root->left == NULL) {

        Node* temp = root->right;

        delete root;

        return temp;

    }

    else if (root->right == NULL) {

        Node* temp = root->left;

        delete root;

        return temp;

    }

  

    // Если оба ребенка существуют

    else {

  

        Node* succParent = root->right;

          

        // Найти преемника

        Node *succ = root->right;

        while (succ->left != NULL) {

            succParent = succ;

            succ = succ->left;

        }

  

        // Удалить преемника. С преемником

        // всегда остается дочерним от своего родителя

        // мы можем смело сделать право преемника

        // правый ребенок слева от своего родителя.

        succParent->left = succ->right;

  

        // Копируем данные преемника в корень

        root->key = succ->key;

  

        // Удалить наследник и вернуть root

        delete succ;         

        return root;

    }

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    / * Давайте создадим следующий BST

              50

           / /

          30 70

         / / / /

       20 40 60 80 *

    Node* root = NULL;

    root = insert(root, 50);

    root = insert(root, 30);

    root = insert(root, 20);

    root = insert(root, 40);

    root = insert(root, 70);

    root = insert(root, 60);

    root = insert(root, 80);

  

    printf("Inorder traversal of the given tree \n");

    inorder(root);

  

    printf("\nDelete 20\n");

    root = deleteNode(root, 20);

    printf("Inorder traversal of the modified tree \n");

    inorder(root);

  

    printf("\nDelete 30\n");

    root = deleteNode(root, 30);

    printf("Inorder traversal of the modified tree \n");

    inorder(root);

  

    printf("\nDelete 50\n");

    root = deleteNode(root, 50);

    printf("Inorder traversal of the modified tree \n");

    inorder(root);

  

    return 0;

}

Выход:

Inorder traversal of the given tree 
20 30 40 50 60 70 80 
Delete 20
Inorder traversal of the modified tree 
30 40 50 60 70 80 
Delete 30
Inorder traversal of the modified tree 
40 50 60 70 80 
Delete 50
Inorder traversal of the modified tree 
40 60 70 80

Спасибо wolffgang010 за предложенную выше оптимизацию.

Ссылки по теме:

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Двоичное дерево поиска | Набор 2 (Удалить)

0.00 (0%) 0 votes