Рубрики

Найти пару с заданной суммой в сбалансированном BST

Учитывая сбалансированное дерево двоичного поиска и целевую сумму, напишите функцию, которая возвращает истину, если есть пара с суммой, равной целевой сумме, в противном случае возвращает ложь. Ожидаемая сложность по времени составляет O (n), и может использоваться только O (Logn) дополнительное пространство. Любые изменения в бинарном дереве поиска не допускаются. Обратите внимание, что высота сбалансированного BST всегда O (Logn).

Эта проблема в основном является продолжением предыдущего поста . Здесь нам не разрешено изменять BST.

Решение грубой силы состоит в том, чтобы рассмотреть каждую пару в BST и проверить, равна ли сумма X. Временная сложность этого решения будет O (n ^ 2).

Лучшим решением является создание вспомогательного массива и сохранение обхода Inorder для BST в массиве. Массив будет отсортирован, так как обход Instder BST всегда производит отсортированные данные. Получив обход Inorder, мы можем выполнить сопряжение за O (n) раз (подробности см. В этом разделе). Это решение работает за O (n) времени, но требует O (n) вспомогательного пространства.

Джава

// Java-код для поиска пары с заданной суммой
// в сбалансированном BST

import java.util.ArrayList;

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

class Node {

  

    int data;

    Node left, right;

  

    Node(int d)

    {

        data = d;

        left = right = null;

    }

}

  

class BinarySearchTree {

  

    // Корень BST

    Node root;

  

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

    BinarySearchTree()

    {

        root = null;

    }

  

    // По обходу дерева

    void inorder()

    {

        inorderUtil(this.root);

    }

  

    // Сервисная функция для обхода дерева по порядку

    void inorderUtil(Node node)

    {

        if (node == null)

            return;

  

        inorderUtil(node.left);

        System.out.print(node.data + " ");

        inorderUtil(node.right);

    }

  

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

    void insert(int key)

    {

        root = insertRec(root, key);

    }

  

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

    Node insertRec(Node root, int data)

    {

  

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

        if (root == null) {

            root = new Node(data);

            return root;

        }

  

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

        if (data < root.data)

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

        else if (data > root.data)

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

  

        return root;

    }

  

    // Метод, который добавляет значения данного BST в ArrayList

    // и, следовательно, возвращает ArrayList

    ArrayList<Integer> treeToList(Node node, ArrayList<Integer>

                                                 list)

    {

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

        if (node == null)

            return list;

  

        treeToList(node.left, list);

        list.add(node.data);

        treeToList(node.right, list);

  

        return list;

    }

  

    // метод, который проверяет наличие пары

    boolean isPairPresent(Node node, int target)

    {

        // Этот список a1 передается в качестве аргумента

        // в методе treeToList

        // который позже заполняется значениями BST

        ArrayList<Integer> a1 = new ArrayList<>();

  

        // список a2 содержит все значения BST

        // возвращается методом treeToList

        ArrayList<Integer> a2 = treeToList(node, a1);

  

        int start = 0; // Начальный индекс a2

  

        int end = a2.size() - 1; // Конечный индекс а2

  

        while (start < end) {

  

            if (a2.get(start) + a2.get(end) == target) // Цель найдена!

            {

                System.out.println("Pair Found: " + a2.get(start) + " + " + a2.get(end) + " "

                                   + "= " + target);

                return true;

            }

  

            if (a2.get(start) + a2.get(end) > target) // конец декремента

            {

                end--;

            }

  

            if (a2.get(start) + a2.get(end) < target) // увеличивает начало

            {

                start++;

            }

        }

  

        System.out.println("No such values are found!");

        return false;

    }

  

    // Функция драйвера

    public static void main(String[] args)

    {

        BinarySearchTree tree = new BinarySearchTree();

        / *

                   15

                / /

              10 20

             / / / /

            8 12 16 25 * /

        tree.insert(15);

        tree.insert(10);

        tree.insert(20);

        tree.insert(8);

        tree.insert(12);

        tree.insert(16);

        tree.insert(25);

  

        tree.isPairPresent(tree.root, 33);

    }

}

  
// Этот код предоставлен Камалем Равалом

C #

// C # код для поиска пары с заданной суммой
// в сбалансированном BST

using System;

using System.Collections.Generic;

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

public class Node {

  

    public int data;

    public Node left, right;

  

    public Node(int d)

    {

        data = d;

        left = right = null;

    }

}

  

public class BinarySearchTree {

  

