[Tree] 이진 트리 ( Binary Tree )

이진 트리란?

이진 트리는 트리 자료구조의 한 종류로, 각 노드가 최대 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에 출력할 경우 위와 같이 출력해 볼 수 있습니다.

Termial 출력 코드

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

W3Schools.com