Рубрики

Самый низкий общий предок в дереве бинарного поиска.

По заданным значениям двух значений n1 и n2 в дереве двоичного поиска найдите L owest C ommon A ncestor (LCA). Вы можете предположить, что оба значения существуют в дереве.

LCA of 10 and 14 is 12
LCA of 14 and 8 is 8
LCA of 10 and 22 is 20

Ниже приводится определение LCA из Википедии :
Пусть T — корневое дерево. Самый низкий общий предок между двумя узлами n1 и n2 определяется как самый низкий узел в T, у которого оба n1 и n2 являются потомками (где мы позволяем узлу быть потомком самого себя).

LCA для n1 и n2 в T является общим предком n1 и n2, который расположен дальше всего от корня. Вычисление низших общих предков может быть полезно, например, как часть процедуры определения расстояния между парами узлов в дереве: расстояние от n1 до n2 может быть вычислено как расстояние от корня до n1 плюс расстояние от корня до n2, минус удвоенное расстояние от корня до их самого низкого общего предка. (Источник вики )

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

Мы можем решить эту проблему, используя свойства BST. Мы можем рекурсивно пройти BST от корня. Основная идея решения заключается в том, что при обходе сверху вниз первый узел n, с которым мы сталкиваемся, имеет значение между n1 и n2, т. Е. N1 <n <n2 или то же, что и один из n1 или n2, это LCA для n1 и n2 (при условии, что n1 <n2). Так что просто рекурсивно проходите через BST, если значение узла больше, чем n1 и n2, тогда наша LCA лежит в левой части узла, если она меньше, чем n1 и n2, тогда LCA лежит на правой стороне. В противном случае root — это LCA (при условии, что в BST присутствуют как n1, так и n2)

С

// Рекурсивная C-программа для поиска LCA двух узлов n1 и n2.
#include <stdio.h>
#include <stdlib.h>

  

struct node

{

    int data;

    struct node* left, *right;

};

  
/ * Функция для нахождения LCA из n1 и n2. Функция предполагает, что оба

   n1 и n2 присутствуют в BST * /

struct node *lca(struct node* root, int n1, int n2)

{

    if (root == NULL) return NULL;

  

    // Если n1 и n2 меньше, чем root, то LCA лежит слева

    if (root->data > n1 && root->data > n2)

        return lca(root->left, n1, n2);

  

    // Если n1 и n2 больше, чем root, то LCA лежит справа

    if (root->data < n1 && root->data < n2)

        return lca(root->right, n1, n2);

  

    return root;

}

  
/ * Вспомогательная функция, которая выделяет новый узел с заданными данными. * /

struct node* newNode(int data)

{

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

    node->data  = data;

    node->left  = node->right = NULL;

    return(node);

}

  
/ * Программа драйвера для проверки lca () * /

int main()

{

    // Давайте построим BST, показанный на рисунке выше

    struct node *root        = newNode(20);

    root->left               = newNode(8);

    root->right              = newNode(22);

    root->left->left         = newNode(4);

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

    root->left->right->left  = newNode(10);

    root->left->right->right = newNode(14);

  

    int n1 = 10, n2 = 14;

    struct node *t = lca(root, n1, n2);

    printf("LCA of %d and %d is %d \n", n1, n2, t->data);

  

    n1 = 14, n2 = 8;

    t = lca(root, n1, n2);

    printf("LCA of %d and %d is %d \n", n1, n2, t->data);

  

    n1 = 10, n2 = 22;

    t = lca(root, n1, n2);

    printf("LCA of %d and %d is %d \n", n1, n2, t->data);

  

    getchar();

    return 0;

}

C ++

// Рекурсивная программа CPP для поиска
// LCA двух узлов n1 и n2.
#include <bits/stdc++.h>

using namespace std;

  

class node 

    public:

    int data; 

    node* left, *right; 

}; 

  
/ * Функция для нахождения LCA из n1 и n2.
Функция предполагает, что оба
n1 и n2 присутствуют в BST * /

node *lca(node* root, int n1, int n2) 

    if (root == NULL) return NULL; 

  

    // Если оба n1 и n2 меньше

    // чем корень, то LCA лежит слева

    if (root->data > n1 && root->data > n2) 

        return lca(root->left, n1, n2); 

  

    // Если n1 и n2 больше чем

    // корень, то LCA лежит справа

    if (root->data < n1 && root->data < n2) 

        return lca(root->right, n1, n2); 

  

    return root; 

  
