[Java자료구조] 8 - 트리 응용

학습목표

• 이진탐색트리 탐색, 삽입, 삭제 알고리즘을 이해한다.
• 힙(Heap) 삽입, 삭제 알고리즘을 이해한다.
• PriorityQueue 클래스를 활용하여 힙을 사용할 수 있다.
• 힙 정렬 알고리즘을 구현할 수 있다.

전위 순회 : 0->1->3->7->8->4->9->10->2->5->11->6

중위 순회 : 7->3->8->1->9->4->10->0->11->5->2->6

후위 순회 : 7->8->3->9->10->4->1->11->5->6->2->0

층별 순회 : 0->1->2->3->4->5->6->7->8->9->10->11

 

★전위 순회는 뿌리->왼쪽 자식->오른쪽 자식 순

★중위 순회는 왼쪽자식-> 뿌리-> 오른쪽 자식

★후위 순회는 왼쪽자식->오른쪽 자식-> 뿌리

★층별 순회는 그냥 노드의 순서대로

1. 이진탐색트리

이진탐색트리는 효율적인 탐색을 위한 자료구조로 아래와 같은 특성을 가진 이진트리이다.

• 모든 원소는 서로 다른 유일한 키를 갖는다.
• 왼쪽 서브트리에 있는 원소의 키는 그 루트의 키보다 작다.
• 오른쪽 서브트리에 있는 원소의 키는 그 루트의 키보다 크다.
• 왼쪽 서브트리와 오른쪽 서브트리도 이진탐색 트리다.

 

이진탐색트리는 중위순회를 통해 오름차순으로 정렬된 순서로 노드를 방문하게 된다

 

이진탐색트리는 $O(logn)$ 탐색 시간을 가진다 ⇒ 탐색 시간이 빠르다

이진탐색트리 탐색 연산

탐색은 항상 루트 노드에서 시작한다. 먼저, 키 값 x와 루트 노드의 키 값을 비교한다. 이진탐색트리 탐색 알고리즘을 의사코드로 표현하면 아래와 같다.

• if (x == 루트) 원하는 원소를 찾았으므로 탐색 성공
• else if (루트 > x) 루트의 왼쪽 서브트리에 대해서 탐색 연산 수행
• else if (루트 < x) 루트의 오른쪽 서브트리에 대해서 탐색 연산 수행

이진탐색트리 삽입 연산

이진탐색트리의 탐색, 삽입 연산을 자바로 구현한 예제

import java.util.*;
public class BinarySearchTree1 {
    class Node { // 이진탐색트리를 구성하는 노드 객체의 타입
        int key;
        Node left, right;
        public Node(int item) {
            key = item;
            left = right = null;
        }
    }
    Node root; // 루트 노드 저장 변수
    BinarySearchTree1() {
        root = null;
    }
    void insert(int key) { // 이진탐색트리에 데이터 추가
        root = insertRec(root, key);
        // 내부에서 재귀호출로 다시 불러서 사용
        // 재귀호출은 인자값이 무조건 하나 이상 더 많을 수 밖에 없음 만약 없으면 무한재귀호출에 빠질수도있음
    }

    Node insertRec(Node root, int key) { // root를 루트로 하는 서브트리에 key 값 추가
        if (root == null) {
            root = new Node(key);
            return root;
        }
        if (key < root.key) // 루트 값보다 작은면, 왼쪽 서브트리로
            root.left = insertRec(root.left, key);
        else if (key > root.key) // 루트 값보다 작은면, 왼쪽 서브트리로
            root.right = insertRec(root.right, key);
        return root;
    }
    void inorder() { // 중위 순회
        inorderRec(root);
    }
    void inorderRec(Node root) { // root를 루트로 가지는 서브트리 중위 순회
        if (root != null) {
            inorderRec(root.left);
            System.out.println(root.key);
            inorderRec(root.right);
        }
    }

