Преемник предварительного заказа всех узлов в двоичном дереве поиска

Опубликовано: 12 Января, 2022

Рассмотрим BST (двоичное дерево поиска), где дублирование недопустимо.
Данный ключ присутствует в BST. Задача состоит в том, чтобы найти его преемника предварительного заказа в этом BST, то есть задача состоит в том, чтобы найти ключ, который идет рядом с данным ключом, если мы применяем обход предварительного заказа на данном BST.

Пример:
Вставьте следующие ключи в BST в том же порядке: 51, 39, 31, 54, 92, 42, 21, 10, 26, 52, 36, 47, 82, 5, 62.
В итоге вы получите BST, как показано ниже:

Предварительный заказ : 51 39 31 21 10 5 26 36 42 47 54 52 92 82 62

 =====================================
Ключевой преемник предварительного заказа
=====================================
51 39
39 31
31 21
21 10 
10 5
5 26
26 36
36 42
42 47
47 54
52 92
92 82
82 62
62 Не существуют.
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Простой подход: простой и легкий способ решить эту проблему - применить обход предварительного заказа к данному BST и сохранить ключи BST в массиве. Затем найдите данный ключ в массиве. Если он существует, то его следующий ключ (который может не обязательно существовать) является его преемником предварительного заказа. Если данный ключ не существует в массиве, это означает, что данный ключ не существует в BST и, следовательно, для этого ключа не может быть никакого преемника предварительного заказа.
Но этот алгоритм имеет временную сложность O (n) . И пространственная сложность O (n), и, следовательно, это не лучший способ решения этой проблемы.

Эффективный подход : эффективный способ решения этой проблемы основан на следующих наблюдениях:

  • Найдите узел в BST, содержащий данный ключ.
    • Если его нет в BST, то для этого ключа не может быть никакого преемника предварительного заказа.
    • Если он существует в BST, то для этого ключа может быть преемник предварительного заказа. Обратите внимание, что если ключ существует, то необязательно, чтобы он имел преемника для предварительного заказа. Это зависит от позиции данного ключа в BST.
  • Если узел, содержащий данный ключ, имеет левый дочерний элемент, то его левый дочерний элемент является его преемником предварительного порядка.
  • Если узел, содержащий данное, имеет правого, но не левого дочернего элемента, то его правый дочерний элемент является его преемником предварительного порядка.
  • Если узел, содержащий данный ключ, является листом, тогда вам нужно найти его ближайшего предка, у которого есть правый дочерний элемент, и ключ этого предка больше, чем данный ключ, то есть вы должны искать его ближайшего предка в левом поддереве, из которого данное ключ существует. Далее два случая:
    • Такой предок существует, если это так, то правый дочерний элемент этого предка является преемником предварительного заказа данного ключа.
    • Такого предка не существует, если он существует, то для данного ключа не существует преемника для предварительного заказа.

Below is the implementation of the above approach :  

C

// C program to find pre-Order successor
// of a node in Binary Search Tree
#include<stdio.h>
#include<stdlib.h>
 
// Declare a structure
struct Node{
    // Key to be stored in BST
    int key;
 
    // Pointer to left child
    struct Node *left;
 
    // Pointer to the right child
    struct Node *right;
     
    // Pointer to parent
    struct Node *parent;
};
 
// This function inserts node in BST
struct Node* insert(int key, struct Node *root,
                                   struct Node *parent)
{
     
    // If root is NULL, insert key here
    if(!root)
    {
        // Allocate memory dynamically
        struct Node *node = (struct Node*)malloc(sizeof(struct Node));
 
        // Validate malloc call
        if(node)
        {
            // Populate the object pointer to by
            // pointer named node
            node->key = key;
            node->left = node->right = NULL;
            node->parent = parent;
 
            // Return newly created node
            return node;
             
        }
        else
            // Malloc was not successful to satisfy our request,
            // given an appropriate message to the user
            printf("Could not allocate memory.");
         
    }
     
    // If this is a duplicate key then give a message to user
    else if(key == root->key)
        printf("Duplicates are not allowed in BST.");
     
    // If the key to be inserted is greater than the root"s
    // key then it will go to the right subtree of
    // the tree with current root
    else if(key > root->key)
        root->right = insert(key, root->right,root);
     
    // If the key to be inserted is smaller than the
    // root"s key then it will go to a left subtree of
    // the tree with current root
    else
        root->left = insert(key, root->left, root);
     
    // Return the root
    return root;
}
 
// This function searched for a given key in BST
struct Node* search(int key, struct Node *root)
{
    // Since the root is empty and hence key
    // does not exist in BST
    if(!root)
        return NULL;
     
    // Current root contains the given key,
    // so return current root
    else if( key == root->key)
        return root;
     
    // Key is greater than the root"s key and therefore
    // we will search for this key in the right subtree of
    // tree with root as current root because of all of the keys
    // which are greater than the root"s key exist in the right subtree   
    else if(key > root->key)
        return search(key, root->right);
     
    // Key is smaller than the root"s key and therefore we will
    // search for this key in the left subtree of the tree with
    // root as the current root because of all of the keys which are
    // smaller than the root"s key exists in the left subtree
    // search tree in the left subtree
    else
        return search(key, root->left);
     
}
 
// This function returns the node that contains the
// pre-order successor for the given key
struct Node* preOrderSuccessor(int key, struct Node *root){
 
    // Search for a node in BST that contains the given key
    struct Node *node = search(key, root);
 
    // There is no node in BST that contains the given key,
    // give an appropriate message to user
    if(!node){
        printf("%d do not exists in BST. ", key);
        return NULL;
    }
 
 
    // There exist a node in BST that contains the given key
    // Apply our observations
    if(node->left)
        // If left child of the node that contains the
        // given key exist then it is the pre-order
        // successor for the given key
        return node->left;
 
