오늘의 학습 키워드
- Search in a Binary Search Tree
공부한 내용 본인의 언어로 정리하기
/**
* 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) {
// 기본 케이스: 트리가 비어있거나 찾는 값을 발견했을 때
if(root == null || root.val == val){
return root;
}
// val이 현재 노드의 값보다 작으면 왼쪽 서브트리에서 검색
if(val < root.val){
return searchBST(root.left, val);
}
// val이 현재 노드의 값보다 크면 오른쪽 서브트리에서 검색
return searchBST(root.right, val);
}
}오늘의 회고
오늘은 이분탐색을 주제로 문제나 나왔다. 문제를 풀기 전 문제에 대해서 이해하기 위해서 Binary Search Tree에 대해 먼저 조사했다.
이진 탐색 트리는 다음과 같은 특성을 가진 노드들의 집합이다.
- 각 노드는 최대 두 개의 자식 노드를 가진다 (왼쪽 자식과 오른쪽 자식)
- 왼쪽 서브트리의 모든 노드는 현재 노드의 값보다 작다.
- 오른쪽 서브트리의 모든 노드는 현재 노드의 값보다 크다.
노드의 개념과 작동 원리
노드는 데이터 구조에서 데이터를 저장하는 기본 단위이다. 각 노드는 두 가지 주요 요소를 가진다.
- 데이터: 노드가 저장하는 실제 정보
- 링크(포인터): 다른 노드를 가리키는 참조
노드는 다음과 같이 작동된다
- 데이터 저장: 각 노드는 특정 데이터를 보유합니다.
- 연결: 노드는 다른 노드와 연결되어 복잡한 데이터 구조를 형성합니다.
- 탐색: 노드 간의 연결을 따라 데이터 구조를 탐색할 수 있습니다.
이진 탐색 트리의 주요 연산
a. 노드 생성 및 삽입
TreeNode root = new TreeNode(4);
root.left = new TreeNode(2);
root.right = new TreeNode(7);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(3);b. 트리 탐색 (예: 값 검색)
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) {
return root;
}
if (val < root.val) {
return searchBST(root.left, val);
}
return searchBST(root.right, val);
}c. 트리 순회
// 중위 순회 (오름차순으로 값을 출력)
void inorderTraversal(TreeNode node) {
if (node != null) {
inorderTraversal(node.left);
System.out.print(node.val + " ");
inorderTraversal(node.right);
}
}설명을 보면서 노드에 대해서도 이해를 하지 못해서 추가로 더 조사하였다.
노드(Node)란?
노드는 데이터를 저장하는 상자라고 생각하고 이 상자 안에는 두 가지가 들어있다
값: 우리가 저장하고 싶은 정보 (예: 숫자, 이름 등)
화살표: 다른 상자를 가리키는 표시
코드는 트리 탐색을 가지고 하면 될거 같아 그대로 RUN을 돌렸는데 ACCEPT가 나왔고 어떤 상황에서 어떻게 작동을 하는지에 대해 추가로 주석을 달면서 조금이나마 이해하려고 노력했다.
AI 코드리뷰
현재 코드의 장점
- 간결하고 이해하기 쉬운 구조입니다.
- 재귀를 사용하여 트리를 효율적으로 탐색합니다.
- BST의 특성을 잘 활용하여 불필요한 탐색을 줄입니다.
현재 코드의 단점
- 재귀 호출로 인해 트리의 깊이가 매우 깊을 경우 스택 오버플로우가 발생할 수 있습니다.
- 트리가 불균형할 경우 최악의 시간 복잡도가 발생할 수 있습니다.
시간 복잡도
- 평균적인 경우: O(log n), 여기서 n은 노드의 수입니다.
- 최악의 경우 (트리가 한쪽으로 치우친 경우): O(n)
개선된 코드 제안
1번 (반복문을 사용한 버전)
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
while (root != null && root.val != val) {
root = val < root.val ? root.left : root.right;
}
return root;
}
}개선된 버전의 장점:
- 재귀를 사용하지 않아 스택 오버플로우의 위험이 없습니다.
- 약간의 성능 향상을 기대할 수 있습니다 (함수 호출 오버헤드 감소).
- 메모리 사용량이 상수입니다 (O(1)).
시간 복잡도는 여전히 동일합니다:
- 평균의 경우: O(log n)
- 최악의 경우: O(n)
2번 (균형 잡힌 BST를 가정한 버전)
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) return root;
TreeNode current = root;
while (current != null) {
if (val == current.val) return current;
if (val < current.val) {
if (current.left == null) return null;
current = current.left;
} else {
if (current.right == null) return null;
current = current.right;
}
}
return null;
}
}개선된 버전의 장점:
- 반복문을 사용하여 스택 오버플로우 위험을 제거합니다.
- 각 단계에서 자식 노드의 존재 여부를 확인하여 불필요한 반복을 줄입니다.
- 균형 잡힌 BST에서 더 효율적으로 동작할 수 있습니다.
이 버전의 시간 복잡도:
- 평균 및 최선의 경우: O(log n)
- 최악의 경우: O(n) (트리가 완전히 불균형할 때)
두 번째 개선된 버전은 BST가 어느 정도 균형을 유지하고 있다고 가정할 때 더 효율적입니다. 또한, 노드의 자식 존재 여부를 확인함으로써 불필요한 null 체크를 줄이고, 트리의 끝에 도달했을 때 빠르게 null을 반환할 수 있습니다.
내일 공부할 것 :
이진 탐색 트리와 관련된 CS 지식을 더 깊이 이해하기 위해 추가로 학습해야 할 것 같다.
기본 데이터 구조
- 배열과 리스트: 데이터를 순차적으로 저장하는 가장 기본적인 구조
- 스택과 큐: LIFO(Last In First Out)와 FIFO(First In First Out) 구조
- 링크드 리스트: 노드들이 연결된 구조 (단일, 이중 링크드 리스트)
트리 구조의 확장
- 일반 트리: 자식 노드 수에 제한이 없는 트리
- AVL 트리, 레드-블랙 트리: 자동으로 균형을 잡는 이진 탐색 트리
- B-트리: 디스크 기반의 탐색에 효율적인 트리 구조
그래프
- 방향/무방향 그래프
- 가중치 그래프
- 그래프 탐색 알고리즘 (DFS, BFS)
알고리즘 기초
- 시간 복잡도와 공간 복잡도
- 정렬 알고리즘 (버블, 선택, 삽입, 퀵, 머지 정렬 등)
- 탐색 알고리즘 (선형 탐색, 이진 탐색)
프로그래밍 패러다임
- 절차적 프로그래밍
- 객체 지향 프로그래밍 (OOP)
- 함수형 프로그래밍
문제
https://leetcode.com/problems/search-in-a-binary-search-tree/