    /*
    * 재귀호출로 동작을 하고, 현재 노드가 null이거나, 현재 노드의 키 값이 찾고자 하는 키 값(key)과 같은지 확인
    * 만약 두 조건 중 하나라도 만족하면 현재 노드를 반환함.
    * 찾고자 하는 키 값이 현재 노드의 키 값보다 작다면, 현재 노드의 왼쪽 자식 노드를 루트로 하는 서브 트리에서 키 값을 찾음
    *
    * */
    public Node search(Node root, int key) { // root 서브트리에 key 값 검색
        if (root==null || root.key==key)
            return root;

        if (root.key > key)
            return search(root.left, key);

        return search(root.right, key);
    }

    public static void main(String[] args) {
        BinarySearchTree1 tree = new BinarySearchTree1();
        // 이진탐색트리에 데이터 추가
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);
        tree.inorder(); // 이진탐색트리 중위 순회 : 오름차순 정렬
        System.out.println(tree.search(tree.root, 90)); // 만약 찾는 값이 없으면 Node의 값이 없으니까 null임
        if (tree.search(tree.root, 30) != null) // 이진탐색트리에서 30 검색
            System.out.printf("%d : 검색성공\\n", 30);
        else
            System.out.printf("%d : 검색실패\\n", 30);
    }
}

해당 코드를 이진 탐색트리 그림으로 나타내면

                    50
                 /       \\
               30         70
             /   \\       /  \\
            20    40    60   80

이진탐색트리 삭제 연산

만약에 삭제를 하여도 여전히 이진탐색트리의 규칙을 가지고 있어야함.

 

1. 삭제할 노드가 단말노드인 경우(차수가 0인 경우)

• 차수가 0이면 자식이 없는 단말노드이므로 그냥 삭제를 하면 끝

2. 삭제할 노드가 한 개의 자식노드를 가진 경우(차수가 1인 경우)

 

오른쪽 자식 노드를 본래 부모 노드의 자리의 루트로 대체를 시킴

 

3. 삭제할 노드가 두 개의 자식노드를 가진 경우(차수가 2인 경우)

 

왼쪽 서브트리 중에서 가장 큰 노드를 대체하거나 오른쪽 서브트리의 가장 작은 노드를 대체

연쇄적으로 대체를 해야함

 

 

/*
 * 노드 삭제 시 오른쪽 서브트리의 가장 작은 값을 선택하도록
 * */

import java.util.*;
class BinarySearchTree2 {
    class Node { // 이진탐색트리의 노드 객체 타입
        int key;
        Node left, right;
        public Node(int item) {
            key = item;
            left = right = null;
        }
    }
    Node root;
    BinarySearchTree2() {
        root = null;
    }
    void deleteKey(int key) { // 이진탐색트리에서 key 값 삭제
        root = deleteRec(root, key);
    }
    Node deleteRec(Node root, int key) { // root 서브트리에서 key 값 삭제
        if (root == null) return root;
        if (key > root.key) // 루트보다 크면 오른쪽 서브로
            root.right = deleteRec(root.right, key);
        else if (key < root.key) // 루트보다 작으면 왼쪽 서브로
            root.left = deleteRec(root.left, key);
        else {
            if (root.left == null) // 왼쪽 자식노드가 없으면
                return root.right;
            else if (root.right == null) // 오른쪽 자식노드가 없으면
                return root.left;
            // 오른쪽 서브트리에서 가장 작은 값을 찾아서 삭제할 노드의 키값으로 설정
            System.out.println("minValue" + minValue(root.right));
            root.key = minValue(root.right);
            // 오른쪽 서브트리에서 가장 작은 값을 삭제
            root.right = deleteRec(root.right, root.key);
        }
        return root;
    }

    int minValue(Node root) { // root 서브트리에서 최소값 반환
        int minv = root.key;
        while (root.left != null) {
            minv = root.left.key;
            root = root.left;
        }
        return minv;
    }

