99클럽 코테 스터디 13일차 TIL Search in a Binary Search Tree

 

# 오늘의 학습 키워드 

이분탐색(이진탐색)

 

# 오늘의 문제 

https://leetcode.com/problems/search-in-a-binary-search-tree/description/

 

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

 

# 나의 풀이방식 

node의 value와 val을 비교하는 재귀함수를 작성하여 노드를 탐색한다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {


        // 탐색하려는 node가 null이라면 null을 반환
        if(root == null){
            return null;
        }

        // node의 value값이 val과 동일하면 해당 node 반환 
        if(root.val == val){
            return root;
        }


        // node의 value와 val을 비교해서 val이 node값보다 크다면 오른쪽 노드를 계속 탐색
        if(root.val < val){ 
            return searchBST(root.right,val);

        // 반대로 val이 node값보다 작다면 왼쪽 노드를 계속 탐색
        }else{
            return searchBST(root.left,val);
        }

    }
}

 

 

# 오늘의 공부 

 

* BST(Binary Search Tree) : 이분탐색(이진탐색)

 

1. BST는 왜 필요한가? 

- 탐색은 프로그램에서 가장 시간이 많이 걸리는 연산 중 하나이다. 스택, 큐, 배열, 리스트 구조는 모두 선형적인 구조로 일일이 순차적으로 접근해서 데이터를 탐색하기때문에 비효율적이다. 효율적인 탐색을 위해 등장한 것이 BST이다. 선형구조의 경우 데이터가 100개 있으면 마지막 인덱스까지 100번을 탐색해 평균 50번, 빅오표기법으로는 평균 O(N)의 시간복잡도를 갖는다. BTS의 경우 평균적으로 6~7번의 탐색을 거치며 빅오표기법으로는 평균 O(logN)의 시간복잡도를 갖는다. 

 

2. 트리 순회 방법 

- 전위순회 : 부모노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리 

- 중위순회 : 왼쪽 서브트리 -> 부모노드 -> 오른쪽 서브트리 

- 후위순회 : 왼쪽 서브트리 -> 오른쪽 서브트리 -> 부모노드