    else if(node->right)
        // If right but not left child of node that contains
        // the given key exist then it is the pre-order
        // successor for the given key
        return node->right;
 
    else
    {
        // Node containing the key has neither left nor right child
        // which means that it is leaf node. In this case we will search
        // for its nearest ancestor with right child which has a key
        // greater than the given key
 
        // Since node is a leaf node so its parent is guaranteed to exist
        struct Node *temp = node->parent;
 
        // Search for nearest ancestor with right child that has
        // key greater than the given key
        while(temp){
            if(key < temp->key && temp->right)
                break;
            temp = temp->parent;
        }
 
        // If such an ancestor exist then right child of this ancestor
        // is the pre-order successor for the given otherwise there
        // do not exist any pre-order successor for the given key
        return temp ? temp->right : NULL;
    }
}
 
// This function traverse the BST in pre-order fashion
void preOrder(struct Node *root)
{
    if(root)
    {
        // First visit the root
        printf("%d ", root->key);
         
        // Next visit its left subtree
        preOrder(root->left);
         
        // Finally visit its right subtree
        preOrder(root->right);
    }
}
 
// Driver code
int main()
{
    // Declares a root for our BST
    struct Node *ROOT = NULL;
 
    // We will create 15 random integers in
    // range 0-99 to populate our BST
    int a[] = {51, 39, 31, 54, 92, 42, 21, 10,
                          26, 52, 36, 47, 82, 5, 62};
 
    int n = sizeof(a) / sizeof(a[0]);
     
    // Insert all elements into BST
    for(int i = 0 ; i < n; i++)
    {
        // Insert the generated number in BST
        printf("Inserting %2d.....", a[i]);
         
        ROOT = insert(a[i], ROOT, NULL);
        printf("Finished Insertion. ");
    }
 
    // Apply pre-order traversal on BST
    printf(" Pre-Order Traversal : ");
    preOrder(ROOT);
 
    // Display pre-order Successors for all of the keys in BST
    printf(" =====================================");
    printf(" %-10s%s ", "Key", "Pre-Order Successor");
    printf("===================================== ");
 
    // This stores the pre-order successor for a given key
    struct Node *successor = NULL;
 
    // Iterate through all of the elements inserted
    // in BST to get their pre-order successor
    for(int i = 0 ; i < n; ++i)
    {
        // Get the pre-order successor for the given key
        successor = preOrderSuccessor(a[i], ROOT);
 
        if(successor)
            // Successor is not NULL and hence it contains
            // the pre-order successor for given key
            printf("%-10d%d ", a[i], successor->key);
        else
            // Successor is NULL and hence given key do
            // not have a pre-order successor
            printf("%-10dDo Not Exist. ", a[i]);
    }
 
    return 0;
}

Java

// Java program to find pre-Order successor
// of a node in Binary Search Tree
import java.util.*;
 
class GFG
{
 
// Declare a structure
static class Node
{
    // Key to be stored in BST
    int key;
 
    // Pointer to left child
    Node left;
 
    // Pointer to the right child
    Node right;
     
    // Pointer to parent
    Node parent;
};
 
// This function inserts node in BST
static Node insert(int key, Node root,
                            Node parent)
{
     
    // If root is null, insert key here
    if(root == null)
    {
        // Allocate memory dynamically
        Node node = new Node();
 
        // Validate malloc call
        if(node != null)
        {
            // Populate the object pointer to by
            // pointer named node
            node.key = key;
            node.left = node.right = null;
            node.parent = parent;
 
            // Return newly created node
            return node;
             
        }
        else
         
            // Malloc was not successful to
            // satisfy our request, given
            // an appropriate message to the user
            System.out.printf("Could not allocate memory.");
    }
     
    // If this is a duplicate key then
    // give a message to user
    else if(key == root.key)
        System.out.printf("Duplicates are not" +
                            " allowed in BST.");
     
    // If the key to be inserted is greater than
    // the root"s key then it will go to the
    // right subtree of the tree with current root
    else if(key > root.key)
        root.right = insert(key, root.right, root);
     
    // If the key to be inserted is smaller than the
    // root"s key then it will go to a left subtree
    // of the tree with current root
    else
        root.left = insert(key, root.left, root);
     
    // Return the root
    return root;
}
 
// This function searched for a given key in BST
static Node search(int key, Node root)
{
    // Since the root is empty and hence
    // key does not exist in BST
    if(root == null)
        return null;
     
    // Current root contains the given key,
    // so return current root
    else if( key == root.key)
        return root;
     
    // Key is greater than the root"s key and 
    // therefore we will search for this key
    // in the right subtree of tree with root
    // as current root because of all of the keys
    // which are greater than the root"s key
    // exist in the right subtree
    else if(key > root.key)
        return search(key, root.right);
     
    // Key is smaller than the root"s key and
    // therefore we will search for this key
    // in the left subtree of the tree with root
    // as the current root because of all of the keys
    // which are smaller than the root"s key exists in
    // the left subtree search tree in the left subtree
    else
        return search(key, root.left);
}
 
// This function returns the node
// that contains the pre-order successor
// for the given key
static Node preOrderSuccessor(int key,
                              Node root)
{
 
    // Search for a node in BST
    // that contains the given key
    Node node = search(key, root);
 
    // There is no node in BST
    // that contains the given key,
    // give an appropriate message to user
    if(node == null)
    {
        System.out.printf("%d do not exists" +
                           " in BST. ", key);
        return null;
    }
 
    // There exist a node in BST that contains
    // the given key. Apply our observations
    if(node.left != null)
    <
Алгоритмы Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Разница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана
21 Января, 2023
Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023
Когда использовать Queue over ArrayList в Java?
6 Января, 2023