이진 검색 트리에서 가장 낮은 공통 조상

난이도 쉽게
자주 묻는 질문 아마존 Facebook 링크드 인 신탁
이진 검색 트리 이진 트리 순회 나무 트리 순회조회수 23

이진 검색의 루트가 주어지면 나무 두 개의 노드 n1과 n2는 주어진 이진 검색 트리에서 노드의 LCA (Lowest Common Ancestor)를 찾습니다.

이진 검색 트리에서 가장 낮은 공통 조상

이진 검색 트리에서 가장 낮은 공통 조상을위한 순진한 접근 방식

LCA를 찾는 최적의 방법을 사용하여 LCA (n1, n2)를 찾습니다. 이진 트리, BST는 이진 트리이기도합니다.

LCA를 찾아야하는 n1과 n2가 트리에 존재한다고 가정하면 위의 문제를 한 번의 순회로 해결할 수 있습니다.

트리를 가로 지르면 모든 노드에 대해 네 가지 경우 중 하나가 있습니다.

  1. 현재 노드는 n1 또는 n2입니다.이 경우 노드를 반환합니다.
  2. 현재 노드의 하위 트리 중 하나는 n1을 포함하고 다른 하나는 n2를 포함합니다.이 노드는 LCA이며 노드를 반환합니다.
  3. 현재 노드의 한 하위 트리에는 n1과 n2가 모두 포함되어 있으며 하위 트리가 반환하는 것을 반환합니다.
  4. n1 및 n2를 포함하는 하위 트리가 없습니다. null을 반환합니다.

시간 복잡성 = O (n), 단일 순회 포함 
여기서 n은 트리의 노드 수입니다.

이진 검색 트리에서 가장 낮은 공통 조상을위한 최적의 접근 방식

BST의 속성을 사용하여 LCA는 훨씬 더 적은 시간 복잡성으로 찾을 수 있습니다.

  1. 루트에서 시작하여 BST를 횡단합니다 (커서를 루트로 초기화).
  2. 현재 노드의 값이 n1과 n2 (둘 다 포함) 사이에 있으면 이것이 LCA입니다.
  3. 그렇지 않으면 노드의 값이 n1과 n2보다 작 으면 LCA가 오른쪽 절반에 표시됩니다 (curr은 curr.right가 됨).
  4. 그렇지 않으면 LCA가 왼쪽 절반에 있습니다 (통화는 curr.left가 됨).

설명

위 이미지의 BST를 고려하여 LCA (32, 40)를 찾으십시오.

루트에서 시작하여 트리 횡단을 시작하십시오.

  • 현재 노드의 값 = 20
    20 <32 및 20 <40, LCA는 오른쪽 하위 트리에 있습니다.
  • 현재 노드의 값 = 24
    24 <32 및 20 <40, LCA는 오른쪽 서브 트레에 존재합니다.
  • 현재 노드의 값 = 35
    35> = 32 및 35 <= 40, 이것이 LCA입니다.
    즉, LCA (32, 40) = 35

이진 검색 트리에서 가장 낮은 공통 조상을위한 JAVA 코드

public class LCABST {
    // Class to represent a node in BST
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
            left = right = null;
        }
    }

    // Function to return LCA of two nodes, and return -1 if LCA does not exist
    private static int LCA(Node root, int n1, int n2) {
        // No LCA for an empty tree
        if (root == null) {
            return -1;
        }

        // Traverse the tree starting from root
        Node curr = root;
        int lca = -1;
        while (curr != null) {
            if (curr.data < n1 && curr.data < n2) {
                // LCA is present in the right sub tree
                curr = curr.right;
            } else if (curr.data > n1 && curr.data > n2) {
                // LCA is present in left sub tree
                curr = curr.left;
            } else {
                lca = curr.data;
                break;
            }
        }

        // Return LCA
        return lca;
    }

    public static void main(String[] args) {
        // Constructing the BST in above example
        Node root = new Node(20);
        root.left = new Node(11);
        root.right = new Node(24);
        root.right.left = new Node(21);
        root.right.right = new Node(35);
        root.right.right.left = new Node(32);
        root.right.right.right = new Node(40);

        // Queries
        System.out.println(LCA(root, 24, 40));
        System.out.println(LCA(root, 11, 21));
        System.out.println(LCA(root, 32, 40));
    }
}

이진 검색 트리에서 가장 낮은 공통 조상을위한 C ++ 코드

#include <iostream>
using namespace std;

// Class representing node of binary search tree
class Node {
    public:
    int data;
    Node *left;
    Node *right;
};

// Function to allocate new memory to a tree node
Node* newNode(int data) { 
    Node *node = new Node(); 
    node->data = data; 
    node->left = NULL; 
    node->right = NULL;
  
    return (node); 
}

// Function to return LCA of two nodes, and return -1 if LCA does not exist
int LCA(Node *root, int n1, int n2) {
    // No LCA for an empty tree
    if (root == NULL) {
        return -1;
    }
    
    // Traverse the tree starting from root
    Node *curr = root;
    int lca = -1;
    while (curr != NULL) {
        if (curr->data < n1 && curr->data < n2) {
            // LCA is present in the right sub tree
            curr = curr->right;
        } else if (curr->data > n1 && curr->data > n2) {
            // LCA is present in left sub tree
            curr = curr->left;
        } else {
            lca = curr->data;
            break;
        }
    }
    
    // Return LCA
    return lca;
}

int main() {
  // Construct the tree shown in above example
    Node *root = newNode(20);
    root->left = newNode(11);
    root->right = newNode(24);
    root->right->left = newNode(21);
    root->right->right = newNode(35);
    root->right->right->left = newNode(32);
    root->right->right->right = newNode(40);
    
    // Queries
    cout<<LCA(root, 24, 40)<<endl;
    cout<<LCA(root, 11, 21)<<endl;
    cout<<LCA(root, 32, 40)<<endl;
    
    return 0;
}
24
20
35

복잡성 분석

시간 복잡성 = 오), 여기서 h는 BST의 높이입니다.

참조

Translate »