    // Корень BST

    Node root;

  

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

    BinarySearchTree()

    {

        root = null;

    }

  

    // По обходу дерева

    void inorder()

    {

        inorderUtil(this.root);

    }

  

    // Сервисная функция для обхода дерева по порядку

    void inorderUtil(Node node)

    {

        if (node == null)

            return;

  

        inorderUtil(node.left);

        Console.Write(node.data + " ");

        inorderUtil(node.right);

    }

  

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

    void insert(int key)

    {

        root = insertRec(root, key);

    }

  

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

    Node insertRec(Node root, int data)

    {

  

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

        if (root == null) {

            root = new Node(data);

            return root;

        }

  

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

        if (data < root.data)

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

        else if (data > root.data)

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

  

        return root;

    }

  

    // Метод, который добавляет значения данного BST в ArrayList

    // и, следовательно, возвращает ArrayList

    List<int> treeToList(Node node, List<int> list)

    {

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

        if (node == null)

            return list;

  

        treeToList(node.left, list);

        list.Add(node.data);

        treeToList(node.right, list);

  

        return list;

    }

  

    // метод, который проверяет наличие пары

    bool isPairPresent(Node node, int target)

    {

        // Этот список a1 передается в качестве аргумента

        // в методе treeToList

        // который позже заполняется значениями BST

        List<int> a1 = new List<int>();

  

        // список a2 содержит все значения BST

        // возвращается методом treeToList

        List<int> a2 = treeToList(node, a1);

  

        int start = 0; // Начальный индекс a2

  

        int end = a2.Count - 1; // Конечный индекс а2

  

        while (start < end) {

  

            if (a2[start] + a2[end] == target) // Цель найдена!

            {

                Console.WriteLine("Pair Found: " + a2[start] + " + " + a2[end] + " "

                                  + "= " + target);

                return true;

            }

  

            if (a2[start] + a2[end] > target) // конец декремента

            {

                end--;

            }

  

            if (a2[start] + a2[end] < target) // увеличивает начало

            {

                start++;

            }

        }

  

        Console.WriteLine("No such values are found!");

        return false;

    }

  

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

    public static void Main(String[] args)

    {

        BinarySearchTree tree = new BinarySearchTree();

        / *

                15

                / /

            10 20

            / / / /

            8 12 16 25 * /

        tree.insert(15);

        tree.insert(10);

        tree.insert(20);

        tree.insert(8);

        tree.insert(12);

        tree.insert(16);

        tree.insert(25);

  

        tree.isPairPresent(tree.root, 33);

    }

}

  
// Этот код предоставлен Rajput-Ji


Выход :

Pair Found: 8 + 25 = 33

Оптимизированное пространство обсуждается в предыдущем посте . Идея состояла в том, чтобы сначала преобразовать BST в двусвязный список (DLL) на месте, а затем найти пару в отсортированной DLL за O (n) раз. Это решение занимает O (n) времени и O (Logn) дополнительного пространства, но оно модифицирует данный BST.

Решение, рассмотренное ниже, занимает O (n) время, O (Logn) пространство и не модифицирует BST . Идея состоит в том же, что нахождение пары в отсортированном массиве (см метод 1 из этого для деталей). Мы проходим BST в нормальном и обратном порядке одновременно. В обратном порядке мы начинаем с самого правого узла, который является узлом максимального значения. В обычном порядке мы начинаем с самого левого узла, который является узлом минимального значения. Мы добавляем сумму текущих узлов в обоих обходах и сравниваем эту сумму с заданной целевой суммой. Если сумма совпадает с целевой суммой, мы возвращаем true. Если сумма больше целевой суммы, мы переходим к следующему узлу при обратном обходе по порядку, в противном случае мы переходим к следующему узлу при обычном обходе по порядку. Если какой-либо из обходов завершен без поиска пары, мы возвращаем false. Ниже приводится реализация этого подхода на C ++.

C ++

/ * В сбалансированном бинарном дереве поиска
isPairPresent два элемента, который суммирует
заданное значение времени O (n) пробел O (logn) * /
#include <bits/stdc++.h>

using namespace std;

#define MAX_SIZE 100

  
// узел BST

class node {

public:

    int val;

    node *left, *right;

};

  
// Тип стека

class Stack {

public:

    int size;

    int top;

    node** array;

};

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

Stack* createStack(int size)