/ * Вспомогательная функция, которая выделяет
новый узел с заданными данными. * /

node* newNode(int data) 

    node* Node = new node();

    Node->data = data; 

    Node->left = Node->right = NULL; 

    return(Node); 

  
/ * Код водителя * /

int main() 

    // Давайте построим BST

    // показано на рисунке выше

    node *root = newNode(20); 

    root->left = newNode(8); 

    root->right = newNode(22); 

    root->left->left = newNode(4); 

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

    root->left->right->left = newNode(10); 

    root->left->right->right = newNode(14); 

  

    int n1 = 10, n2 = 14; 

    node *t = lca(root, n1, n2); 

    cout << "LCA of " << n1 << " and " << n2 << " is " << t->data<<endl; 

  

    n1 = 14, n2 = 8; 

    t = lca(root, n1, n2); 

    cout<<"LCA of " << n1 << " and " << n2 << " is " << t->data << endl; 

  

    n1 = 10, n2 = 22; 

    t = lca(root, n1, n2); 

    cout << "LCA of " << n1 << " and " << n2 << " is " << t->data << endl; 

    return 0; 

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

Джава

// Рекурсивная Java-программа для печати lca двух узлов

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

class Node 

{

    int data;

    Node left, right;

   

    Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

   

class BinaryTree 

{

    Node root;

       

    / * Функция для нахождения LCA из n1 и n2. Функция предполагает, что оба

       n1 и n2 присутствуют в BST * /

    Node lca(Node node, int n1, int n2) 

    {

        if (node == null)

            return null;

   

        // Если n1 и n2 меньше, чем root, то LCA лежит слева

        if (node.data > n1 && node.data > n2)

            return lca(node.left, n1, n2);

   

        // Если n1 и n2 больше, чем root, то LCA лежит справа

        if (node.data < n1 && node.data < n2) 

            return lca(node.right, n1, n2);

   

        return node;

    }

   

    / * Программа драйвера для проверки lca () * /

    public static void main(String args[]) 

    {

        // Давайте построим BST, показанный на рисунке выше

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(20);

        tree.root.left = new Node(8);

        tree.root.right = new Node(22);

        tree.root.left.left = new Node(4);

        tree.root.left.right = new Node(12);

        tree.root.left.right.left = new Node(10);

        tree.root.left.right.right = new Node(14);

   

        int n1 = 10, n2 = 14;

        Node t = tree.lca(tree.root, n1, n2);

        System.out.println("LCA of " + n1 + " and " + n2 + " is " + t.data);

   

        n1 = 14;

        n2 = 8;

        t = tree.lca(tree.root, n1, n2);

        System.out.println("LCA of " + n1 + " and " + n2 + " is " + t.data);

   

        n1 = 10;

        n2 = 22;

        t = tree.lca(tree.root, n1, n2);

        System.out.println("LCA of " + n1 + " and " + n2 + " is " + t.data);

   

    }

}

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

питон

# Рекурсивная программа на Python для поиска LCA двух узлов
# n1 и n2

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

class Node:

  

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

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

  
# Функция, чтобы найти LCA из n1 и n2. Функция предполагает
# что оба n1 и n2 присутствуют в BST

def lca(root, n1, n2):

      

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

    if root is None:

        return None

  

    # Если n1 и n2 меньше, чем root, то LCA

    # лежит слева

    if(root.data > n1 and root.data > n2):

        return lca(root.left, n1, n2)

  

    # Если n1 и n2 больше, чем root, то LCA

    # лежит в праве

    if(root.data < n1 and root.data < n2):

        return lca(root.right, n1, n2)

  

    return root

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

  
# Давайте построим BST, показанный на рисунке

root = Node(20)

root.left = Node(8)

root.right = Node(22)

root.left.left = Node(4)

root.left.right = Node(12)

root.left.right.left = Node(10)

root.left.right.right = Node(14)

  

n1 = 10 ; n2 = 14

t = lca(root, n1, n2)

print "LCA of %d and %d is %d" %(n1, n2, t.data)

  

n1 = 14 ; n2 = 8

t = lca(root, n1, n2)

print "LCA of %d and %d is %d" %(n1, n2 , t.data)

  

n1 = 10 ; n2 = 22

t = lca(root, n1, n2)

print "LCA of %d and %d is %d" %(n1, n2, t.data)

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

C #

using System;

  
// Рекурсивная программа на C # для вывода lca из двух узлов

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

public class Node

{

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

public class BinaryTree

{

