Рубрики

Самый низкий общий предок в бинарном дереве | Набор 2 (с помощью родительского указателя)

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

Например, рассмотрим двоичное дерево на диаграмме, значение LCA для 10 и 14 равно 12, а значение LCA для 8 и 14 равно 8.

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

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

Ниже приведены шаги, чтобы найти LCA.

  1. Создайте пустую хеш-таблицу.
  2. Вставьте n1 и всех его предков в хеш-таблицу.
  3. Проверьте, существует ли n2 или любой из его предков в хеш-таблице, если да, верните первого существующего предка.
  4. Ниже приведена реализация вышеуказанных шагов.

    С

    // C ++ программа для поиска наименьшего общего предка, используя родительский указатель
    #include <bits/stdc++.h>

    using namespace std;

      
    // Узел дерева

    struct Node

    {

        Node *left, *right, *parent;

        int key;

    };

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

    Node *newNode(int item)

    {

        Node *temp = new Node;

        temp->key = item;

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

        return temp;

    }

      
    / * Утилита для вставки нового узла с

       данный ключ в бинарном дереве поиска * /

    Node *insert(Node *node, int key)

    {

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

        if (node == NULL) return newNode(key);

      

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

        if (key < node->key)

        {

            node->left  = insert(node->left, key);

            node->left->parent = node;

        }

        else if (key > node->key)

        {

            node->right = insert(node->right, key);

            node->right->parent = node;

        }

      

        / * вернуть (неизмененный) указатель узла * /

        return node;

    }

      
    // Найти LCA узлов n1 и n2 в двоичном дереве
    Node *LCA(Node *n1, Node *n2)
    {

       // Создаем карту для хранения предков n1

       map <Node *, bool> ancestors;

      

       // Вставляем n1 и всех его предков в карту

       while (n1 != NULL)

       {

           ancestors[n1] = true;

           n1 = n1->parent;

       }

      

       // Проверяем, находится ли n2 или любой из его предков

       // карта.

       while (n2 != NULL)

       {

           if (ancestors.find(n2) != ancestors.end())

               return n2;

           n2 = n2->parent;

       }

      

       return NULL;

    }

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

    int main(void)

    {

        Node * root = NULL;

      

        root = insert(root, 20);

        root = insert(root, 8);

        root = insert(root, 22);

        root = insert(root, 4);

        root = insert(root, 12);

        root = insert(root, 10);

        root = insert(root, 14);

      

        Node *n1 = root->left->right->left;

        Node *n2 = root->left;

        Node *lca = LCA(n1, n2);

      

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

      

        return 0;

    }

    Джава

    import java.util.HashMap;

    import java.util.Map;

      
    // Java-программа для поиска наименьшего общего предка, используя родительский указатель
    // Узел дерева

    class Node 

    {

        int key;

        Node left, right, parent;

      

        Node(int key) 

        {

            this.key = key;

            left = right = parent = null;

        }

    }

      

    class BinaryTree 

    {

        Node root, n1, n2, lca;

      

        / * Утилита для вставки нового узла с

           данный ключ в бинарном дереве поиска * /

        Node insert(Node node, int key) 

        {

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

            if (node == null)

                return new Node(key);

      

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

            if (key < node.key) 

            {

                node.left = insert(node.left, key);

                node.left.parent = node;

            }

            else if (key > node.key) 

            {

                node.right = insert(node.right, key);

                node.right.parent = node;

            }

      

            / * вернуть (неизмененный) указатель узла * /

            return node;

        }

      

        // Найти LCA узлов n1 и n2 в двоичном дереве

        Node LCA(Node n1, Node n2) 

        {

            // Создаем карту для хранения предков n1

            Map<Node, Boolean> ancestors = new HashMap<Node, Boolean>();

      

            // Вставляем n1 и всех его предков в карту

            while (n1 != null

            {

                ancestors.put(n1, Boolean.TRUE);

                n1 = n1.parent;

            }

      

            // Проверяем, находится ли n2 или любой из его предков

            // карта.

            while (n2 != null

            {

                if (ancestors.containsKey(n2) != ancestors.isEmpty())

                    return n2;

                n2 = n2.parent;

            }

      

            return null;

        }

      

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

        public static void main(String[] args) 

        {

            BinaryTree tree = new BinaryTree();

            tree.root = tree.insert(tree.root, 20);

            tree.root = tree.insert(tree.root, 8);

            tree.root = tree.insert(tree.root, 22);

            tree.root = tree.insert(tree.root, 4);

            tree.root = tree.insert(tree.root, 12);

            tree.root = tree.insert(tree.root, 10);

            tree.root = tree.insert(tree.root, 14);

      

            tree.n1 = tree.root.left.right.left;

            tree.n2 = tree.root.left;

            tree.lca = tree.LCA(tree.n1, tree.n2);

      

            System.out.println("LCA of " + tree.n1.key + " and " + tree.n2.key

                    + " is " + tree.lca.key);

        }

    }

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

    C #

    // C # программа для поиска наименьшего общего предка, используя родительский указатель
    // Узел дерева

    using System;

    using System.Collections;

    using System.Collections.Generic; 

      

    public class Node 

    {

        public int key;

        public Node left, right, parent;

      

        public Node(int key) 

        {

            this.key = key;

            left = right = parent = null;

        }

    }

      

    class BinaryTree 

    {

        Node root, n1, n2, lca;

      

        / * Утилита для вставки нового узла с

        данный ключ в бинарном дереве поиска * /

        Node insert(Node node, int key) 

        {

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

            if (node == null)

                return new Node(key);

      

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

            if (key < node.key) 

            {

                node.left = insert(node.left, key);

                node.left.parent = node;

            }

            else if (key > node.key) 

            {

                node.right = insert(node.right, key);

                node.right.parent = node;

            }

      

            / * вернуть (неизмененный) указатель узла * /

            return node;

        }

      

        // Найти LCA узлов n1 и n2 в двоичном дереве

        Node LCA(Node n1, Node n2) 

        {

            // Создаем карту для хранения предков n1

            Dictionary<Node, Boolean> ancestors = new Dictionary<Node, Boolean>();

      

            // Вставляем n1 и всех его предков в карту

            while (n1 != null

            {

                ancestors.Add(n1,true);

                n1 = n1.parent;

            }

      

            // Проверяем, находится ли n2 или любой из его предков

            // карта.

            while (n2 != null

            {

                if (ancestors.ContainsKey(n2))

                    return n2;

                n2 = n2.parent;

            }

      

            return null;

        }

      

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

        public static void Main(String []args) 

        {

            BinaryTree tree = new BinaryTree();

            tree.root = tree.insert(tree.root, 20);

            tree.root = tree.insert(tree.root, 8);

            tree.root = tree.insert(tree.root, 22);

            tree.root = tree.insert(tree.root, 4);

            tree.root = tree.insert(tree.root, 12);

            tree.root = tree.insert(tree.root, 10);

            tree.root = tree.insert(tree.root, 14);

      

            tree.n1 = tree.root.left.right.left;

            tree.n2 = tree.root.left;

            tree.lca = tree.LCA(tree.n1, tree.n2);

      

            Console.WriteLine("LCA of " + tree.n1.key + " and " + tree.n2.key

                    + " is " + tree.lca.key);

        }

    }

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


    Выход:

    LCA of 10 and 8 is 8 

    Примечание. Приведенная выше реализация использует вставку бинарного дерева поиска для создания бинарного дерева, но функция LCA предназначена для любого бинарного дерева (не обязательно бинарного дерева поиска).


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

    Вспомогательное пространство: O (ч)

    AO (ч) время и O (1) дополнительное пространство Решение :
    Приведенное выше решение требует дополнительного места, потому что нам нужно использовать хеш-таблицу для хранения посещенных предков. Мы можем решить эту проблему в O (1) дополнительном пространстве, используя следующий факт: если оба узла находятся на одном уровне, и если мы переходим вверх, используя родительские указатели обоих узлов, первый общий узел в пути к корню — это lca.
    Идея состоит в том, чтобы найти глубины заданных узлов и переместить указатель более глубокого узла на разницу между глубинами. Как только оба узла достигнут одинакового уровня, пройдите их вверх и верните первый общий узел.

    Спасибо Mysterious Mind за предложенный подход.

    C ++

    // C ++ программа для поиска наименьшего общего предка, используя родительский указатель
    #include <bits/stdc++.h>

    using namespace std;

      
    // Узел дерева

    struct Node

    {

        Node *left, *right, *parent;

        int key;

    };

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

    Node *newNode(int item)

    {

        Node *temp = new Node;

        temp->key = item;

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

        return temp;

    }

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

    Node *insert(Node *node, int key)

    {

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

        if (node == NULL) return newNode(key);

      

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

        if (key < node->key)

        {

            node->left = insert(node->left, key);

            node->left->parent = node;

        }

        else if (key > node->key)

        {

            node->right = insert(node->right, key);

            node->right->parent = node;

        }

      

        / * вернуть (неизмененный) указатель узла * /

        return node;

    }

      
    // Полезная функция для определения глубины узла
    // (расстояние от корня)

    int depth(Node *node)

    {

        int d = -1;

        while (node)

        {

            ++d;

            node = node->parent;

        }

        return d;

    }

      
    // Найти LCA узлов n1 и n2 в двоичном дереве
    Node *LCA(Node *n1, Node *n2)
    {

        // Находим глубины двух узлов и различий

        int d1 = depth(n1), d2 = depth(n2);

        int diff = d1 - d2;

      

        // Если n2 глубже, поменяйте местами n1 и n2

        if (diff < 0)

        {

            Node * temp = n1;

            n1 = n2;

            n2 = temp;

            diff = -diff;

        }

      

        // Перемещаем n1 вверх, пока он не достигнет того же уровня, что и n2

        while (diff--)

            n1 = n1->parent;

      

        // Теперь n1 и n2 находятся на одинаковых уровнях

        while (n1 && n2)

        {

            if (n1 == n2)

                return n1;

            n1 = n1->parent;

            n2 = n2->parent;

        }

      

        return NULL;

    }

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

    int main(void)

    {

        Node * root = NULL;

      

        root = insert(root, 20);

        root = insert(root, 8);

        root = insert(root, 22);

        root = insert(root, 4);

        root = insert(root, 12);

        root = insert(root, 10);

        root = insert(root, 14);

      

        Node *n1 = root->left->right->left;

        Node *n2 = root->right;

      

        Node *lca = LCA(n1, n2);

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

      

        return 0;

    }

    Джава

    import java.util.HashMap;

    import java.util.Map;

      
    // Java-программа для поиска наименьшего общего предка, используя родительский указатель

      
    // Узел дерева

    class Node 

    {

        int key;

        Node left, right, parent;

      

        Node(int key) 

        {

            this.key = key;

            left = right = parent = null;

        }

    }

      

    class BinaryTree 

    {

        Node root, n1, n2, lca;

      

        / * Утилита для вставки нового узла с

           данный ключ в бинарном дереве поиска * /

        Node insert(Node node, int key) 

        {

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

            if (node == null)

                return new Node(key);

      

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

            if (key < node.key) 

            {

                node.left = insert(node.left, key);

                node.left.parent = node;

            

            else if (key > node.key) 

            {

                node.right = insert(node.right, key);

                node.right.parent = node;

            }

      

            / * вернуть (неизмененный) указатель узла * /

            return node;

        }

      

        // Полезная функция для определения глубины узла

        // (расстояние от корня)

        int depth(Node node) 

        {

            int d = -1;

            while (node != null

            {

                ++d;

                node = node.parent;

            }

            return d;

        }

      

        // Найти LCA узлов n1 и n2 в двоичном дереве

        Node LCA(Node n1, Node n2) 

        {

            // Находим глубины двух узлов и различий

            int d1 = depth(n1), d2 = depth(n2);

            int diff = d1 - d2;

      

            // Если n2 глубже, поменяйте местами n1 и n2

            if (diff < 0

            {

                Node temp = n1;

                n1 = n2;

                n2 = temp;

                diff = -diff;

            }

      

            // Перемещаем n1 вверх, пока он не достигнет того же уровня, что и n2

            while (diff-- != 0)

                n1 = n1.parent;

      

            // Теперь n1 и n2 находятся на одинаковых уровнях

            while (n1 != null && n2 != null

            {

                if (n1 == n2)

                    return n1;

                n1 = n1.parent;

                n2 = n2.parent;

            }

      

            return null;

        }

      

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

        public static void main(String[] args) 

        {

            BinaryTree tree = new BinaryTree();

            tree.root = tree.insert(tree.root, 20);

            tree.root = tree.insert(tree.root, 8);

            tree.root = tree.insert(tree.root, 22);

            tree.root = tree.insert(tree.root, 4);

            tree.root = tree.insert(tree.root, 12);

            tree.root = tree.insert(tree.root, 10);

            tree.root = tree.insert(tree.root, 14);

      

            tree.n1 = tree.root.left.right.left;

            tree.n2 = tree.root.right;

            tree.lca = tree.LCA(tree.n1, tree.n2);

      

            System.out.println("LCA of " + tree.n1.key + " and " + tree.n2.key

                    + " is " + tree.lca.key);

        }

    }

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

    C #

    // C # программа для поиска наименьшего общего
    // предок, используя родительский указатель

    using System;

      
    // Узел дерева

    public class Node

    {

        public int key;

        public Node left, right, parent;

      

        public Node(int key)

        {

            this.key = key;

            left = right = parent = null;

        }

    }

      

    class GFG

    {

    public Node root, n1, n2, lca;

      
    / * Утилита для вставки нового

     узел с данным ключом в бинарном дереве поиска * /

    public virtual Node insert(Node node, int key)

    {

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

           новый узел * /

        if (node == null)

        {

            return new Node(key);

        }

      

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

        if (key < node.key)

        {

            node.left = insert(node.left, key);

            node.left.parent = node;

        }

        else if (key > node.key)

        {

            node.right = insert(node.right, key);

            node.right.parent = node;

        }

      

        / * вернуть (неизмененный) указатель узла * /

        return node;

    }

      
    // Полезная функция для определения глубины
    // узел (расстояние от него до корня)

    public virtual int depth(Node node)

    {

        int d = -1;

        while (node != null)

        {

            ++d;

            node = node.parent;

        }

        return d;

    }

      
    // Найти LCA узлов n1 и n2
    // в двоичном дереве

    public virtual Node LCA(Node n1, Node n2)

    {

        // Находим глубины двух узлов

        // и различия

        int d1 = depth(n1), d2 = depth(n2);

        int diff = d1 - d2;

      

        // Если n2 глубже, поменяйте местами n1 и n2

        if (diff < 0)

        {

            Node temp = n1;

            n1 = n2;

            n2 = temp;

            diff = -diff;

        }

      

        // Перемещаем n1 вверх, пока не достигнем

        // тот же уровень, что и n2

        while (diff-- != 0)

        {

            n1 = n1.parent;

        }

      

        // Теперь n1 и n2 находятся на одинаковых уровнях

        while (n1 != null && n2 != null)

        {

            if (n1 == n2)

            {

                return n1;

            }

            n1 = n1.parent;

            n2 = n2.parent;

        }

      

        return null;

    }

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

    public static void Main(string[] args)

    {

        GFG tree = new GFG();

        tree.root = tree.insert(tree.root, 20);

        tree.root = tree.insert(tree.root, 8);

        tree.root = tree.insert(tree.root, 22);

        tree.root = tree.insert(tree.root, 4);

        tree.root = tree.insert(tree.root, 12);

        tree.root = tree.insert(tree.root, 10);

        tree.root = tree.insert(tree.root, 14);

      

        tree.n1 = tree.root.left.right.left;

        tree.n2 = tree.root.right;

        tree.lca = tree.LCA(tree.n1, tree.n2);

      

        Console.WriteLine("LCA of " + tree.n1.key +

                          " and " + tree.n2.key + 

                          " is " + tree.lca.key);

    }
    }

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


    Выход :

    LCA of 10 and 22 is 20 

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

    Самый низкий общий предок в бинарном дереве | Комплект 1

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

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

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

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

    Самый низкий общий предок в бинарном дереве | Набор 2 (с помощью родительского указателя)

    0.00 (0%) 0 votes