Рубрики

Удалить ключи BST за пределами указанного диапазона

Учитывая Двоичное дерево поиска (BST) и диапазон [min, max], удалите все ключи, которые находятся за пределами указанного диапазона. Модифицированное дерево также должно быть BST. Например, рассмотрим следующий BST и диапазон [-10, 13].

Данное дерево должно быть изменено на следующее. Обратите внимание, что все ключи за пределами диапазона [-10, 13] удалены и изменено дерево BST.

Есть два возможных случая для каждого узла.
1) Ключ узла находится вне заданного диапазона. Этот случай имеет два подслоя.
……. а) Ключ узла меньше значения min.
……. б) Ключ узла больше максимального значения.
2) Ключ узла находится в радиусе действия.

В случае 2 нам ничего не нужно делать. В случае 1 нам нужно удалить узел и изменить корень поддерева, укорененного в этом узле.
Идея состоит в том, чтобы исправить дерево в стиле Postorder. Когда мы посещаем узел, мы проверяем, что его левые и правые поддеревья уже зафиксированы. В случае 1.a) мы просто удаляем корень и возвращаем правое поддерево как новый корень. В случае 1.b) мы удаляем корень и возвращаем левое поддерево как новый корень.

Ниже приводится реализация вышеуказанного подхода.

C ++

// Программа на C ++ для удаления ключей BST за пределами заданного диапазона
#include<stdio.h>
#include <iostream>

  

using namespace std;

  
// BST узел имеет ключ, а также левый и правый указатели

struct node

{

    int key;

    struct node *left;

    struct node *right;

};

  
// Удаляет все узлы, имеющие значение вне заданного диапазона и возвращает корень
// модифицированного дерева

node* removeOutsideRange(node *root, int min, int max)

{

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

   if (root == NULL)

      return NULL;

  

   // Сначала исправляем левое и правое поддеревья корня

   root->left =  removeOutsideRange(root->left, min, max);

   root->right =  removeOutsideRange(root->right, min, max);

  

   // Теперь исправим рут. Есть 2 возможных случая для toot

   // 1.a) Ключ Root меньше минимального значения (root не находится в диапазоне)

   if (root->key < min)

   {

       node *rChild = root->right;

       delete root;

       return rChild;

   }

   // 1.b) Ключ корня больше максимального значения (корень не находится в диапазоне)

   if (root->key > max)

   {

       node *lChild = root->left;

       delete root;

       return lChild;

   }

   // 2. Корень находится в диапазоне

   return root;

}

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

node* newNode(int num)

{

    node* temp = new node;

    temp->key = num;

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

    return temp;

}

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

node* insert(node* root, int key)

{

    if (root == NULL)

       return newNode(key);

    if (root->key > key)

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

    else

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

    return root;

}

  
// Утилита для обхода двоичного дерева после преобразования

void inorderTraversal(node* root)

{

    if (root)

    {

        inorderTraversal( root->left );

        cout << root->key << " ";

        inorderTraversal( root->right );

    }

}

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

int main()

{

    node* root = NULL;

    root = insert(root, 6);

    root = insert(root, -13);

    root = insert(root, 14);

    root = insert(root, -8);

    root = insert(root, 15);

    root = insert(root, 13);

    root = insert(root, 7);

  

    cout << "Inorder traversal of the given tree is: ";

    inorderTraversal(root);

  

    root = removeOutsideRange(root, -10, 13);

  

    cout << "\nInorder traversal of the modified tree is: ";

    inorderTraversal(root);

  

    return 0;

}

Джава

// Java-программа для удаления BST
// ключи вне заданного диапазона

import java.math.BigDecimal;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

import java.util.Scanner;

  

class Node

{

    int key;

    Node left;

    Node right;

}

  

class GFG

{

    // Удаляет все узлы, имеющие значение

    // вне заданного диапазона и

    // возвращает корень модифицированного дерева

    private static Node removeOutsideRange(Node root, 

                                           int min, int max) 

    {

        // БАЗОВЫЙ ВАРИАНТ

        if(root == null)

        {

            return null;

        }

          

        // ПЕРВЫЙ ФИКС ЛЕВОГО И

        // ПРАВАЯ ДЕРЕВА КОРНИ

        root.left = removeOutsideRange(root.left, 

                                       min, max);

        root.right = removeOutsideRange(root.right, 

                                        min, max);

          

        // Теперь исправим корень. ЕСТЬ

        // ДВА ВОЗМОЖНЫХ СЛУЧАЯ ДЛЯ КОРНИ

        // 1. a) Ключ Root меньше чем

        // минимальное значение (корень не в диапазоне)

        if(root.key < min) 

        {

            Node rchild = root.right;

            root = null;

            return rchild;

        }

          

        // 1. б) Ключ root больше чем

        // максимальное значение (Root не находится в диапазоне)

        if(root.key > max) 

        {

            Node lchild = root.left;

            root = null;

            return lchild;

        }

          

        // 2. Корень в диапазоне

        return root;

    }

  

    public static Node newNode(int num) 

    {

        Node temp = new Node();

        temp.key = num;

        temp.left = null;

        temp.right = null;

        return temp;

    }

  

    public static Node insert(Node root,

                              int key) 

