BinarySearchTree ⇒ 이진검색트리
안녕하세요! 오랜만에 자료구조에 대해서 글을 정리하는거 같습니다!
요즘 스프링, 스프링부트, MySQL을 공부하게 되면서 너무 자료구조랑 알고리즘에 소홀했던거 같아서,
주말에 시간이 좀 남아서 바로 정리를 해보고자 합니다!
이진검색트리?
이진검색트리는 말그대로,
트리형태의 자료구조인데 이진검색 방식을 활용하는것을 말합니다.
기본적으로 이진검색트리는 데이터가 들어가는 시점부터 정렬이 되어 들어가는 형태로
트리에 데이터를 넣고 따로 정렬을 해줄 필요가 없습니다!
또한 이진검색을 활용하기에 트리구조에서 필요한 데이터를 찾을때 걸리는 시간복잡도는 0(logN) 입니다!
한마디로 검색방식에 있어서 매우 효율적인 자료 구조라는 뜻이죠 🙂
이진검색트리의 특징
- 루트노드의 왼쪽 서브 트리에는 해당 노드의 데이터보다 작은 데이터를 가지 노드들로만 이루어져 있다.
- 루트노드의 오른쪽 서브 트리에는 해당 노드의 데이터보다 큰 데이터를 가지 노드들로만 이루어져 있다.
- 좌우 서브 트리도 모두 이진 탐색 트리여야 한다.
- 이진 탐색 트리는 기존 이진트리보다 탐색이 빠르다. 이진 탐색 트리의 탐색 연산은 트리의 높이(height)가 h라면 O(h)의 시간 복잡도를 갖습니다.
- 이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됐습니다.
완성 코드:
package tree;
class Tree{
class Node{
int data;
Node left;
Node right;
Node (int data){
this.data = data;
}
}
Node root;
public void makeTree(int[] a) {
root = makeTreeR(a, 0, a.length -1);
}
public Node makeTreeR(int[] a, int start, int end) {
if(start > end) return null;
int mid = (start+end)/2;
Node node = new Node(a[mid]);
node.left = makeTreeR(a, start, mid-1);
node.right = makeTreeR(a, mid+1, end);
return node;
}
public void searchBTree(Node n, int find) {
if (find<n.data) {
System.out.println("Data is smaller than"+n.data);
searchBTree(n.left, find);
}else if(find>n.data) {
System.out.println("Data is bigger than"+n.data);
searchBTree(n.right, find);
}else {
System.out.println("Data Found!");
}
}
}
public class BinarySearchTree {
public static void main (String[] args) {
int[] a = new int[10];
for(int i=0; i< a.length; i++) {
a[i]=i;
}
Tree t = new Tree();
t.makeTree(a);
t.searchBTree(t.root, 2);
}
}
여기서 이제 차근차근 어떻게 구현을 했는지 코드를 나눠서 보도록 하겠습니다!
1. Tree클래스 생성, Node클래스 생성
class Tree{
class Node{
int data;
Node left;
Node right;
Node (int data){
this.data = data;
}
}
Node root;
일단은 자료구조를 만들기 위한 기본틀을 먼저 만듭니다.
트리형의 자료구조를 만들거니 tree클래스를 선언하고 그안에는 Node클래스를 선언합니다.
Node클래스는 실제 데이터를 담을 변수, 노드를 기준으로 왼쪽, 오른쪽에 존재하는 데이터(노드), 실제 데이터는 생성자를 선언하여 받아옵니다!
또한 root값이 될 Node도 선언을 해줍니다.
2. 입력받은 배열안에 있는 데이터를 이진검색트리로 변환해주는 메소드 선언 및 재귀호출 구현
public void makeTree(int[] a) {
root = makeTreeR(a, 0, a.length -1);
}
public Node makeTreeR(int[] a, int start, int end) {
if(start > end) return null;
int mid = (start+end)/2;
Node node = new Node(a[mid]);
node.left = makeTreeR(a, start, mid-1);
node.right = makeTreeR(a, mid+1, end);
return node;
}
순서가 헷갈리지 않게 먼저 makeTreeR메소드를 먼저 보겠습니다.
매개변수로 배열, 배열의 시작 인덱싱, 배열의 끝 인덱싱 넘버를 받고 있습니다.
만약에 시작지점과 끝 지점이 엇갈리게 되면 루트를 기준으로 왼쪽과 오른쪽에 있는 모든 데이터를 순환했다는
의미임으로 더이상 재귀호출을 반복하지 않고, 자신을 호출한곳으로 그동안의 결과값을 가지고 돌아갑니다.
“재귀호출을 사용할때는 언제 호출을 끝낼것인지를 명확하게 구분해줘야 합니다. 아니면 도르마무에 빠질지도???…”
제일 먼저 root값이 될 노드를 생성합니다. 그 기준은 배열의 중간에 위치해있는 값을 기준으로 잡습니다!
그래서 일단은 중간값이 있는 인덱싱을 mid로 선언하여 매개변수로 받은 start+end/2 로 구해서 값을 담아줍니다.
그렇게 루트가 될 노드를 생성하고 그 노드를 기준으로 왼쪽노드에는 루트값보다 작은 값들이 재귀호출을 반복하여 알맞게 들어가게 됩니다.
루트노드 기준 오른쪽에 해당되는 데이터들도 똑같은 방식으로 재귀호출을 사용하여 계속해서 들어가게 됩니다.
그렇게 생성된 노드들을 return을 합니다.
3. 생성된 이진검색트리가 잘 작동하는지 확인하기 위해 검색메소드를 만듭니다.
public void searchBTree(Node n, int find) {
if (find<n.data) {
System.out.println("Data is smaller than"+n.data);
searchBTree(n.left, find);
}else if(find>n.data) {
System.out.println("Data is bigger than"+n.data);
searchBTree(n.right, find);
}else {
System.out.println("Data Found!");
}
}
매개변수로 노드객체와 찾고자 하는 데이터값을 입력을 받습니다.
만약에 찾고자 하는 값이 입력한 노드의 데이터보다 작다면, 노드의 왼쪽으로 이동하게 되고 (검색범위가 반절로 줄어든다) 재귀호출을 사용해 (노드의 왼쪽값, 찾고자하는값 매개변수로 전달)
find==n.data가 일치할때까지 재귀호출을 반복하게 됩니다.
위에 식에서는 루트노드의 데이터가 찾고자 하는값보다 작으면 왼쪽 노드로, 크다면 오른쪽
둘다 아니라면 데이터가 일치하는 소리이기 때문에 데이터를 찾았다고 콘솔에 찍어줍니다.
4. 테스트
public class BinarySearchTree {
public static void main (String[] args) {
int[] a = new int[10];
for(int i=0; i< a.length; i++) {
a[i]=i;
}
Tree t = new Tree();
t.makeTree(a);
t.searchBTree(t.root, 2);
}
}
일단 이진검색트리를 만들기 위한 준비물이 필요하죠?
데이터가 담긴 배열을 준비합니다. 이때 조심해야 될거는 만약에 배열이 정렬이 안되있는 상태라면
해당 배열의 중간인덱싱에 해당되는 데이터는 전체 데이터의 중앙에 위치하지 않기 때문에,
경우의 수가 최악이면 선택한 데이터가 배열에서 제일 작은 데이터일수 있습니다.
그렇게 되면 재가 만든 이진검색트리 구조 구현 방식은 그냥 이진트리를 만들게 되기 떄문에,
시간복잡도가 0(N) 이 나오게 됩니다!………….그래서 꼭 정렬이 된 상태의 배열로 테스트를 해야합니다😟 ⇒ 이진검색트리의 특징중 하나이죠?
0~9까지 정수가 담긴 배열을 선언하고, 위에서 만든 Tree클래스의 객체를 생성해 메소드를 호출하고 테스트해봅니다!
저희가 만든 배열은 0~9 즉 가운데값인 4를 기준으로 루트를 세우고 트리구조를 그려보면
4 1 70 2 5 8 3 6 9형태를 가지게 되죠? 찾고자 하는 값은 2였습니다!
그렇다면 4를 기준으로 작기 때문에 1로 이동을 하게되고,
1보다는 크기 때문에 1를 기준으로 오른쪽으로 이동하게 됩니다.
그랬더니 2가 나왔죠? Data Found를 출력하게 됩니다!!!
오늘은 배열을 담으면 이진트리로 만들어주는 구조를 구현해봤는데요!
다음번에는 이렇게 만들어진 이진검색트리에서 데이터 삭제와, 수정, 삽입을 구현해보도록 하겠습니다 🙂
'Data Structure' 카테고리의 다른 글
| Tree 구조 순회방식 구현해보기 (0) | 2023.01.13 |
|---|---|
| Tree 구조는 뭘까요…🥲 (0) | 2023.01.13 |
| Stack, Queue - Data Structure. (0) | 2023.01.13 |
| 빠르고 좋다는 Quick 정렬 원리와 구현 (2) | 2023.01.13 |
