트리에 대해서

안녕하세요, 오늘은 저번 시간에 이어서 새로운 자료구조에 대해서 알아봅시다.
오늘 배워볼 자료구조는 트리이며 이는 내용이 꽤 재미있으므로 지루하지 않을 것입니다.

🏕 트리란?

저번 시간에 배운 리스트는 데이터를 순서대로 나열하는 자료구조였지만 오늘 배워볼 트리는 데이터 사이의 계층 관계를 나타내는 자료구조입니다. 예를 들면 족보와 같이 일정한 규칙에 따라 데이터를 계층적으로 나타내는 것이라고 할 수 있습니다. 그럼 먼저 트리 자료구조에 대해서 알아보기 전 트리와 관련된 용어들을 살펴보도록 하겠습니다. 아래의 트리 구조를 참고하면서 글을 읽어주세요.

노드와 가지 : 트리의 구성 요소이며 각각의 노드는 가지를 통해 다른 노드와 연결되어 있습니다.

루트 : 트리의 가장 윗부분에 위치하는 노드이며 하나의 트리에는 하나의 루트만 존재합니다.

리프 : 자신의 노드 아래에 더 이상 노드가 존재하지 않는 것을 의미합니다.

안쪽 노드 : 리프를 제외한 트리 속 모든 노드를 의미합니다.

자식 : 어떤 노드로부터 가지로 연결된 아래쪽 노드를 의미합니다.

부모 : 어떤 노드에서 가지로 연결된 위쪽 노드를 의미합니다.

형제 : 같은 부모를 가진 노드를 의미합니다.

조상 : 어떤 노드에서 가지로 연결된 위쪽의 모든 노드를 의미합니다.

자손 : 어떤 노드에서 가지로 연결된 아래쪽의 모든 노드를 의미합니다.

레벨 : 루트로부터 얼마나 떨어져 있는지에 대한 값이며 아래로 내려갈수록 레벨이 1씩 증가합니다.

차수 : 노드가 갖는 자식의 수를 의미하며 모든 노드의 차수가 n이하인 트리를 n진 트리라고 합니다.

높이 : 루트로부터 가장 멀리 떨어진 아래쪽 리프까지의 거리를 의미합니다.

서브 트리 : 트리 안에서 다시 어떤 노드를 루트로 정하고 그 자손으로 이루어진 트리를 의미합니다.

널 트리 : 노드와 가지가 존재하지 않는 트리를 의미합니다.

순서 트리와 무순서 트리 : 형제 노드의 순서가 있는지 없는지에 따라 두 종류로 분류합니다.

🧭 순서 트리 검색

트리 자료구조에서는 대부분 순서 트리를 무순서 트리보다 자주 사용하기에 이를 초점을 두어 설명하겠습니다. 아래의 트리는 모든 노드의 차수가 2 이하인 이진트리입니다. 아래의 이진트리는 순서 트리에 포함되며 형제 노드의 순서가 존재합니다. 순서 트리는 트리 내부의 노드를 스캔하는 방법으로 너비 우선 탐색과 깊이 우선 탐색이라는 2가지의 대표적인 탐색 알고리즘이 존재합니다.

# 너비 우선 탐색 (BFS)

너비 우선 탐색은 아래와 같이 낮은 레벨에서 시작해 왼쪽에서 오른쪽 방향으로 노드를 검색하고 한 레벨에서의 검색이 모두 끝나면 다음 레벨로 내려가는 것을 볼 수 있습니다. 추후 배울 깊이 우선 탐색 알고리즘보다는 간단하나 확장성이 떨어지는 단점이 있습니다.

 

너비 우선 탐색 결과

A -> B -> C -> D -> E -> F -> G -> H -> I -> J -> K -> L

# 깊이 우선 탐색 (DFS)

깊이 우선 탐색은 아래와 같이 트리의 가장 하단에 위치한 리프까지 내려가면서 노드를 검색하는 것을 우선으로 하는 탐색 알고리즘입니다. 만약 리프에 도달해 더 이상 검색을 진행할 곳이 없을 경우 부모에게 돌아갑니다. 그런 다음 다시 자식 노드로 내려갑니다.

 

깊이 우선 탐색은 위에서 배웠던 너비 우선 탐색보다 확장성이 좋으며 노드의 방문 시기에 따라 전위 순회, 중위 순회, 후위 순회라는 3가지의 대표적인 순회 방법이 존재합니다. 각각의 순회 방법을 알아볼 때는 노드의 방문 시기를 주의 깊게 살펴보시기 바랍니다.

 

전위 순회 (Preorder)

노드 방문 -> 왼쪽 자식 -> 오른쪽 자식

깊이 우선 탐색 결과

A -> B -> D -> H -> E -> I -> J -> C -> F -> K -> L -> G

중위 순회 (Inorder)