    {

        if(root == null

        {

            return newNode(key);

        }

        if(root.key > key) 

        {

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

        }

        else 

        {

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

        }

        return root;

    }

      

    private static void inorderTraversal(Node root)

    {

        if(root != null

        {

            inorderTraversal(root.left);

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

            inorderTraversal(root.right);

        }

    }

      

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

    public static void main(String[] args)

    {

        Node root = null;

        root = insert(root, 6);

        root = insert(root, -13);

        root = insert(root, 14);

        root = insert(root, -8);

        root = insert(root, 15);

        root = insert(root, 13);

        root = insert(root, 7);

          

        System.out.print("Inorder Traversal of "

                           "the given tree is: ");

        inorderTraversal(root);

          

        root = removeOutsideRange(root, -10, 13);

          

        System.out.print("\nInorder traversal of "

                           "the modified tree: ");

        inorderTraversal(root);

    }

}

  
// Этот код добавлен
// Дивья

python3

# Python3 программа для удаления ключей BST
# вне заданного диапазона

  
# Узел BST имеет ключ, а также левый и правый
# указатели. Полезная функция для создания
# новый узел BST с ключом с указанным номером

class newNode: 

  

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

    def __init__(self, data): 

        self.key = data 

        self.left = None

        self.right = None

          
# Удаляет все узлы, имеющие значение вне
# данный диапазон и возвращает корень
# измененного дерева

def removeOutsideRange(root, Min, Max):

      

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

    if root == None:

        return None

      

    # Сначала исправьте левую и правую

    # поддеревья корня

    root.left = removeOutsideRange(root.left,

                                   Min, Max

    root.right = removeOutsideRange(root.right,

                                    Min, Max

      

    # Теперь исправим рут. Есть 2

    # возможные случаи для toot

    # 1.a) Ключ Root меньше чем

    # минимальное значение (корень не находится в диапазоне)

    if root.key < Min:

        rChild = root.right 

        return rChild

          

    # 1.b) Ключ root больше максимального

    # значение (корень не в диапазоне)

    if root.key > Max:

        lChild = root.left 

        return lChild

          

    # 2. Корень в радиусе

    return root

  

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

def insert(root, key):

    if root == None:

        return newNode(key) 

    if root.key > key:

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

    else:

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

    return root

  
# Утилита для обхода двоичного файла
# дерево после преобразования

def inorderTraversal(root):

    if root:

        inorderTraversal( root.left) 

        print(root.key, end = " ")

        inorderTraversal( root.right)

  
Код водителя

if __name__ == '__main__':

    root = None

    root = insert(root, 6)

    root = insert(root, -13

    root = insert(root, 14

    root = insert(root, -8

    root = insert(root, 15

    root = insert(root, 13

    root = insert(root, 7

  

    print("Inorder traversal of the given tree is:"

                                          end = " "

    inorderTraversal(root) 

  

    root = removeOutsideRange(root, -10, 13)

    print()

    print("Inorder traversal of the modified tree is:",

                                             end = " "

    inorderTraversal(root) 

  
# Этот код предоставлен PranchalK

C #

// AC # программа для удаления BST
// ключи вне заданного диапазона

using System;

  

public class Node 

    public int key; 

    public Node left; 

    public Node right; 

  

public class GFG 

    // Удаляет все узлы, имеющие значение

    // вне заданного диапазона и

    // возвращает корень модифицированного дерева

    private static Node removeOutsideRange(Node root, 

                                        int min, int max) 

    

        // БАЗОВЫЙ ВАРИАНТ

        if(root == null

        

            return null

        

          

        // ПЕРВЫЙ ФИКС ЛЕВОГО И

        // ПРАВАЯ ДЕРЕВА КОРНИ

        root.left = removeOutsideRange(root.left, 

                                    min, max); 

        root.right = removeOutsideRange(root.right, 

                                        min, max); 

          

        // Теперь исправим корень. ЕСТЬ

        // ДВА ВОЗМОЖНЫХ СЛУЧАЯ ДЛЯ КОРНИ

        // 1. a) Ключ Root меньше чем

        // минимальное значение (корень не в диапазоне)

        if(root.key < min) 

        

            Node rchild = root.right; 

            root = null

            return rchild; 

        

          

        // 1. б) Ключ root больше чем

        // максимальное значение (Root не находится в диапазоне)

        if(root.key > max) 

        

            Node lchild = root.left; 

            root = null

            return lchild; 

        

          

        // 2. Корень в диапазоне

        return root; 

    

  

    public static Node newNode(int num) 

    

        Node temp = new Node(); 

        temp.key = num; 

        temp.left = null

        temp.right = null

        return temp; 

    

  

    public static Node insert(Node root, 

                            int key) 

    

        if(root == null

        

            return newNode(key); 

        

        if(root.key > key) 

        

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

        

        else

        

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

        

        return root; 

    

      

    private static void inorderTraversal(Node root) 

    

        if(root != null

        

            inorderTraversal(root.left); 

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

            inorderTraversal(root.right); 

        

    

      

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

    public static void Main(String[] args) 

    

        Node root = null

        root = insert(root, 6); 

        root = insert(root, -13); 

        root = insert(root, 14); 

        root = insert(root, -8); 

        root = insert(root, 15); 

        root = insert(root, 13); 

        root = insert(root, 7); 

          

        Console.Write("Inorder Traversal of "

                        "the given tree is: "); 

        inorderTraversal(root); 

          

        root = removeOutsideRange(root, -10, 13); 

          

        Console.Write("\nInorder traversal of "

                        "the modified tree: "); 

        inorderTraversal(root); 

    

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


Выход:

Inorder traversal of the given tree is: -13 -8 6 7 13 14 15
Inorder traversal of the modified tree is: -8 6 7 13

Сложность времени: O (n), где n — количество узлов в данном BST.

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

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

Удалить ключи BST за пределами указанного диапазона

0.00 (0%) 0 votes