Repository

들어가기에 앞서

해당 글을 작성하기에 앞서 이진트리는 어떤 것인지에 대한 사전 지식이 있어야 이해할 수 있는 글입니다.

만약 이진트리가 무엇인지 모른다면 이 글을 읽고 오시기 바랍니다.

이진 트리 순회

이진 트리를 순회하는 방법에는 어디서부터 확인하느냐로 4가지로 나눌 수 있습니다.

순회 방법에 따라 사용처가 다르게 나오게 되고, 이를 학습함으로써 좀 더 본인이 사용하고자 하는 목적에 알맞은 방법으로 알고리즘을 작성할 수 있습니다.

아래 보이는 이진 트리를 통해 각각의 순회 결과에 대해 알려드리겠습니다.

아래 이진 트리는 이 곳에서 코드로 확인해 보실 수 있습니다.

전위 순회 ( Pre-order Traversal )

전위 순회는 부모 노드 -> 왼쪽 노드 -> 오른쪽 노드 순으로 재귀하며 출력하는 방법입니다.

즉 가장 왼쪽부터 라인부터 탐색하며, 가장 깊은 Level의 오른쪽 노드부터 차근차근 탐색할 수 있게 해줍니다.

public void traversePreOrder(TreeNode<Integer> node) {
    if (node != null) {
        System.out.print(" " + node.getValue());
        traversePreOrder(node.getLeft());
        traversePreOrder(node.getRight());
    }
}

결과

사용처

• DFS 탐색
• 트리 복사

중위 순회 ( In-order Traversal )

중위 순회는 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식노드 순으로 순회하는 방법입니다.

public void traverseInOrder(TreeNode<Integer> node) {
    if (node != null) {
        traverseInOrder(node.getLeft());
        System.out.print(" " + node.getValue());
        traverseInOrder(node.getRight());
    }
}

결과

사용처

• 오름차순 정렬
• 정렬된 데이터 탐색

후위 순회 ( Post-order Traversal )

후위 순회는 왼쪽 자식노드 -> 오른쪽 자식노드 -> 부모 노드 순으로 순회하는 방법입니다.

public void traversePostOrder(TreeNode node) {
    if (node != null) {
        traversePostOrder(node.getLeft());
        traversePostOrder(node.getRight());
        System.out.print(" " + node.getValue());
    }
}

결과

사용처

• 메모리 해제
• 파일 구조 삭제
• 후위 표기법을 통한 연산

레벨 순회 ( Level-order Traveral )

레벨 순회는 root 부터 각 레벨마다 순차적으로 왼쪽부터 오른쪽으로 순회하는 방법입니다.

public void traverseLevelOrder(TreeNode root) {
    if (root == null) return;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.print(" " + node.getValue());

        if (node.getLeft() != null) queue.add(node.getLeft());
        if (node.getRight() != null) queue.add(node.getRight());
    }
}

결과

사용처

• 최단 경로 탐색
• Bfs 탐색

Reference

https://www.w3schools.com/dsa/dsa_data_binarysearchtrees.php

이진 트리란?

이진 트리는 트리 자료구조의 한 종류로, 각 노드가 최대 2개의 자식노드를 가질 수 있는 구조입니다.

이진 트리를 구성하는 노드들은 3가지로 분리할 수 있습니다.

• 루트 노드 ( Root Node ): 트리의 시작점으로, 부모 노드가 존재하지 않고 이진트리에서 하나만 존재합니다.
• 자식 노드 ( Child Node ): 부모 노드에 속한 노드로써 Left Child와 Right Child로 구분.
• 잎 노드 (Leaf Node): 트리의 마지막에 존재하는 노드로써 자식이 존재하지 않는 노드를 의미합니다.

위와 같이 3가지로 분류할 수 있지만 때에 따라 하나의 노드가 의미하는 바가 겹칠 수 있습니다.

이진 트리 유형

이진 트리는 속한 노드들의 상태에 따라 아래와 같은 유형들로 분류할 수 있습니다.

균형 이진 트리 ( Balanced Binary Tree )

모든 자식 노드들의 Level차이가 최대 1 이하 차이나는 트리입니다.

즉, 한 노드에 쏠림 현상이 발생하지 않고 아래와 같이 규형 잡힌 상태를 의미합니다.

