이진 검색 트리 Leetcode 솔루션에 삽입


난이도 중급
자주 묻는 질문 아마존 Apple 골드 피처 페이스북 서비스 구글 Microsoft
이진 검색 트리

이 문제에서 우리는 이진 검색 트리 이진 검색 트리에 추가하고 구조를 반환해야하는 노드의 정수 값과 정수 값을 포함합니다. 요소를 BST에 삽입 한 후 Inorder Traversal을 인쇄해야합니다.

Binary Search Tree:
 
    7
 
  /     \

3         10

        /

      8
Integer Value = 11
3 7 8 10 11
Binary Search Tree:
           5

         /

       4

     /

   3
Integer Value = 2
2 3 4 5

설명

이진 검색 트리 Leetcode 솔루션에 삽입

이진 검색 트리 Leetcode 솔루션에 삽입

접근하다(재귀)

이진 검색 트리에서 주어진 노드를 어디에 삽입해야하는지 결정하려면 루트에서 왼쪽 / 오른쪽 자식이 주어진 노드가 될 해당 노드로의 경로를 설정해야합니다.

우리는 문제에서 하위 문제로 작업을 전달함으로써 재귀 적으로 해결할 수 있습니다. 이 경우 새 노드를 트리에 삽입한다는 것은 왼쪽 하위 트리 또는 오른쪽 하위 트리에 새 노드를 삽입하는 것을 의미합니다. 동일한 아이디어가 다른 하위 트리에도 적용됩니다. 기본 케이스를 설정해야합니다. 하위 트리의 루트 노드가있는 지점에 도달하면 NULL, 대상 노드를 삽입 할 경로의 끝에 도달했음을 의미합니다. 그래서 우리는 새로운 주어진 값으로 노드 값을 갖는 노드 주소. 이진 검색 트리는 임의의 요소를 검색하는 데 상당한 이점이 있습니다. O (logN) 평균 사례에서 시간. 따라서이 경우 효율적인 시간에 삽입 할 새 노드의 위치를 ​​찾습니다.

암호알고리즘

  1. 함수 만들기 insertIntoBST () 의 주소를 반환합니다 뿌리 삽입 후 BST의 주어진 노드
  2. insertIntoBST () 두 개의 매개 변수가 있습니다. 뿌리 나무의 가치 삽입 할 노드의
  3. 이 기능은 다음을 수행합니다.
    • If 뿌리 is Null 주어진 값과 동일한 값을 가진 새 트리 노드를 반환합니다.
    • 주어진 값이 가치보다 뿌리 노드, 그런 다음 오른쪽 하위 트리에 동일한 문제를 호출 한 다음 루트를 반환합니다.
      • root.right = insertIntoBST (root-> right, 값)
      • 반환 뿌리
    • 그렇지 않으면 왼쪽 하위 트리에서 다음과 같이 검색합니다.
      • root.left= insertIntoBST (root.left, 값)
      • 반환 뿌리
  4. 이진 검색 트리의 순회 순회 인쇄

이진 검색 트리 Leetcode 솔루션에 삽입 구현

C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

void inorderTraversal(BSTNode* root)
{
    if(root == NULL)
        return;
    inorderTraversal(root->left);
    cout << root->value << " ";
    inorderTraversal(root->right);
    return;
}


BSTNode* insertIntoBST(BSTNode* root , int val)
{
    if(root == NULL)
        return new BSTNode(val);
    if(val > root->value)
    {
        root->right = insertIntoBST(root->right , val);
        return root;
    }
    root->left = insertIntoBST(root->left , val);
    return root;
}

int main()
{
    BSTNode* root = new BSTNode(7);
    root->left = new BSTNode(3);
    root->right = new BSTNode(10);
    root->right->left = new BSTNode(8);
    int val = 11;
    root = insertIntoBST(root , val);
    inorderTraversal(root);
    return 0;
}

자바 프로그램

class BSTNode
{
    int value;
    BSTNode left , right;

    BSTNode(int val)
    {
        value = val;
        left = right = null;
    }
}

class insert_into_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(7);
        root.left = new BSTNode(3);
        root.right = new BSTNode(10);
        root.right.left = new BSTNode(8);
        int val = 11;
        root = insertIntoBST(root , val);
        inorderTraversal(root);
    }

    static BSTNode insertIntoBST(BSTNode root , int val)
    {
        if(root == null)
            return new BSTNode(val);
        if(val > root.value)
        {
            root.right = insertIntoBST(root.right , val);
            return root;
        }
        root.left = insertIntoBST(root.left , val);
        return root;
    }

    static void inorderTraversal(BSTNode root)
    {
        if(root == null)
            return;
        inorderTraversal(root.left);
        System.out.print(root.value + " ");
        inorderTraversal(root.right);
        return;
    }
}

3 7 8 10 11

이진 검색 트리 Leetcode 솔루션에 삽입의 복잡성 분석

시간 복잡성

오) = BST 높이 = logN (여기서 N = BST의 노드 수) 평균적인 경우 (logN 재귀 호출을 수행 할 때). 그러나 의 위에) 최악의 경우 나무가 비뚤어진 경우입니다. 나무가 비뚤어진 경우 검색이 선의 하나.

