Рубрики

Inorder предшественник и преемник для данного ключа в BST

Недавно я столкнулся с вопросом в интервью компании электронной коммерции. Интервьюер задал следующий вопрос:

Существует BST с корневым узлом с ключевой частью только как целое число. Структура каждого узла выглядит следующим образом:

struct Node

{

    int key;

    struct Node *left, *right ;

};

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

Ниже приведен алгоритм достижения желаемого результата. Это рекурсивный метод:

Input: root node, key
output: predecessor node, successor node

1. If root is NULL
      then return
2. if key is found then
    a. If its left subtree is not null
        Then predecessor will be the right most 
        child of left subtree or left child itself.
    b. If its right subtree is not null
        The successor will be the left most child 
        of right subtree or right child itself.
    return
3. If key is smaller then root node
        set the successor as root
        search recursively into left subtree
    else
        set the predecessor as root
        search recursively into right subtree

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

C ++

// C ++ программа для поиска предшественника и преемника в BST
#include <iostream>

using namespace std;

  
// BST Node

struct Node

{

    int key;

    struct Node *left, *right;

};

  
// Эта функция находит предшественника и преемника ключа в BST.
// Он устанавливает pre и suc как предшественника и преемника соответственно

void findPreSuc(Node* root, Node*& pre, Node*& suc, int key)

{

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

    if (root == NULL)  return ;

  

    // Если ключ присутствует в корне

    if (root->key == key)

    {

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

        if (root->left != NULL)

        {

            Node* tmp = root->left;

            while (tmp->right)

                tmp = tmp->right;

            pre = tmp ;

        }

  

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

        if (root->right != NULL)

        {

            Node* tmp = root->right ;

            while (tmp->left)

                tmp = tmp->left ;

            suc = tmp ;

        }

        return ;

    }

  

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

    if (root->key > key)

    {

        suc = root ;

        findPreSuc(root->left, pre, suc, key) ;

    }

    else // перейти к правильному поддереву

    {

        pre = root ;

        findPreSuc(root->right, pre, suc, key) ;

    }

}

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

Node *newNode(int item)

{

    Node *temp =  new Node;

    temp->key = item;

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

    return temp;

}

  
/ * Утилита для вставки нового узла с заданным ключом в 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;

}

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

int main()

{

    int key = 65;    // Ключ для поиска в BST

  

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

              50

           / /

          30 70

         / / / /

       20 40 60 80 *

    Node *root = NULL;

    root = insert(root, 50);

    insert(root, 30);

    insert(root, 20);

    insert(root, 40);

    insert(root, 70);

    insert(root, 60);

    insert(root, 80);

  

  

    Node* pre = NULL, *suc = NULL;

  

    findPreSuc(root, pre, suc, key);

    if (pre != NULL)

      cout << "Predecessor is " << pre->key << endl;

    else

      cout << "No Predecessor";

  

    if (suc != NULL)

      cout << "Successor is " << suc->key;

    else

      cout << "No Successor";

    return 0;

}

питон

# Программа Python для поиска предшественника и преемника в BST

  
# Узел BST

class Node:

  

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

    def __init__(self, key):

        self.key  = key

        self.left = None

        self.right = None

  
# Эта функция находит предшественника и преемника ключа в BST
# Он устанавливает pre и suc как предшественник и преемник соответственно

def findPreSuc(root, key):

  

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

    if root is None:

        return

  

    # Если ключ присутствует в корне

    if root.key == key:

  

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

        if root.left is not None:

            tmp = root.left 

            while(tmp.right):

                tmp = tmp.right 

            findPreSuc.pre = tmp

  

  

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

        if root.right is not None:

            tmp = root.right

            while(temp.left):

                tmp = tmp.left 

            findPreSuc.suc = tmp 

  

        return 

  

    # Если ключ меньше ключа root, перейдите в левое поддерево

    if root.key > key :

        findPreSuc.suc = root 

        findPreSuc(root.left, key)

  

    else: # перейти к нужному поддереву

        findPreSuc.pre = root

        findPreSuc(root.right, key)

  
# Полезная функция для вставки нового узла с заданным ключом в 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

  

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

key = 65 # Ключ для поиска в BST

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

              50

           / /

          30 70

         / / / /

       20 40 60 80

«»»

root = None

root = insert(root, 50)

insert(root, 30);

insert(root, 20);

insert(root, 40);

insert(root, 70);

insert(root, 60);

insert(root, 80);

  
# Статические переменные функции findPreSuc

findPreSuc.pre = None

findPreSuc.suc = None

  
findPreSuc(root, key)

  