    void insert(int key) { // 이진탐색트리에 key 값 삽입
        root = insertRec(root, key);
    }
    Node insertRec(Node root, int key) { // root 서브트리에 key 값 삽입
        if (root == null) {
            root = new Node(key);
            return root;
        }
        if (key < root.key)
            root.left = insertRec(root.left, key);
        else if (key > root.key)
            root.right = insertRec(root.right, key);
        return root;
    }
    void inorder() { // 이진탐색트리 중위순회
        inorderRec(root);
    }
    void inorderRec(Node root) { // root 서브트리 중위순회
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.key + " ");
            inorderRec(root.right);
        }
    }
    public static void main(String[] args) {
        BinarySearchTree2 tree = new BinarySearchTree2();
        // 이진탐색트리에 데이터 추가
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);
        System.out.println("중위순회 : ");
        tree.inorder(); // 중위순회 : 오름차순 정렬
        System.out.println("\\n20 삭제"); // 20은 단말노드임
        tree.deleteKey(20); // 데이터 20 삭제
        System.out.println("중위순회 : ");
        tree.inorder(); // 중위순회 : 오름차순 정렬
        System.out.println("\\n30 삭제"); // 30은 40을 오른쪽 서브트리로 가짐 (차수 : 1)
        // 차수가 1이기에 삭제 시 오른쪽 서브트리의 가장 작은 값을 선택하여 대체

        tree.deleteKey(30); // 데이터 30 삭제
        System.out.println("중위순회 : ");
        tree.inorder(); // 중위순회 : 오름차순 정렬
        System.out.println("\\n50 삭제"); // 50은 루트노드임(차수 : 2)
        // 차수가 2이기에 삭제 시 오른쪽 서브트리의 가장 작은 값을 선택하여 대체한다.

        tree.deleteKey(50); // 데이터 50 삭제
        System.out.println("중위순회 : ");
        tree.inorder(); // 중위순회 : 오름차순 정렬
    }
}

 

 

추가 실습) maxValue(root.left)

• 왼쪽 서브트리에서 가장 큰 값을 찾아서 root로 대체

import java.util.*;
/*
* 노드 삭제 시 왼쪽 서브트리의 가장 큰 값을 선택하도록
* */
class BinarySearchTree3 {
    class Node { // 이진탐색트리의 노드 객체 타입
        int key;
        Node left, right;
        public Node(int item) {
            key = item;
            left = right = null;
        }
    }
    Node root;
    BinarySearchTree3() {
        root = null;
    }
    void deleteKey(int key) { // 이진탐색트리에서 key 값 삭제
        root = deleteRec(root, key);
    }
    Node deleteRec(Node root, int key) { // root 서브트리에서 key 값 삭제
        if (root == null) return root;
        if (key > root.key) // 루트보다 크면 오른쪽 서브로
            root.right = deleteRec(root.right, key);
        else if (key < root.key) // 루트보다 작으면 왼쪽 서브로
            root.left = deleteRec(root.left, key);
        else {
            if (root.left == null) // 왼쪽 자식노드가 없으면
                return root.right;
            else if (root.right == null) // 오른쪽 자식노드가 없으면
                return root.left;
            // 왼쪽 서브트리에서 가장 큰 값을 찾아서 삭제할 노드의 키값으로 설정
            System.out.println("오른쪽 서브트리에서 가장 큰 값을 찾아서 삭제할 노드의 키 값으로 설정 "+ maxValue(root.left));
            root.key = maxValue(root.left);
            // 왼쪽 서브트리에서 가장 큰 값을 삭제
            root.left = deleteRec(root.left, root.key);
        }
        return root;
    }

    int maxValue(Node root) { // root 서브트리에서 최대값 반환
        int maxv = root.key;
        while (root.right != null) {
            maxv = root.right.key;
            root = root.right;
        }
        return maxv;
    }

