이진 검색 트리 검색 및 삽입

난이도 쉽게
자주 묻는 질문 아마존 디보이 광신자 GE 헬스 케어 MAQ Microsoft UHG 옵텀
이진 검색 트리 이진 트리 이론 나무조회수 86

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

이진 검색 트리에서 검색 및 삽입을 수행하는 알고리즘을 작성합니다. 그래서 우리가 할 일은 입력의 일부 요소를 이진 검색 트리에 삽입하는 것입니다. 특정 요소를 검색하라는 요청을받을 때마다 BST (Binary Search Tree의 줄임말)의 요소 중에서 검색합니다.

Insert 10
Insert 15
Search 5
Insert 5
Insert 18
Search 5
Insert 12
Search 10
false
true
true

 

이진 검색 트리는 무엇입니까?

이진 검색 트리는 다음 속성을 따르는 특별한 종류의 이진 트리입니다.

  1. 현재 노드보다 작은 모든 노드가 왼쪽 하위 트리에 있습니다.
  2. 현재 노드보다 큰 모든 노드가 오른쪽 하위 트리에 있습니다.
  3. 노드의 왼쪽 및 오른쪽 하위 트리도 이진 검색 트리이며 반복되는 요소가 없습니다.

수색

암호알고리즘

이진 검색 트리는 데이터를 분류 방법 (그것으로 순회 순회 정렬 된 데이터로 이어집니다). 따라서 BST에서 검색하는 것은 매우 간단하고 쉽습니다.

루트가 대상 노드와 같은지 확인하고, 그렇다면 true를 반환하고, 그렇지 않으면 대상이 루트 값보다 작 으면 왼쪽 하위 트리에서 검색하고 그렇지 않으면 오른쪽 하위 트리에서 검색합니다.

1. Check if root equals to the target node, if yes, return true, else go to step 2.
2. If the target is smaller than the root's value, search the target in the left sub-tree.
3. Else search the target in the right sub-tree.

시간 복잡성 = O (N)

최악의 경우 전체 트리를 횡단 할 것이기 때문입니다. 최악의 경우는 나무가 기울어 져 있고 목표 값이 나무의 잎으로되어있을 수 있습니다. 그건 그렇고, 이진 검색 트리에서 검색과 삽입은 모두 동일한 시간 복잡도를 갖습니다.

공간 복잡성 = O (1)

알고리즘 동안 배열을 사용하거나 노드 값을 저장하지 않기 때문입니다. 따라서 검색은 O (1) 공간 복잡도에서 발생합니다. 공간 복잡성도 마찬가지입니다. 이진 검색 트리의 검색과 삽입은 모두 O (1) 공간 복잡성 알고리즘입니다.

삽입

BST에 새 노드를 삽입하는 것은 검색과 유사합니다. BST의 속성을 충족하여 BST에서 첫 번째 빈 위치를 검색하고 해당 위치에 새 노드를 삽입합니다.

이진 검색 트리 검색 및 삽입

암호알고리즘

1. Allocate space for new Node, let it be node.
2. If root is null, make root as node and return.
3. If the value of new node is smaller than the root's value, insert the new node in the left sub-tree.
4. Else insert the new node in the right sub-tree.

시간 복잡성 = O (N)

여기에서도 증가 또는 감소하는 순서로 요소가 제공되거나 트리가 기울어 질 수있는 경우가 있습니다. 그런 다음 삽입 할 요소가 리프가 될 것입니다. 우리는 나무 전체를 횡단해야합니다. 따라서 O (n) 시간 복잡성에 기여합니다.

공간 복잡성 = O (1)

여기에서는 각 노드에 해당하는 값을 저장하지 않았기 때문에. 우리는 일정한 공간 복잡성을 가지고 있습니다.

 

암호

이진 검색 트리에서 검색 및 삽입을위한 JAVA 코드

class BSTSearchAndInsert {
    // class to represent node of a binary tree
    static class Node {
        int data;
        Node left, right;

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

    private static Node insertToBST(Node root, Node node) {
        // if root is null, then make root as node and return
        if (root == null) {
            root = node;
            return root;
        }

        // if node's value is less than root, insert it to left subtree
        if (node.data < root.data) {
            root.left = insertToBST(root.left, node);
        }
        // else insert it to right subtree
        else {
            root.right = insertToBST(root.right, node);
        }

        // return the updated root
        return root;
    }

    private static Node insert(Node root, int value) {
        // allocate memory for new node
        Node node = new Node(value);

        // insert the new node to tree
        return insertToBST(root, node);
    }

    private static boolean search(Node root, int val) {
        // if root is null, return false
        if (root == null) {
            return false;
        }

        // if root is equals to target, return true
        if (root.data == val) {
            return true;
        }
        // else if val is less than root, search in left subtree
        else if (val < root.data) {
            return search(root.left, val);
        }
        // else search in right subtree
        else {
            return search(root.right, val);
        }
    }

    public static void main(String[] args) {
        // Example
        Node root = null;
        root = insert(root, 10);
        root = insert(root, 15);
        System.out.println(search(root, 5));
        root = insert(root, 5);
        root = insert(root, 18);
        System.out.println(search(root, 5));
        root = insert(root, 12);
        System.out.println(search(root, 10));
    }
}
false
true
true

이진 검색 트리에서 검색 및 삽입을위한 C ++ 코드

#include <bits/stdc++.h> 
using namespace std; 

// class representing node of a binary tree 
class Node { 
    public: 
    int data; 
    Node *left; 
    Node *right; 
    
    Node(int d) { 
        data = d; 
        left = right = NULL; 
    } 
};

Node* insertToBST(Node *root, Node *node) {
    // if root is null, then make root as node and return
    if (root == NULL) {
        root = node;
        return root;
    }
    
    // if node's value is less than root, insert it to left subtree
    if (node->data < root->data) {
        root->left = insertToBST(root->left, node);
    }
    // else insert it to right subtree
    else {
        root->right = insertToBST(root->right, node);
    }
    
    // return the updated root
    return root;
}

Node* insert(Node *root, int value) {
    // allocate memory for new node
    Node *node = new Node(value);
    
    // insert the new node to tree
    return insertToBST(root, node);
}

bool search(Node *root, int value) {
    // if root is null, return false
    if (root == NULL) {
        return false;
    }
    
    // if root is equals to target, return true
    if (root->data == value) {
        return true;
    }
    // else if val is less than root, search in left subtree
    else if (value < root->data) {
        return search(root->left, value);
    }
    // else search in right subtree
    else {
        return search(root->right, value);
    }
}

int main() {
    // Example
    Node *root = NULL;
    root = insert(root, 10);
    root = insert(root, 15);
    if (search(root, 5)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    root = insert(root, 5);
    root = insert(root, 18);
    if (search(root, 5)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    root = insert(root, 12);
    if (search(root, 10)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
false
true
true
균열 시스템 설계 인터뷰
Translate »