포화 이진 트리 ( Full Binary Tree )

모든 자식 노드가 0개 혹은 2개씩 채워진 상태를 의미합니다. 

완전 이진 트리 ( Complete Binary Tree )

완전 이진트리는 마지막 레벨을 제외 모든 노드들이 채워져 있는 상태를 의미합니다.

이때 자식 노드는 왼쪽부터 차 있어야 합니다.

이진 트리 표현

이진 트리는 배열과 링크드 리스트를 통해 표현할 수 있습니다.

Array 표현

배열을 통해 이진트리를 표현할 경우 아래와 같은 규칙을 통해 표현할 수 있습니다.

• 루트는 배열의 0번째 인덱스 혹은 1번째 인덱스에 존재한다.
• 왼쪽 자식인덱스 = 루트 인덱스 == 0 ? 부모 인덱스 * 2 + 1 : 부모 인덱스 * 2;
• 오른쪽 자식 인덱스 = 루트 인덱스 == 0 ? 부모인덱스 * 2 + 2; 부모 인덱스 * 2 + 1;

위와 같은 규칙을 가지고 이진트리를 표현하였을 때 단점이 존재하는데,

이는 배열로 구현하다 보니 초기 이진트리의 크기가 특정된다는 점이고, 이는 이진트리 내 데이터가 골고루 분포되지 않다면 메모리 자원을 비효율 적으로 사용한다는 단점이 존재합니다.

public static void main(String[] args) {
        int[] arr = new int[7];
        // Root
        arr[0] = 1;
        // Level 1
        arr[1] = 2;
        arr[2] = 3;
        // Level 2
        arr[3] = 4;
        // Level 3
        arr[5] = 6;
        arr[6] = 7;
        printTree(arr);
}

코드로 작성하면 위와 같이 작성을 할 수 있고, Terminal에 출력할 경우 위와 같이 출력해 볼 수 있습니다.

public static void printTree(int[] arr) {
        int level = 0;
        int index = 0;
        while (index < arr.length) {
            int nodesInLevel = (int) Math.pow(2, level); // 해당 레벨의 노드 개수
            for (int i = 0; i < nodesInLevel && index < arr.length; i++) {
                System.out.print(arr[index] + " ");
                index++;
            }
            System.out.println(); // 각 레벨 출력 후 줄바꿈
            level++;
        }
 }

Linked List 표현

Linked List로 표현할 경우 좀더 효율적으로 생성이 가능하다는 장점이 있지만, 균형 이진 트리인 경우 배열로 구현하는 것이 더욱 효율적이라 생각합니다.

우선 우리가 알고 있는 java.util.LinkedList 구현체로 구현하는 것은 아닙니다.

LinkedList의 구현체 중 데이터 저장 클래스인 Node를 확인해보면 Node안은 아래 필드들로 구현되어있습니다.

• E item
• Node<E> next
• Node<E> prev

위와 같이 이전과 이후에 대한 주소를 얻을 수 있지만 우리가 원하는 이진트리를 구현하기 위해서는 next가 leftNext와 rightNext로 나눠져야합니다.

그리하여 직접 구현한다면 아래와 같이 구현할 수 있습니다.

public static class TreeNode<E> {
        private E item;
        private TreeNode<E> left;
        private TreeNode<E> right;

        public TreeNode(E item) {
            this.item = item;
        }

    }

    public static class BinaryTree {
        TreeNode<Integer> root;

        public void add(Integer item) {
            root = addRecursive(root, item);
        }
        private TreeNode<Integer> addRecursive(TreeNode<Integer> current, Integer item) {
            if (current == null) {
                return new TreeNode<>(item);
            }

            if(current.item > item) {
                current.left = addRecursive(current.left, item);
            } else {
                current.right = addRecursive(current.right, item);
            }

            return current;
        }
}

root를 기준으로 왼쪽은 작은값, 오른쪽은 큰값으로 셋팅되게 구현하였습니다.

검색의 성능을 높이기 위해 최소 힙, 최대 힙, 탐색 이진 트리 등등 다양한 방법으로 구성될 수 있으며,

해당 내용들은 다음 글에 작성하도록 하겠습니다.

Reference

https://www.w3schools.com/dsa/dsa_data_binarysearchtrees.php