    void insert(int key) { // 이진탐색트리에 key 값 삽입
        root = insertRec(root, key);
    }
    Node insertRec(Node root, int key) { // root 서브트리에 key 값 삽입
        if (root == null) {
            root = new Node(key);
            return root;
        }
        if (key < root.key)
            root.left = insertRec(root.left, key);
        else if (key > root.key)
            root.right = insertRec(root.right, key);
        return root;
    }
    void inorder() { // 이진탐색트리 중위순회
        inorderRec(root);
    }
    void inorderRec(Node root) { // root 서브트리 중위순회
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.key + " ");
            inorderRec(root.right);
        }
    }
    public static void main(String[] args) {
        BinarySearchTree3 tree = new BinarySearchTree3();
        // 이진탐색트리에 데이터 추가
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);
        System.out.println("중위순회 : ");
        tree.inorder(); // 중위순회 : 오름차순 정렬
        System.out.println("\\n20 삭제");
        tree.deleteKey(20); // 데이터 20 삭제
        System.out.println("중위순회 : ");
        tree.inorder(); // 중위순회 : 오름차순 정렬
        System.out.println("\\n30 삭제");
        tree.deleteKey(30); // 데이터 20 삭제
        System.out.println("중위순회 : ");
        tree.inorder(); // 중위순회 : 오름차순 정렬
        System.out.println("\\n50 삭제");
        tree.deleteKey(50); // 데이터 20 삭제
        System.out.println("중위순회 : ");
        tree.inorder(); // 중위순회 : 오름차순 정렬
    }
}

2. 힙(Heap)

힙(Heap)은 완전 이진트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 쉽게 찾기 위해 만들어진 자료구조이다. 힙에는 최대 힙(Max Heap)과 최소 힙(Min Heap)이 두 가지 종류가 있다.

 

힙의 장점은 원소가 1조개가 있어도 정렬을 하는건 40번만 하면됨

부모가 자식보다 더 큰 값으로 만들어짐

완전 이진트리 = 힙(Heap)

 

삽입 연산

힙도 이진탐색트리와 동일하게 삽입을 하여도 완전 이진트리를 유지하여야 한다.

삽입 연산은 최대 트리의 높이만큼만 반복 수행되므로 수행시간 복잡도가 $O(logn)$ 이다.

 

삭제 연산

삭제 연산도 트리 높이만큼만 수행하면 되므로 수행시간 복잡도는 $O(logn)$ 이다.

 

마지막 노드를 루트자리로 가져다 놓고 밑의 값들과 비교를 하여 밑의 값이 더 크면 자리 바꾸기를 계속해서 반복한다.

import java.util.*;
public class MaxHeap {
    private int[] Heap; // 이진트리(힙)를 표현하는 배열
    private int size;
    private int maxsize;
    private static final int FRONT = 1;
    public MaxHeap(int maxsize) {
        this.maxsize = maxsize;
        this.size = 0;
        Heap = new int[this.maxsize + 1];
        Heap[0] = Integer.MAX_VALUE;
    }
    private int parent(int pos){ // 부모노드 반환
        return pos / 2;
    }
    private int leftChild(int pos) { // 왼쪽 자식노드 반환
        return (2 * pos);
    }
    private int rightChild(int pos) { // 오른쪽 자식노드 반환
        return (2 * pos) + 1;
    }
    private boolean isLeaf(int pos) { // 단말노드 체크
        if (pos > (size / 2) && pos <= size)
            return true;
        return false;
    }
    private void swap(int fpos, int spos){ // 두 노드간에 위치 교환
        int tmp;
        tmp = Heap[fpos];
        Heap[fpos] = Heap[spos];
        Heap[spos] = tmp;
    }
    private void maxHeapify(int pos) { // MaxHeap 만족하도록 재구성
        if (!isLeaf(pos))
            if (Heap[pos] < Heap[leftChild(pos)] ||
                    Heap[pos] < Heap[rightChild(pos)])
                if (Heap[leftChild(pos)] > Heap[rightChild(pos)]){
                    swap(pos, leftChild(pos));
                    maxHeapify(leftChild(pos));
                } else{
                    swap(pos, rightChild(pos));
                    maxHeapify(rightChild(pos));
                }
    }
    public void insert(int element) { // 힙에 데이터 추가 연산 수행
        Heap[++size] = element;
        int current = size;
        while (Heap[current] > Heap[parent(current)]){
            swap(current, parent(current));
            current = parent(current);
        }
    }
    public void print(){ // 힙에 저장된 데이터 출력
        for (int i = 1; i <= size / 2; i++) {
            System.out.print(" PARENT : " + Heap[i] + " LEFT_CHILD : " +
                    Heap[2 * i] + " RIGHT_CHILD :" + Heap[2 * i + 1]);
            System.out.println();
        }
    }
    public int remove() { // 힙에서 데이터 삭제 연산 수행
        int popped = Heap[FRONT]; // FRONT는 1 == root 위치
        Heap[FRONT] = Heap[size--];
        maxHeapify(FRONT);
        return popped;
    }
    public static void main(String[] arg) {
        System.out.println("Max Heap : ");
        MaxHeap maxHeap = new MaxHeap(15); // 크기가 15인 힙 객체 생성
        // 힙에 데이터 추가
        maxHeap.insert(5);
        maxHeap.insert(3);
        maxHeap.insert(17);
        maxHeap.insert(10);
        maxHeap.insert(84);
        maxHeap.insert(19);
        maxHeap.insert(6);
        maxHeap.insert(22);
        maxHeap.insert(9);
        maxHeap.print();
        System.out.println("최대값 : " + maxHeap.remove());
        // 배열의 0번째 인덱스는 비어있기 때문에 remove를 하면 1번째 값이 나옴
        System.out.println("삭제 작업");
        System.out.println("가장 큰 값(84)이 삭제되고 그 다음 큰 값인 22가 root가 됨");
        maxHeap.print();
        System.out.println("최대값 : " + maxHeap.remove());
    }
    /*         최대힙 결과
    *              84
    *          22      19
    *       17   10   5   6
    *     3    9
    *  */
}

 

 

