이진 검색 트리 (BST : Binary Search Tree)
- 최대 두 개의 자식을 가지는 구조
- 노드의 왼쪽 자식의 값이 반드시 자신의 값 이하이며, 오른쪽 자식의 값은 반드시 자신의 값 이상이다.
- 이진 검색 트리의 장점 가운데 하나로 룩업 연산(트리에 있는 특정 노드의 위치를 알아내는 연산)을 빠르고 간단하게 처리할 수 있다.
- ⛔️ 순차 탐색보다 조금 더 효율적이지만, 미리 정렬이 되어있어야 한다.
- 순차 탐색은 O(n)의 복잡도를 가지는 반면 이진 탐색은 O(log n)이다.
코드 흐름
0,1,2,3,4,5,6,7,8
1. 중간 값 4가 root가 된다. 만약 짝수 개인 경우 더 작은 숫자를 root로 설정한다.
2. 앞 뒤로 0,1,2,3 / 5,6,7,8에서 중간 값 1, 7을 4의 자식 노드로 추가해준다.
[중간 결과]
4
1 7
3. 각 부모의 숫자보다 클 경우 우측에, 작을 경우 좌측에 넣어준다. (반복)
[중간 결과]
4
1 7
0 2 5 8
3 6 9
코드
package study;
class Tree {
Node root; //트리가 시작하는 루트 노트 / 최상위 노드를 기본으로 가르키고 있음
//트리를 만드는 일을 시작해주는 함수
//재귀함수를 시작하기 앞서 필요한 변수를 던져주는 역할은 한다. (처음 시작시킴)
public void makeTree(int[] a) {
//처음부터 마지막 index를 알려준다.
this.root = makeTreeR(a, 0, a.length - 1);
}
//반쪼개고 중간 값을 찾는 작업
public Node makeTreeR(int[] a, int start, int last) {
//재귀함수를 종료 시킬 조건
if (start > last) return null;
//형변환으로 소수점부분은 제외하고 자동으로 정수부분만 들어감 - https://jhnyang.tistory.com/207
//int mid = (int) Math.floor((start + last) / 2);
int mid = (last + start) / 2;
//중간 지점에 저장된 값으로 node를 생성한다.
//다른 클래스의 객세 생성에는 new를 통해야 한다.
Node node = new Node(a[mid]);
node.left = makeTreeR(a, start, mid - 1);
node.right = makeTreeR(a, mid + 1, last);
//최상위 root노드임 (=최초 재귀함수가 실행될때 생성된 값)
return node;
}
//n 검색을 할 시작 노드, find 찾을 인자
public void searchBTree(Node n, int find) {
//찾아야 하는 값이 현재 노드의 값보다 작은지를 비교하고
if (find < n.data) {
System.out.println("small data! " + n.data);
//왼쪽 (더 작은 값)을 검색해야함
searchBTree(n.left, find);
} else if (find > n.data) {
System.out.println("big data! " + n.data);
//오른쪽 (더 큰 값)을 검색해야함
searchBTree(n.right, find);
} else { //같을 때
System.out.println("same data! " + n.data);
}
}
class Node {
int data;
Node left; //왼쪽 오른쪽 값을 저장할 노드 값
Node right;
//생성자에서 데이터를 받아 node data에 저장한다.
Node(int data) {
this.data = data;
}
}
}
public class TreeTest {
public static void main(String[] args) {
int[] a = new int[10];
for (int i = 0; i < a.length; i++) {
a[i] = i;
}
Tree tree = new Tree();
tree.makeTree(a);
//0~9까지의 숫자를 트리로 두었을때 5는 찾아보자
tree.searchBTree(tree.root, 5);
/*
(4)
/ \
/ \
/ \
(1) (7)
/ \ / \
(0) (2) (5) (8)
\ \ \
(3) (6) (9)
*/
}
}출력 값
big data! 4
small data! 7
same data! 5
코드 작동 과정
제귀함수로 작동 과정을 확인하기 위해 한 줄씩 확인했다. 두 번째 적은 건데도 깔끔하지 못해서 아쉽다..ㅎ
확실히 코드는 한 줄씩 손으로 써가면서 해야 이해가 쉬운 것 같다.
3,1,2 이렇게 절반만 작동한 과정이다.
학습처, 코드 출처
728x90
반응형