기본 콘텐츠로 건너뛰기

개발 공부 - 이진 탐색 트리의 추가와 탐색 (Java 힙 정렬)

* 공부용의 자유로운 글씨😀
『가장 쉬운 독학 알고리즘 첫걸음 - 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/




댓글

이 블로그의 인기 게시물

Ebook - 전자책 drm 상관 없이 pdf로 만들기

yes24와 교보문고에서 ebook을 구매 해야 했는데 너무 불편하고, 필기가 매우 화날 정도로 안 좋아서 원시적으로 사용하기로 했다. 1. 목적 : ebook에서 필기 및 사용이 불편하여 pdf로 변환  2. 용도 : 개인 사용 목적이며 화질이 다소 저하되어도 필기만 용이하면 상관 없음 3. 방법 1) 휴대폰 및 카메라로 동영상을 촬영했다. DRM 때문에 프로그램으로는 촬영이 안 되는 것을 확인했다. (사실 개인 사용 목적이면 기본 화면 캡쳐를 사용해도 된다...) 2) 마우스 클릭 해주는 매크로를 사용했다. (1) key_macro.exe > https://blog.daum.net/pg365/250 듀얼 모니터에서 위치 이탈 현상이 있긴 해도 괜찮았다. (2) AutoClick.exe > http://bestsoftwarecenter.blogspot.com/2011/02/autoclick-22.html 이 걸로 잘 사용했다. 3초마다 한 번 클릭하도록 사용했다. 3) 동영상을 이미지로 변경해주는 프로그램을 사용했다. Free Video to JPG Converter > https://www.dvdvideosoft.com/products/dvd/Free-Video-to-JPG-Converter.htm (240826: 다운로드 시 정상적으로 되지 않아서 URL 수정) 일 하면서 듀얼 모니터에 켜 놨는데 속도가 괜찮았다. * Every frame 으로 사용해야 한다. 4) 중복 사진 제거해주는 프로그램을 사용했다. VlsiPics  > http://www.visipics.info/index.php?title=Main_Page 생각보다 느리니 퇴근시에 걸어놓고 가면 된다. 한번 play가 끝나면 Auto-select 하고 Delete 하면 된다. 5) 이미지를 일괄 Crop 작업 해주는 프로그램을 사용했다. JPEGCrops > https://jpegcrops.softonic.kr/ * https://joker1209.tistory.co

개발 공부 - json JSONObject 사용 시 백슬래시(\), 원화 표시(\) 제거 및 치환

import org.json.simple.JSONObject; String dataString = new String(authData.toJSONString()); dataString = dataString.replaceAll("\\\\", ""); String 으로 안 바뀌는 가 싶어서 String 으로 변환 해 주고 작업 하였다. 사실 toJSONString 해도 정상 동작 해야 하는데 이유를 잘 모르겠음. 그리고 나서 다시 이클립스 구동 하니 toString 도 먹은 걸로 봐서 이상하다고 생각! String dataString = authData.toString(); dataString = dataString.replaceAll("\\\\", ""); 어쨌든 백 슬래시 제거를 해줘야 하는데 \\ 도 아니고 \\\\를 해야 변환이 가능했다는 결말이었습니다. 참고 : https://stackoverflow.com/questions/15450519/why-does-string-replace-not-work/15450539 test =test.replace("KP", "");  replace 후에 담아 주지 않으면 적용이 안 됩니다!

개발 공부 - OracleXETNSListener 서비스가 로컬 컴퓨터에서 시작했다가 중지되었습니다.

여러 가지 요인이 있지만 PC 이름 변경시 OracleXETNSListener 서비스 시작이 불가능합니다. 고치는 법은 C:\oraclexe\app\oracle\product\11.2.0\server\network\ADMIN 와 같은 설치 경로에서 listener.ora와 tnsnames.ora 의 pc명을 바꾼 PC명으로 바꿔주면 됩니다. 그래도 안 된다면 cmd 창에서 services.msc 를 입력 후 OracleXETNSListener 서비스를 시작 시키면 됩니다. 오류명: OracleXETNSListener 서비스가 로컬 컴퓨터에서 시작했다가 중지되었습니다. 일부 서비스는 다른 서비스 또는 프로그램에서 사용되지 않으면 자동으로 중지됩니다. 참고한 사이트들 1. http://blog.naver.com/visioner7/120165951652 2. http://database.sarang.net/?inc=read&aid=6819&criteria=oracle&subcrit=&id=&limit=20&keyword=ora-12560&page=5 이런 걸 보면 오라클은 앙칼진 시골 아가씨야