* 공부용의 자유로운 글씨😀
『가장 쉬운 독학 알고리즘 첫걸음 - C&자바편』 공부용이다.
이진 탐색 트리는 프로그래멋 레벨 3쯤 되면 많이 나온다.
공부용은 레벨 0 1 2를 딱콩딱콩 풀고 남의 코드를 훑고 있는 1인이다.
어쨌든 트리는 나뭇가지처럼 뻗어 나가는 구조인데,
루트
루트 자식1 루트 자식2
루자1자식3 루자2자식4 루자2자식5
이런 식으로 구성되어 있다.
자식을 보통 노드(마디)라고 하는데, 맨 위에 있는 노드가 루트이다.
루트는 뿌리를 내림에 따라 부모가 되는데, 부모노드 - 자식노드로 구분한다.
같은 부모를 갖는 노드는 형제노드라고 하고,
부모와 자식 노드 형태로 묶인 트리의 일부분은 서브 트리라고 한다.
만약에 별도 자식이 없으면 그냥 리프 노드(잎 노드)라고 한다.
이진 탐색 트리는 제일 작은 값이 왼쪽에, 제일 큰 값이 오른쪽에 연결된
트리이다!
4
2 6
1 3 5 7
이런 식으로 생겼는데, 5를 찾기 위해서는
1) 4보다 5가 크니까 >>> 로 감
2) 6보다 5가 작으니가 <<< 로 감
이런 식으로 찾는다.
이진 탐색 (바이너리 서치 트리라서 BST라고 함)
는
○ 구조체 : BST {정수형 : data, 정수형 : left, 정수형 : right}
로 의사코드를 나타낼 수 있는데,
이거는 사실 연결 리스트 비슷한 거라서 구조체 배열로 구현하면 된다.
<<<로 가는 연결 정보
>>>로 가는 연결 정보가 있다.
class BST{
public int data;
public int left;
public int right;
}
와 같은 형태로 나타낼 수 있다!
(우리 자바는 구조체가 없어서 클래스로 표현한다.)
4 - 6 - 5 - 2 - 3 - 7 - 1의 순서로 요소를 추가하는 이진 탐색 트리를 짜보려면 의사코드는 아래와 같다.
addBST랑 printPhysicalBST를 만들고, main문에서 addBST로 추가를 해버린다.
함수 외부에 tree(이진 검색 트리 본체), head에 해당하는 rootIdx, 다음에 저장할 요소의 인덱스인 newIdx를 선언한다.
현재 위치값보다 크면 >>로 가고, 작으면 <<로 가서 잘 처리한다.
맨 처음 값은 root가 된다.
이걸 잘 구현해 보면 아래와 같다.
class BST{
int data;
int left;
int right;
}
public class 이진탐색트리 {
//이진 탐색 트리 실체 배열 - 요소 수 원래 정해져 있음
public static BST[] tree = new BST[10];
public static int rootIdx = 0; //루트의 물리 위치 인덱스 = head
public static int newIdx = 0; //다음 삽입할 것 물리 위치 인덱스
public static void addBST(int data){
//요소 삽입하기
int currentIdx; //현재 요소 위치 인덱스
boolean addFlag; //요소 추가 완료 확인 플래그
tree[newIdx].data = data;
tree[newIdx].left = -1;
tree[newIdx].right = -1;
if(newIdx != rootIdx){
//루트 인덱스면 위에서 끝나고, 아니면 여기로 옴
currentIdx = rootIdx; //루트인 0부터 내려감
addFlag = false; //요소 추가 안 됨
do{
if(data <tree[currentIdx].data){
//루트보다 작으면 <<<로 감
if(tree[currentIdx].left == -1){
//끝이면
tree[currentIdx].left = newIdx;
addFlag = true; //끝냄
}else{
currentIdx = tree[currentIdx].left; //더 내려가고 루프를 돔
}
}else{
//루트보다 크면 >>>로 감
if(tree[currentIdx].right == -1){
//끝이면
tree[currentIdx].right = newIdx;
addFlag = true; //끝냄
}else{
currentIdx = tree[currentIdx].right;
}
}
}while(addFlag == false); //true 되면 끝남
}
newIdx++; //다음 추가용을 위해 인덱스를 1 늘려놓음
}
public static void printPhysicalBST(){
for(int i = 0; i< newIdx; i++){
//인덱스 개수만큼 루프
System.out.println("데이터 " + tree[i].data + " 왼쪽 : " + tree[i].left + " 오른쪽 : " + tree[i].right);
}
System.out.println("");
}
public static void main(String[] args) {
for(int i = 0; i < tree.length; i++){
tree[i] = new BST();
//이진 탐색 트리 10개 만듬
}
addBST(4);
addBST(6);
addBST(5);
addBST(2);
addBST(3);
addBST(7);
addBST(1);
printPhysicalBST();
}
}
결과값은 아래와 같이 나오는데, -1은 맨 아래 자식이라 4개가 나온다.
데이터 4 왼쪽 : -1 오른쪽 : -1
처음에는 head밖에 없어서 head의 왼/오가 다 -1이다.
데이터 4 왼쪽 : -1 오른쪽 : 1
데이터 6 왼쪽 : -1 오른쪽 : -1
tree[currentIdx].right = newIdx;
4의 오른쪽은 여기를 타고 1이 된다.(아까 +1해놓은 것)
데이터 4 왼쪽 : -1 오른쪽 : 1
데이터 6 왼쪽 : 2 오른쪽 : -1
데이터 5 왼쪽 : -1 오른쪽 : -1
5니까 4 >>> 6 <<< 이므로
6의 왼쪽을 2로 바꾸게 된다. (아까 +1 함)
데이터 4 왼쪽 : 3 오른쪽 : 1
데이터 6 왼쪽 : 2 오른쪽 : -1
데이터 5 왼쪽 : -1 오른쪽 : -1
데이터 2 왼쪽 : -1 오른쪽 : -1
위와 같은 식으로 동작한다.
데이터 4 왼쪽 : 3 오른쪽 : 1
데이터 6 왼쪽 : 2 오른쪽 : -1
데이터 5 왼쪽 : -1 오른쪽 : -1
데이터 2 왼쪽 : -1 오른쪽 : 4
데이터 3 왼쪽 : -1 오른쪽 : -1
데이터 4 왼쪽 : 3 오른쪽 : 1
데이터 6 왼쪽 : 2 오른쪽 : 5
데이터 5 왼쪽 : -1 오른쪽 : -1
데이터 2 왼쪽 : -1 오른쪽 : 4
데이터 3 왼쪽 : -1 오른쪽 : -1
데이터 7 왼쪽 : -1 오른쪽 : -1
데이터 4 왼쪽 : 3 오른쪽 : 1
데이터 6 왼쪽 : 2 오른쪽 : 5
데이터 5 왼쪽 : -1 오른쪽 : -1
데이터 2 왼쪽 : 6 오른쪽 : 4
데이터 3 왼쪽 : -1 오른쪽 : -1
데이터 7 왼쪽 : -1 오른쪽 : -1
데이터 1 왼쪽 : -1 오른쪽 : -1
데이터 4 왼쪽 : 3 오른쪽 : 1
데이터 6 왼쪽 : 2 오른쪽 : 5
데이터 5 왼쪽 : -1 오른쪽 : -1
데이터 2 왼쪽 : 6 오른쪽 : 4
데이터 3 왼쪽 : -1 오른쪽 : -1
데이터 7 왼쪽 : -1 오른쪽 : -1
데이터 1 왼쪽 : -1 오른쪽 : -1
과정을 추적해보면 위와 같다.
근데 이거는 지금 물리적 위치 순서로 이진 탐색 요소를 표시하는 것이기 때문에,
printLogicalBST 라는 함수를 추가하여 깊이 우선 탐색 방식으로 표시해보는 것을 하려 한다.
루트보다 작은값을 다 돈 뒤, 큰 값을 도는 방식으로 동작한다.
public static void printLogicalBST(int currentIdx){
//현재 요소 위치를 받아와야 한다.
if(currentIdx != -1){
System.out.println("데이터 " + tree[currentIdx].data + " 왼쪽 : " + tree[currentIdx].left + " 오른쪽 : " + tree[currentIdx].right);
printLogicalBST(tree[currentIdx].left);
printLogicalBST(tree[currentIdx].right);
}
}
이런 식으로 짜는데, (if 문 안에 안 넣어서 잠시 고민했다...) 재귀를 사용해서
<<<<노드 조회 뒤 >>>>로 간다.
그리고 searchBST(정수형 x) 함수를 만들것인데, x 값을 이진 탐색 트리에서 탐색하는 함수이다.
1) idx에 임시로 결과 -1을 설정한다.
2) currentIdx에 rootIdx를 설정한다.
3) currentIdx 가 -1이 아닌 한, 다음 처리를 반복한다.
A. tree[currentIdx].data = x 라면, idx에 currentIdx를 설정하고 반복을 종료한다.
B. tree[currentIdx]. data > x라면, currentIdx에 tree[currentidx].left 를 설정한다.
C. tree[currentIdx].data < x 라면 tree[currentidx].right를 currentidx에 설정한다.
4) idx 값을 반환한다.
위와 같은 알고리즘을 의사코드로 만들면,아래와 같다.
코드로 짜면 아래와 같다.
public static int searchBST(int x){
int idx;
int currentIdx;
idx = -1;
currentIdx = rootIdx;
while(currentIdx != -1){
if(tree[currentIdx].data == x){
idx = currentIdx;
break;
}else if(tree[currentIdx].data > x){
//크면 >>>
currentIdx = tree[currentIdx].left;
}else{
//작으면 <<<
currentIdx = tree[currentIdx].right;
}
}
return idx;
}
System.out.println("5의 물리적 위치 찾기 " + searchBST(5));
System.out.println("1의 물리적 위치 찾기 " + searchBST(1));
결과는 다음과 같이 나온다.
재귀 호출을 이용해서 x의 값을 찾을 수도 있는데, 아래와 같다.
public static int searchRecBST(int x, int currentIdx){
if(currentIdx == -1){
//끝일 경우 -1을 리턴
return -1;
}else{
if(tree[currentIdx].data == x){
return currentIdx;
}else if(tree[currentIdx].data > x){
//크면 >>>
return searchRecBST(x, tree[currentIdx].left);
}else{
//작으면 <<<
return searchRecBST(x, tree[currentIdx].right);
}
}
}
currentIdx 자체를 받아서 돌려버림.
root에서부터 찾아서 -> 돌리는 것이 아니라 함수 자체를 재귀호출해서 사용한다.
이진 트리는 코딩 테스트에 엄청 나와버려서 이상한 식으로 구현 하는 것도 많이 한다...
사실 뭔가 구현보다 이상한 문제를 이해하는 것이 더 중요한 느낌으로...
어쨌든 힙 정렬도 나와 있어서 힙과 힙 정렬 쪽도 읽어보는 쪽이 좋겠다.
public class HeapSort {
public void sort(int arr[])
{
int N = arr.length;
// 배열을 재정렬하는 힙 만들기
for (int i = N / 2 - 1; i >= 0; i--)
heapify(arr, N, i);
// 힙에서 요소를 하나씩 추출한다
for (int i = N - 1; i > 0; i--) {
// 현재 루트를 끝부분으로 이동한다
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 감소된 힙에서 최대 heapify 를 호출한다.
heapify(arr, i, 0);
}
}
// 노드 i를 기반으로 하는 하위 트리를 힙화한다.
// n은 힙의 크기이다.
void heapify(int arr[], int N, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// 왼쪽 자식이 루트보다 크면
if (l < N && arr[l] > arr[largest])
largest = l;
// 오른쪽 자식이 지금 가장 큰 것보다 크면
if (r < N && arr[r] > arr[largest])
largest = r;
// 루트가 최대값이 아닌 경우에는
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// 하위 트리를 재귀적으로 힙화한다.
heapify(arr, N, largest);
}
}
/*크기가 n인 배열을 출력하는 함수*/
static void printArray(int arr[])
{
int N = arr.length;
for (int i = 0; i < N; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// 동작코드
public static void main(String args[])
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int N = arr.length;
// Function call
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("정렬된 배열은 ");
printArray(arr);
}
}
구현은 이렇게 한다.
출처 : https://www.geeksforgeeks.org/heap-sort/
댓글
댓글 쓰기