    public Node root;

  

    / * Функция для нахождения LCA из n1 и n2. Функция предполагает, что оба

       n1 и n2 присутствуют в BST * /

    public virtual Node lca(Node node, int n1, int n2)

    {

        if (node == null)

        {

            return null;

        }

  

        // Если n1 и n2 меньше, чем root, то LCA лежит слева

        if (node.data > n1 && node.data > n2)

        {

            return lca(node.left, n1, n2);

        }

  

        // Если n1 и n2 больше, чем root, то LCA лежит справа

        if (node.data < n1 && node.data < n2)

        {

            return lca(node.right, n1, n2);

        }

  

        return node;

    }

  

    / * Программа драйвера для проверки lca () * /

    public static void Main(string[] args)

    {

        // Давайте построим BST, показанный на рисунке выше

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(20);

        tree.root.left = new Node(8);

        tree.root.right = new Node(22);

        tree.root.left.left = new Node(4);

        tree.root.left.right = new Node(12);

        tree.root.left.right.left = new Node(10);

        tree.root.left.right.right = new Node(14);

  

        int n1 = 10, n2 = 14;

        Node t = tree.lca(tree.root, n1, n2);

        Console.WriteLine("LCA of " + n1 + " and " + n2 + " is " + t.data);

  

        n1 = 14;

        n2 = 8;

        t = tree.lca(tree.root, n1, n2);

        Console.WriteLine("LCA of " + n1 + " and " + n2 + " is " + t.data);

  

        n1 = 10;

        n2 = 22;

        t = tree.lca(tree.root, n1, n2);

        Console.WriteLine("LCA of " + n1 + " and " + n2 + " is " + t.data);

  

    }

}

  

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


Выход:

LCA of 10 and 14 is 12
LCA of 14 and 8 is 8
LCA of 10 and 22 is 20

Временная сложность вышеуказанного решения составляет O (h), где h — высота дерева. Также вышеприведенное решение требует O (h) дополнительного пространства в стеке вызовов функций для рекурсивных вызовов функций. Мы можем избежать лишнего пространства, используя итеративное решение .

C ++

/ * Функция для нахождения LCA из n1 и n2. Функция предполагает, что оба

   n1 и n2 присутствуют в BST * /

struct node *lca(struct node* root, int n1, int n2)

{

    while (root != NULL)

    {

         // Если n1 и n2 меньше, чем root, то LCA лежит слева

        if (root->data > n1 && root->data > n2)

           root = root->left;

  

        // Если n1 и n2 больше, чем root, то LCA лежит справа

        else if (root->data < n1 && root->data < n2)

           root = root->right;

  

        else break;

    }

    return root;

}

Джава

/ * Функция для нахождения LCA из n1 и n2.
Функция предполагает, что оба
n1 и n2 присутствуют в BST * /

static node lca(node root, int n1, int n2) 

    while (root != null

    

        // Если оба n1 и n2 меньше

        // чем корень, то LCA лежит слева

        if (root.data > n1 && 

            root.data > n2) 

        root = root.left; 

  

        // Если оба n1 и n2 больше

        // чем корень, то LCA лежит в правом

        else if (root.data < n1 && 

                 root.data < n2) 

        root = root.right; 

  

        else break

    

    return root; 

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

python3

# Функция, чтобы найти LCA из n1 и n2.
# Функция предполагает, что оба
# n1 и n2 присутствуют в BST

def lca_iterative(root, n1, n2):

    while root:

        # Если n1 и n2 меньше, чем root,

        # тогда LCA лежит слева

        if root.data > n1 and root.data > n2:

            root = root.left

          

        # Если n1 и n2 больше, чем root,

        # тогда ДМС лежит в правом

        elif root.data < n1 and root.data < n2:

            root = root.right

  

        else:

            break

  

    return root

  
# Этот код предоставлен Sumit Bhardwaj (Timus)

Смотрите это для полной программы.

Вы можете также увидеть статьи ниже:

Самый низкий общий предок в бинарном дереве

LCA с помощью родительского указателя

Найти LCA в двоичном дереве с помощью RMQ

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

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

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

Самый низкий общий предок в дереве бинарного поиска.

0.00 (0%) 0 votes