{

    Stack* stack = new Stack();

    stack->size = size;

    stack->top = -1;

    stack->array = new node*[(stack->size * sizeof(node*))];

    return stack;

}

  
// ОСНОВНЫЕ ОПЕРАЦИИ СТЕКА

int isFull(Stack* stack)

{

    return stack->top - 1 == stack->size;

}

  

int isEmpty(Stack* stack)

{

    return stack->top == -1;

}

  

void push(Stack* stack, node* node)

{

    if (isFull(stack))

        return;

    stack->array[++stack->top] = node;

}

  
node* pop(Stack* stack)
{

    if (isEmpty(stack))

        return NULL;

    return stack->array[stack->top--];

}

  
// Возвращает true, если пара с целью
// сумма существует в BST, иначе ложь

bool isPairPresent(node* root, int target)

{

    // Создать два стека. s1 используется для

    // нормальный обход по порядку и s2

    // используется для обратного прохождения заказа

    Stack* s1 = createStack(MAX_SIZE);

    Stack* s2 = createStack(MAX_SIZE);

  

    // Обратите внимание, что размеры стеков MAX_SIZE,

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

    // как O (Logn) для сбалансированных деревьев, таких как AVL и Red Black

    // дерево. Мы использовали MAX_SIZE, чтобы сохранить код простым

  

    // done1, val1 и curr1 используются для

    // нормальный обход в порядке с использованием s1

    // done2, val2 и curr2 используются для

    // обратный порядок обхода с использованием s2

    bool done1 = false, done2 = false;

    int val1 = 0, val2 = 0;

    node *curr1 = root, *curr2 = root;

  

    // Цикл прервется, когда мы найдем пару или один из двух

    // обход завершен

    while (1) {

        // Найти следующий узел в обычном порядке

        // обход. Смотрите следующий пост

        // https: // www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/

        while (done1 == false) {

            if (curr1 != NULL) {

                push(s1, curr1);

                curr1 = curr1->left;

            }

            else {

                if (isEmpty(s1))

                    done1 = 1;

                else {

                    curr1 = pop(s1);

                    val1 = curr1->val;

                    curr1 = curr1->right;

                    done1 = 1;

                }

            }

        }

  

        // Найти следующий узел в обратном обходе Inorder. Единственный

        // разница между циклом выше и ниже, в цикле ниже

        // правое поддерево проходит перед левым поддеревом

        while (done2 == false) {

            if (curr2 != NULL) {

                push(s2, curr2);

                curr2 = curr2->right;

            }

            else {

                if (isEmpty(s2))

                    done2 = 1;

                else {

                    curr2 = pop(s2);

                    val2 = curr2->val;

                    curr2 = curr2->left;

                    done2 = 1;

                }

            }

        }

  

        // Если мы найдем пару, то напечатаем пару и вернемся. Первый

        // условие гарантирует, что два одинаковых значения не добавляются

        if ((val1 != val2) && (val1 + val2) == target) {

            cout << "Pair Found: " << val1 << "+ " << val2 << " = " << target << endl;

            return true;

        }

  

        // Если сумма текущих значений меньше,

        // затем перейти к следующему узлу в

        // нормальный обход

        else if ((val1 + val2) < target)

            done1 = false;

  

        // Если сумма текущих значений больше,

        // затем перейти к следующему узлу в

        // обратный обход обхода

        else if ((val1 + val2) > target)

            done2 = false;

  

        // Если какой-либо из обходов

        // кончено, тогда пары нет

        // возвращаем false

        if (val1 >= val2)

            return false;

    }

}

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

node* NewNode(int val)

{

    node* tmp = new node();

    tmp->val = val;

    tmp->right = tmp->left = NULL;

    return tmp;

}

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

int main()

{

    / *

                15

                / /

            10 20

            / / / /

            8 12 16 25 * /

    node* root = NewNode(15);

    root->left = NewNode(10);

    root->right = NewNode(20);

    root->left->left = NewNode(8);

    root->left->right = NewNode(12);

    root->right->left = NewNode(16);

    root->right->right = NewNode(25);

  

    int target = 33;

    if (isPairPresent(root, target) == false)

        cout << "\nNo such values are found\n";

    return 0;

}

  
// Этот код предоставлен rathbhupendra

С

/ * В сбалансированном бинарном дереве поиска isPairPresent два элемента, которые суммируются в

   заданное значение времени O (n) пробел O (logn) * /

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

  
// узел BST

struct node {

    int val;

    struct node *left, *right;

};

  
// Тип стека

struct Stack {

