Рубрики

Найти, есть ли триплет в сбалансированном BST, который добавляет к нулю

Учитывая сбалансированное дерево двоичного поиска (BST), напишите функцию isTripletPresent (), которая возвращает true, если в данном BST есть триплет с суммой, равной 0, в противном случае возвращает false. Ожидаемая сложность времени составляет O (n ^ 2), и только O (Logn) дополнительное пространство может быть использовано. Вы можете изменить данное Двоичное дерево поиска. Обратите внимание, что высота сбалансированного BST всегда O (Logn)
Например, isTripletPresent () должен возвращать true для следующего BST, поскольку существует триплет с суммой 0, триплет равен {-13, 6, 7}.

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

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

Ниже приводится решение, которое работает за время O (n ^ 2) и использует дополнительное пространство O (Logn) :
1) Преобразовать данный BST в двусвязный список (DLL)
2) Теперь перебираем все узлы DLL и, если ключ узла является отрицательным, найдите в DLL пару с суммой, равной ключу текущего узла, умноженному на -1. Чтобы найти пару, мы можем использовать подход, использованный в hasArrayTwoCandidates () в методе 1 этого поста.

C ++

// Программа на C ++, чтобы проверить, есть ли
// триплет с суммой, равной 0 в
// данный BST
#include <bits/stdc++.h>

using namespace std;

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

class node 

    public:

    int key; 

    node *left; 

    node *right; 

}; 

  
// Функция для преобразования данного BST в Doubly
// Связанный список. левый указатель используется
// как предыдущий указатель и правый указатель
// используется в качестве следующего указателя. Функция
// устанавливает * голову, чтобы указать на первый и * хвост
// чтобы указать на последний узел преобразованной DLL

void convertBSTtoDLL(node* root, node** head, node** tail) 

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

    if (root == NULL) 

        return

  

    // Сначала конвертируем левое поддерево

    if (root->left) 

        convertBSTtoDLL(root->left, head, tail); 

  

    // Затем меняем левый угол текущего корня

    // как последний узел левого поддерева

    root->left = *tail; 

  

    // Если tail не равен NULL, тогда устанавливается правильно

    // хвоста как корень, иначе текущий

    // узел - голова

    if (*tail) 

        (*tail)->right = root; 

    else

        *head = root; 

  

    // Обновление хвоста

    *tail = root; 

  

    // Наконец, преобразовать правильное поддерево

    if (root->right) 

        convertBSTtoDLL(root->right, head, tail); 

  
// Эта функция возвращает true, если есть
// пара в DLL с суммой, равной заданному
// сумма Алгоритм похож на hasArrayTwoCandidates ()
// в методе 1 http://tinyurl.com/dy6palr

bool isPresentInDLL(node* head, node* tail, int sum) 

    while (head != tail) 

    

        int curr = head->key + tail->key; 

        if (curr == sum) 

            return true

        else if (curr > sum) 

            tail = tail->left; 

        else

            head = head->right; 

    

    return false

  
// Основная функция, которая возвращает
// истина, если в триплете с 0 суммой
// BST в противном случае возвращает false

bool isTripletPresent(node *root) 

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

    if (root == NULL) 

    return false

  

    // Преобразовать данный BST в двусвязный список. голова и хвост хранят

    // указатели на первый и последний узлы в DLLL

    node* head = NULL; 

    node* tail = NULL; 

    convertBSTtoDLL(root, &head, &tail); 

  

    // Теперь перебираем все узлы и

    // найти, есть ли пара с суммой

    // равно -1 * heaf-> key, где head это текущий узел

    while ((head->right != tail) && (head->key < 0)) 

    

        // Если есть пара с суммой

        // равно -1 * head-> key, затем возвращаем

        // правда еще двигаться вперед

        if (isPresentInDLL(head->right, tail, -1*head->key)) 

            return true

        else

            head = head->right; 

    

  

    // Если мы достигнем здесь, то

    // триплета с нулевой суммой не было

    return false

  
// Полезная функция для создания
// новый узел 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; 

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

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); 

    if (isTripletPresent(root)) 

        cout << "Present"

    else

        cout << "Not Present"

    return 0; 

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

С

// Программа AC для проверки наличия триплета с суммой, равной 0 в
// данный BST
#include<stdio.h>

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

struct node

{

    int key;

    struct node *left;

    struct node *right;

};

  
// Функция для преобразования данного BST в двусвязный список. левый указатель используется
// как предыдущий указатель, а правый указатель используется как следующий указатель. Функция
// устанавливает * head для указания на первый и * tail для указания на последний узел преобразованной DLL

void convertBSTtoDLL(node* root, node** head, node** tail)

{

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

    if (root == NULL)

        return;

  

    // Сначала конвертируем левое поддерево

    if (root->left)

        convertBSTtoDLL(root->left, head, tail);

  

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

    root->left = *tail;

  

    // Если tail не равен NULL, тогда установить права на tail как root, иначе текущий

    // узел - голова

    if (*tail)

        (*tail)->right = root;

    else

        *head = root;

  

    // Обновление хвоста

    *tail = root;

  

    // Наконец, преобразовать правильное поддерево

    if (root->right)

        convertBSTtoDLL(root->right, head, tail);

}

  
// Эта функция возвращает true, если в DLL есть пара с равной суммой
// до заданной суммы. Алгоритм похож на hasArrayTwoCandidates ()
// в методе 1 http://tinyurl.com/dy6palr

bool isPresentInDLL(node* head, node* tail, int sum)

{

    while (head != tail)

    {

        int curr = head->key + tail->key;

        if (curr == sum)

            return true;

        else if (curr > sum)

            tail = tail->left;

        else

            head = head->right;

    }

    return false;

}

  
// Основная функция, которая возвращает true, если в триплете с 0 суммой
// BST в противном случае возвращает false

bool isTripletPresent(node *root)

{

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

    if (root == NULL)

       return false;

  

    // Преобразовать данный BST в двусвязный список. голова и хвост хранят

    // указатели на первый и последний узлы в DLLL

    node* head = NULL;

    node* tail = NULL;

    convertBSTtoDLL(root, &head, &tail);

  

    // Теперь итерация по каждому узлу и поиск пары с суммой

    // равно -1 * heaf-> key, где head это текущий узел

    while ((head->right != tail) && (head->key < 0))

    {

        // Если есть пара с суммой, равной -1 * head-> key, возвращаем

        // правда еще двигаться вперед

        if (isPresentInDLL(head->right, tail, -1*head->key))

            return true;

        else

            head = head->right;

    }

  

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

    return false;

}

  
// Вспомогательная функция для создания нового узла 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;

}

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

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);

    if (isTripletPresent(root))

        printf("Present");

    else

        printf("Not Present");

    return 0;

}


Выход:

Present

Обратите внимание, что вышеуказанное решение изменяет данный BST.

Сложность времени: Время, необходимое для преобразования BST в DLL, равно O (n), а время, необходимое для поиска триплета в DLL, равно O (n ^ 2).

Вспомогательное пространство: вспомогательное пространство требуется только для стека вызовов функций в рекурсивной функции convertBSTtoDLL (). Поскольку данное дерево сбалансировано (высота — O (Logn)), количество функций в стеке вызовов никогда не будет больше, чем O (Logn).

Мы также можем найти триплет в одно и то же время и дополнительное пространство без изменения дерева. Смотрите следующий пост. Обсуждаемый там код также может быть использован для поиска триплета.

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

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

Найти, есть ли триплет в сбалансированном BST, который добавляет к нулю

0.00 (0%) 0 votes