if findPreSuc.pre is not None:

    print "Predecessor is", findPreSuc.pre.key

  

else:

    print "No Predecessor"

  

if findPreSuc.suc is not None:

    print "Successor is", findPreSuc.suc.key

else:

    print "No Successor"

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


Выход:

Predecessor is 60
Successor is 70

Другой подход:
Мы также можем найти преемника по порядку и предшественника по порядку, используя обход обхода. Убедитесь, что текущий узел меньше заданного ключа для предшественника и для преемника, проверьте, больше ли он, чем заданный ключ. Если он больше указанного ключа, проверьте, не меньше ли он уже сохраненного значения в преемнике, затем обновите его. Наконец, получите предшественник и преемник, сохраненные в q (преемник) и p (предшественник).

C ++

// код CPP для следующего преемника
// и предшественник дерева
#include<iostream>
#include<stdlib.h>

  

using namespace std;

  

struct Node

{

    int data;

    Node* left,*right;

};

   
// Функция для возврата данных

Node* getnode(int info)

{

    Node* p = (Node*)malloc(sizeof(Node));

    p->data = info;

    p->right = NULL;

    p->left = NULL;

    return p;

}

  
/ *
так как прохождение inorder приводит к
посещение узла в порядке возрастания
может хранить значения крупнейших
нет, который меньше, чем (предшественник)
и самое маленькое нет, которое больше, чем
(преемник) с использованием обхода по порядку
* /

void find_p_s(Node* root,int a, 

              Node** p, Node** q)

{

    // Если root равен null, вернуть

    if(!root)

        return ;

          

    // пройти левое поддерево

    find_p_s(root->left, a, p, q);

      

    // корневые данные больше чем

    if(root&&root->data > a)

    {

          

        // q хранит узел, данные которого больше

        // чем и меньше, чем ранее

        // хранимые данные в * q, который является наследником

        if((!*q) || (*q) && (*q)->data > root->data)

                *q = root;

    }

      

    // если корневые данные меньше чем

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

    else if(root && root->data < a)

    {

        *p = root;

    }

      

    // пройти правое поддерево

    find_p_s(root->right, a, p, q);

}

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

int main()

{

    Node* root1 = getnode(50);

    root1->left = getnode(20);

    root1->right = getnode(60);

    root1->left->left = getnode(10);

    root1->left->right = getnode(30);

    root1->right->left = getnode(55);

    root1->right->right = getnode(70);

    Node* p = NULL, *q = NULL;

   

    find_p_s(root1, 55, &p, &q);

      

    if(p)

        cout << p->data;

    if(q)

        cout << " " << q->data;

    return 0;

}

python3

"" "Код Python3 для следующего преемника
и предшественник дерева "" "

  
# Узел двоичного дерева
# Сервисная функция для создания нового узла дерева

class getnode: 

  

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

    def __init__(self, data): 

        self.data = data 

        self.left = None

        self.right = None

  
«»»
так как прохождение inorder приводит к
Восходящий порядок посещения узла, мы
может хранить значения крупнейших
о, который меньше, чем (предшественник)
и самое маленькое нет, которое больше, чем
(преемник) с использованием обхода по порядку
«»»

def find_p_s(root, a, p, q): 

  

    # Если root - None, вернуть

    if(not root):

        return

          

    # пройти левое поддерево

    find_p_s(root.left, a, p, q) 

      

    # корневые данные больше чем

    if(root and root.data > a):

          

        # q хранит узел, данные которого больше

        # чем и меньше, чем ранее

        # хранимые данные в * q, который является наследником

        if((not q[0]) or q[0] and 

                q[0].data > root.data):

            q[0] = root

              

    # если корневые данные меньше чем

    # сохранить его в p, который является предшественником

    elif(root and root.data < a):

        p[0]= root 

      

    # пройти правое поддерево

    find_p_s(root.right, a, p, q)

  
Код водителя

if __name__ == '__main__'

  

    root1 = getnode(50

    root1.left = getnode(20

    root1.right = getnode(60

    root1.left.left = getnode(10

    root1.left.right = getnode(30

    root1.right.left = getnode(55

    root1.right.right = getnode(70

    p = [None]

    q = [None

      

    find_p_s(root1, 55, p, q) 

      

    if(p[0]) :

        print(p[0].data, end = "")

    if(q[0]) :

        print("", q[0].data)

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

Выход :

50 60

Спасибо Shweta за предложение этого метода.

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

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

Inorder предшественник и преемник для данного ключа в BST

0.00 (0%) 0 votes