    int size;

    int top;

    struct node** array;

};

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

struct Stack* createStack(int size)

{

    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));

    stack->size = size;

    stack->top = -1;

    stack->array = (struct node**)malloc(stack->size * sizeof(struct node*));

    return stack;

}

  
// ОСНОВНЫЕ ОПЕРАЦИИ СТЕКА

int isFull(struct Stack* stack)

{

    return stack->top - 1 == stack->size;

}

  

int isEmpty(struct Stack* stack)

{

    return stack->top == -1;

}

  

void push(struct Stack* stack, struct node* node)

{

    if (isFull(stack))

        return;

    stack->array[++stack->top] = node;

}

  

struct node* pop(struct Stack* stack)

{

    if (isEmpty(stack))

        return NULL;

    return stack->array[stack->top--];

}

  
// Возвращает true, если в BST существует пара с целевой суммой, иначе false

bool isPairPresent(struct node* root, int target)

{

    // Создать два стека. s1 используется для нормального обхода

    // и s2 используется для обратного обхода

    struct Stack* s1 = createStack(MAX_SIZE);

    struct Stack* s2 = createStack(MAX_SIZE);

  

    // Обратите внимание, что размеры стеков MAX_SIZE, мы можем найти размер дерева и

    // исправить размер стека как O (Logn) для сбалансированных деревьев, таких как AVL и Red Black

    // дерево. Мы использовали MAX_SIZE, чтобы сохранить код простым

  

    // done1, val1 и curr1 используются для нормального обхода inorder с использованием s1

    // done2, val2 и curr2 используются для обратного обхода inorder с использованием s2

    bool done1 = false, done2 = false;

    int val1 = 0, val2 = 0;

    struct node *curr1 = root, *curr2 = root;

  

    // Цикл прервется, когда мы найдем пару или один из двух

    // обход завершен

    while (1) {

        // Найти следующий узел в нормальном обходе Inorder. Смотрите следующий пост

        // https: // www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/

        while (done1 == false) {

            if (curr1 != NULL) {

                push(s1, curr1);

                curr1 = curr1->left;

            }

            else {

                if (isEmpty(s1))

                    done1 = 1;

                else {

                    curr1 = pop(s1);

                    val1 = curr1->val;

                    curr1 = curr1->right;

                    done1 = 1;

                }

            }

        }

  

        // Найти следующий узел в обратном обходе Inorder. Единственный

        // разница между циклом выше и ниже, в цикле ниже

        // правое поддерево проходит перед левым поддеревом

        while (done2 == false) {

            if (curr2 != NULL) {

                push(s2, curr2);

                curr2 = curr2->right;

            }

            else {

                if (isEmpty(s2))

                    done2 = 1;

                else {

                    curr2 = pop(s2);

                    val2 = curr2->val;

                    curr2 = curr2->left;

                    done2 = 1;

                }

            }

        }

  

        // Если мы найдем пару, то напечатаем пару и вернемся. Первый

        // условие гарантирует, что два одинаковых значения не добавляются

        if ((val1 != val2) && (val1 + val2) == target) {

            printf("\n Pair Found: %d + %d = %d\n", val1, val2, target);

            return true;

        }

  

        // Если сумма текущих значений меньше, то перейти к следующему узлу в

        // нормальный обход

        else if ((val1 + val2) < target)

            done1 = false;

  

        // Если сумма текущих значений больше, то перейти к следующему узлу в

        // обратный обход обхода

        else if ((val1 + val2) > target)

            done2 = false;

  

        // Если какой-либо из прохождений по порядку завершен, пары нет

        // возвращаем false

        if (val1 >= val2)

            return false;

    }

}

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

struct node* NewNode(int val)

{

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

    tmp->val = val;

    tmp->right = tmp->left = NULL;

    return tmp;

}

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

int main()

{

    / *

                   15

                / /

              10 20

             / / / /

            8 12 16 25 * /

    struct node* root = NewNode(15);

    root->left = NewNode(10);

    root->right = NewNode(20);

    root->left->left = NewNode(8);

    root->left->right = NewNode(12);

    root->right->left = NewNode(16);

    root->right->right = NewNode(25);

  

    int target = 33;

    if (isPairPresent(root, target) == false)

        printf("\n No such values are found\n");

  

    getchar();

    return 0;

}


Выход:

 Pair Found: 8 + 25 = 33

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

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

Найти пару с заданной суммой в сбалансированном BST

0.00 (0%) 0 votes