왼쪽 자식 -> 노드 방문 -> 오른쪽 자식

깊이 우선 탐색 결과

H -> D -> B -> I -> E -> J -> A -> K -> F -> L -> C -> G

후위 순회 (Postorder)

왼쪽 자식 -> 오른쪽 자식 -> 노드 방문

깊이 우선 탐색 결과

H -> D -> I -> J -> E -> B -> K -> L -> F -> G -> C -> A

🖼 완전이진트리란?

위의 내용에서 모든 노드의 차수가 2 이하인 트리를 이진트리라고 했습니다. 그럼 완전이진트리는 무엇일까요? 트리의 루트부터 노드가 채워져 있으면서 같은 레벨에서는 왼쪽에서 오른쪽으로 노드가 빈 곳 없이 모두 채워져 있는 이진트리를 완전이진트리라고 합니다. 그러나 한 가지의 예외사항으로는 마지막 레벨은 왼쪽부터 오른쪽 방향으로 노드를 채우되 반드시 끝까지 채울 필요는 없다는 특징이 있습니다. 정리하면 마지막 레벨을 제외하고는 트리 속 각 레벨의 노드를 가득 채워야 하는 것이 완전이진트리의 조건입니다.

 

💌 이진검색트리란?

이진트리는 앞에서 배웠던 완전이진트리 뿐만 아니라 아래의 3가지 조건을 모두 만족한다면 이진검색트리가 될 수 있습니다. 이진검색트리의 특정 노드 N을 기준으로 왼쪽 서브 트리에 위치한 모든 노드의 키 값은 특정 노드 N의 키 값보다 작아야하며 또한 오른쪽 서브 트리 노드의 키 값은 노드 N의 키 값보다 커야하며 트리 속 내부에 존재하는 노드의 키 값은 모두 달라야 하는 조건이 있습니다.

 

이진검색트리의 조건

1) 어떤 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값보다 작아야 합니다.

2) 오른쪽 서브 트리 노드의 키 값은 노드 N의 키 값보다 커야 합니다.

3) 같은 키 값을 갖는 노드는 없어야 합니다.

위의 트리는 이진검색트리의 조건 3가지를 모두 만족하는 이진검색트리입니다. 이는 순서 트리에 포함되기 때문에 깊이 우선 탐색 알고리즘을 활용할 수 있으며 그중에서 중위 순회 방법을 사용한다면 아래와 같이 키 값의 오름차순으로 노드를 확인할 수 있습니다.

 

이처럼 이진검색트리는 중위 순회를 하면 키 값의 오름차순으로 노드를 확인할 수 있으며 구조가 매우 단순하고 이진검색과 비슷한 방식으로 검색이 가능하다는 점 그리고 노드의 삽입이 쉬운 점 등의 특징이 있어 트리 자료구조에서 폭넓게 사용되고 있습니다.

 

깊이 우선 탐색 결과 (중위 순회)

1 -> 4 -> 5 -> 6 -> 7 -> 9 -> 11 -> 12 -> 13 -> 14 -> 15 -> 18

그럼 지금부터 이진검색트리를 구현해보도록 하겠습니다. 앞에서 트리 자료구조의 구성 요소로는 노드와 가지가 존재한다고 했습니다. 아래의 노드 클래스는 이진검색트리의 개별 노드를 나타낸 것이며 4개의 멤버 변수로 구성됩니다. 가장 먼저 key라는 변수는 특정 노드의 고유 키 값을 뜻하며 이진검색트리에서는 각각의 노드 별로 이 key 값이 무조건 달라야만 합니다. 그리고 data 변수는 한 노드의 데이터 값을 의미합니다. key와 data 변수는 제네릭 형태의 자료형이므로 실질적인 value가 아닌 reference 변수입니다.

 

지금까지는 key와 data 즉 노드에 관련된 변수에 대해 알아보았습니다. 이번에는 이러한 노드들을 서로 연결해주는 트리 자료구조에서의 또 다른 구성 요소인 가지와 관련된 변수인 left와 right을 살펴보겠습니다. left 변수는 특정 노드에서 왼쪽 자식 노드에 대한 참조를 도와주며 마찬가지로 right 변수는 오른쪽 자식 노드에 대한 참조를 돕습니다. 이들은 주로 실질적인 포인터 역할을 합니다.

class Node<K, D> {
    K key;
    D data;
    Node<K, D> left;
    Node<K, D> right;
}

아래는 지금까지 배웠던 이진검색트리의 개념을 바탕으로 다양한 기능들을 구현해본 것입니다. 각각의 메서드 별로 설명을 하면 좋으나 양이 많기도 하고 위에서 얘기했던 개념만으로도 충분히 이해하실 수 있을 것이라고 판단해 상세한 설명은 건너뛰겠습니다. 이진검색트리의 3가지 조건을 기억하면서 코드들을 천천히 읽으며 분석하시기 바랍니다. 또한 코드 위에 작성해둔 주석을 참고하세요!