3. 자바 PrlorityQueue 활용

PriorityQueue 클래스는 Java에서 제공하는 우선순위 큐 자료구조를 구현한 클래스이다. 이 클래스는 내부적으로 최소 힙(Min Heap)을 사용하며, 우선순위 큐의 특성에 따라 가장 작은 원소가 먼저 나오는 구조이다. 객체를 저장할 때는 해당 객체가 Comparator 인터페이스를 구현한 경우에 한해 저장할 수 있다.

다음은 자바 PriorityQueue 클래스의 사용 예제이다.

import java.util.*;
public class PriorityQueueTest {
    public static void main(String[] args) {
        // 정수객체를 저장하는 우선순위큐 객체 생성
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // 1~10까지의 정수를 입력
        for (int i=10; i>=1; i-- )
            pq.add (new Integer (i)) ;

        System.out.println ("힙 상태 : "+ pq);

        //우선순위 큐에서 가장 작은 숫자를 추출
        Integer root = pq.peek();
        System.out.println ( "루트 값 : "+ root);
    }
    /*
    *           1
    *       2       5
    *    4     3  9    6
    *  10  7  8
    * */
}

 

기본적으로 PriorityQueue는 최소 힙을 구현하고 있어, 루트에는 가장 작은 원소가 위치하게 된다. PriorityQueue에서 값을 하나 꺼내면 가장 작은 원소가 반환되고, 남은 원소들은 다시 최소 힙으로 재구성된다.

따라서 PriorityQueue에서 삭제 연산을 반복하면 오름차순으로 정렬된 결과를 얻을 수 있다. 이를 힙 정렬(Heap Sorting)이라고 한다.

 

다음은 내림차순 정렬을 위해 PriorityQueue를 사용한 예제이다.

import java.util.*;
public class PriorityQueueTest2 {
    public static void main(String[] args) {
        // 정수객체를 저장하는 우선순위큐 객체 생성
        PriorityQueue<Integer> pq = new PriorityQueue<>(10, Collections.reverseOrder());
        int[] arr = {3, 1, 9, 5, 7};

        // arr의 정수를 입력
        for (int i = 0; i<arr.length; i++ )
            pq.add (arr[i]) ;

        System.out.println ("힙 상태 : "+ pq);

        System.out.print("내림차순정렬 : ");
        for(int i=0; i<arr.length; i++)
            System.out.print(pq.remove() + " ");
    }
        /*
                 9
                / \\
               7   3
              / \\
             1   5
    * */
}

 

힙 정렬을 알면 최적 정렬 알고리즘을 만들 수 있다.

시간 복잡도 : $O(logn)$