공간 복잡성

오) 평균적인 경우. 의 위에) 최악의 경우. Space Complexity의 경우는 우리가 만드는 재귀 호출의 수에 따라 다르기 때문에 여기서 Time Complexity와 동일합니다.

접근하다(반복적 인)

공간 복잡성을 개선하기 위해 위의 접근 방식을 반복적으로 따를 수 있습니다. 재귀는 메모리를 소비하는 스택 프레임을 사용합니다. 따라서 반복적 인 솔루션에서 재귀 호출로드 왼쪽 또는 오른쪽 중 하나가있는 노드를 공격 할 때까지 검색 경로의 트리 아래로 이동합니다. NULL. 우리가 가질 때 root.left / root.right = NULL, 이 노드를 주어진 값과 동일한 값을 가진 새 노드와 동일하게 설정합니다. 값을 비교하여 경로를 결정합니다. 뿌리 모든 재귀 호출의 값.

암호알고리즘

  1. 우리는 다시 insertIntoBST () 위와 같은 목적으로
  2. 경우 뿌리 NULL
    1. 주어진 값과 동일한 값으로 새 노드를 반환
  3. 루트 사본을 만듭니다. 더미 BST의 내용을 조작하기 위해
  4. DaVinci에는 더미 is 지원 NULL
    1. 주어진 값이 다음보다 큰 경우 root.val
      1. If root.right NULL
        1. root.right = 주어진 값을 가진 새 노드
        2. 반환 뿌리
      2. 그렇지 않으면 설정
        1. 뿌리 = root.right, 오른쪽 하위 트리로 이동
    2. Else 값이 다음보다 작거나 같으면 root.val
      1. root.left가 NULL 인 경우
        1. root.left = 주어진 값을 가진 새 노드
        2. 반환 뿌리
      2. 그렇지 않으면 설정
        1. 뿌리 = root.left, 왼쪽 하위 트리로 이동
  5. BST의 Inorder 순회 인쇄

이진 검색 트리 Leetcode 솔루션에 삽입 구현

C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

void inorderTraversal(BSTNode* root)
{
    if(root == NULL)
        return;
    inorderTraversal(root->left);
    cout << root->value << " ";
    inorderTraversal(root->right);
    return;
}

BSTNode* insertIntoBST(BSTNode* root , int val)
{
    if(root == NULL)
        return new BSTNode(val);
    BSTNode* dummy = root;
    while(dummy != NULL)
    {
        if(val > dummy->value)
        {
            if(dummy->right == NULL)
            {
                dummy->right = new BSTNode(val);
                return root;
            }
            else
                dummy = dummy->right;
        }
        else
        {
            if(dummy->left == NULL)
            {
                dummy->left = new BSTNode(val);
                return root;
            }
            else
                dummy = dummy->left;
        }
    }
    return root;
}

int main()
{
    BSTNode* root = new BSTNode(7);
    root->left = new BSTNode(3);
    root->right = new BSTNode(10);
    root->right->left = new BSTNode(8);
    int val = 11;
    root = insertIntoBST(root , val);
    inorderTraversal(root);
    return 0;
}

자바 프로그램

class BSTNode
{
    int value;
    BSTNode left , right;

    BSTNode(int val)
    {
        value = val;
        left = right = null;
    }
}

class insert_into_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(7);
        root.left = new BSTNode(3);
        root.right = new BSTNode(10);
        root.right.left = new BSTNode(8);
        int val = 11;
        root = insertIntoBST(root , val);
        inorderTraversal(root);
    }

    static BSTNode insertIntoBST(BSTNode root , int val)
    {
        if(root == null)
            return new BSTNode(val);
        BSTNode dummy = root;
        while(dummy != null)
        {
            if(val > dummy.value)
            {
                if(dummy.right == null)
                {
                    dummy.right = new BSTNode(val);
                    return root;
                }
                else
                    dummy = dummy.right;
            }
            else
            {
                if(dummy.left == null)
                {
                    dummy.left = new BSTNode(val);
                    return root;
                }
                else
                    dummy = dummy.left;
            }
        }
        return root;
    }

    static void inorderTraversal(BSTNode root)
    {
        if(root == null)
            return;
        inorderTraversal(root.left);
        System.out.print(root.value + " ");
        inorderTraversal(root.right);
        return;
    }
}

3 7 8 10 11

이진 검색 트리 Leetcode 솔루션에 삽입의 복잡성 분석

시간 복잡성

오) = BST 높이 = logN (여기서 N = BST의 노드 수) 평균적인 경우. 그러나 의 위에) 최악의 경우 나무가 비뚤어진 경우입니다. 다시 말하지만, 시간 복잡성은 주어진 노드가 삽입되어야하는 대상에 도달하기 위해 수행하는 반복 횟수에 따라 달라지며 트리 구조에 따라 다릅니다.

공간 복잡성

O (1). 최악의 경우에도 변수에 상수 공간 만 사용합니다.