// 이진검색트리 클래스
public class BinTree<K, D> {

    // 노드 클래스
    static class Node<K, D> {
        private K key;
        private D data;
        private Node<K, D> left;
        private Node<K, D> right;

        // 생성자
        Node(K key, D data, Node<K, D> left, Node<K, D> right) {
            this.key = key;
            this.data = data;
            this.left = left;
            this.right = right;
        }

        // 키 값을 반환하는 메서드
        K getKey() {
            return key;
        }

        // 데이터 값을 반환하는 메서드
        D getData() {
            return data;
        }

        // 데이터를 출력하는 메서드
        void printData() {
            System.out.println(data);
        }
    }

    // 루트 & 비교자
    private Node<K, D> root;
    private Comparator<? super K> comparator = null;

    // 생성자
    public BinTree() {
        root = null;
    }

    // 생성자
    public BinTree(Comparator<? super K> c) {
        this();
        comparator = c;
    }

    // 두 키 값을 비교하는 메서드
    private int comp(K key1, K key2) {
        return (comparator == null) ? ((Comparable<K>) key1).compareTo(key2) : comparator.compare(key1, key2);
    }

    // 키 값으로 검색하는 메서드
    public D search(K key) {
        Node<K, D> p = root;

        while (p != null) {
            int cond = comp(key, p.getKey());

            if (cond > 0) p = p.right;
            else if (cond < 0) p = p.left;
            else return p.getData();
        }
        return null;
    }

    // node를 루트로 하는 서브 트리에 노드를 삽입하는 메서드 (아래의 add 메서드와 관련)
    private void addNode(Node<K, D> node, K key, D data) {
        int cond = comp(key, node.getKey());

        if (cond > 0) {
            if (node.right == null) node.right = new Node<>(key, data, null, null);
            else addNode(node.right, key, data);
        } else if (cond < 0) {
            if (node.left == null) node.left = new Node<>(key, data, null, null);
            else addNode(node.left, key, data);
        }
    }

    // 노드를 삽입하는 메서드
    public void add(K key, D data) {
        if (root == null) root = new Node<>(key, data, null, null);
        else addNode(root, key, data);
    }

    // 노드를 삭제하는 메서드
    public boolean remove(K key) {
        Node<K, D> p = root;
        Node<K, D> parent = null;
        boolean isLeftChild = true;

        while (true) {
            if (p == null) return false;

            int cond = comp(key, p.getKey());
            if (cond == 0) break;
            else {
                parent = p;
                if (cond < 0) {
                    isLeftChild = true;
                    p = p.left;
                } else {
                    isLeftChild = false;
                    p = p.right;
                }
            }
        }

        if (p.left == null) {
            if (p == root) root = p.right;
            else if (isLeftChild) parent.left = p.right;
            else parent.right = p.right;
        } else if (p.right == null) {
            if (p == root) root = p.left;
            else if (isLeftChild) parent.left = p.left;
            else parent.right = p.left;
        } else {
            parent = p;
            Node<K, D> left = p.left;
            isLeftChild = true;

            while (left.right != null) {
                parent = left;
                left = left.right;
                isLeftChild = false;
            }

            p.key = left.key;
            p.data = left.data;

            if (isLeftChild) parent.left = left.left;
            else parent.right = left.left;
        }
        return true;
    }

    // node를 루트로 하는 서브 트리의 노드를 키 값의 오름차순으로 출력하는 메서드 (아래의 print 메서드와 관련)
    private void printSubTree(Node<K, D> node) {
        if (node != null) {
            printSubTree(node.left);
            System.out.println(node.data);
            printSubTree(node.right);
        }
    }

    // 모든 노드를 출력하는 메서드
    public void print() {
        printSubTree(root);
    }
}

👍 글을 마치며

이렇게 해서 트리 자료구조에 대한 설명을 모두 마치겠습니다. 저번 시간에 배운 리스트 자료구조보다 양이 적고 내용이 재미있다 보니 글 작성도 빨리 할 수 있었습니다. 트리 자료구조는 실제 프로젝트에서는 다른 자료구조들에 비해 상대적으로 자주 사용하는 자료구조는 아니지만 코딩 테스트 및 알고리즘 문제를 풀 때는 정말 자주 사용하는 자료구조입니다. 그렇기에 개념을 단단히 숙지하고 확실히 이해하시기 바랍니다. 혹시나 오늘 글에서 이해가 되지 않거나 잘못된 내용을 발견하신다면 빠르게 댓글 남겨주시기 바랍니다.

 

참고 : Do it 자료구조와 함께 배우는 알고리즘 입문 자바 편