[비선형 자료구조] 트리(1) - 이진 트리(Binary Tree)

[비선형 자료구조] 트리 링크

트리(2) - 이진탐색트리

트리(3) - AVL 트리

트리(4) - Red-Black 트리

트리(Tree)

• 트리는 노드와 링크로 구성된 자료구조다.
• 그래프의 일종으로 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph) 또는 DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한 종류 이다.(Acyclic = cycle이 존재하지 않는 그래프)
• 계층적 구조(계층 모델)를 나타낼 때 사용한다. 조직도, 가계도, 폴더(디렉토리, 서브 디렉토리)와 같은 파일시스템 구조나 계층적으로 저장할 때 많이 쓰인다.
• 구조상 데이터 저장보다는 저장된 데이터의 효과적인 탐색을 위해 사용된다. 선형 자료구조는 정렬이 되어있지않은 상태에서 특정 값을 탐색한다면 최악의 시간복잡도는 맨 끝까지 탐색하기에 O(N)이지만 이진트리에서 탐색하는데 최적의 시간복잡도는 O(logN)이다.
• 힙(Heap)을 구현하는 방법 중 하나가 트리다.

트리구조예시(파일시스템)

 

트리에서 사용되는 용어

트리에서 사용되는 용어 그림

• 노드(Node) : 트리 구조의 자료 값을 담고 있는 단위
• 간선(Edge) : 노드 간의 연결선
• 루트 노드(Root node) : 부모가 없는 노드, 가장 위의 (최상위)노드
• 잎새 노드(Leaf node) : 자식이 없는 노드(=단말 노드)
• 내부 노드(Internal node) : Leaf node를 제외한 모든 노드
• 부모(Parent) : 연결된 두 노드 중 상위 노드
• 자식(Child) : 연결된 두 노드 중 하위 노드
• 형제(Sibling) : 같은 부모를 가지는 노드
• 깊이(Depth) : 루트에서 어떤 노드까지의 간선의 수( ex : A(root)=0, D=2)
• 레벨(Level) : 트리의 특정 깊이를 가지는 노드 집합
• 높이(Height) : 트리에서 가장 큰 레벨 값
• 크기(Size) : 자신을 포함한 자식 노드의 개수
• 차수(Degree) : 하위 트리 개수 / 간선 수 = 각 노드가 지닌 가지의 수(자식 수)
• 트리의 차수 : 트리의 최대 차수

트리의 특징

1. 하나의 노드에서 다른 노드로 이동하는 경로는 유일하다. 예를 들어, A에서 D로 가는 경로는 한가지 방법밖에 없는 것을 말한다. 그래프의 경우 여러 방법으로 갈 수 있다.
2. 노드가 N개인 트리의 edge(간선) 개수는 N-1개이다.
3. Cycle이 존재하지 않는 Acyclic이다. 모든 노드는 연결되어 있어야한다. 하나의 독립적인, 연결 안된게 존재한다면 그건 다른 트리가 되는 것이다. 하나의 엣지를 끊으면 두 개의 sub-tree로 분리된다.
4. 트리 안에 또다른 트리가 있는 재귀적 자료구조다.

---

이진 트리(Binary Tree)

이진 트리는 부모 노드 밑의 자식 노드 개수(=차수, degree)를 최대 2개로 제한하는, 트리의 가장 간단한 형태다.

탐색하는데 최적의 시간 복잡도는 O(logN)이다.

이진트리특징 예시

자식 노드는 좌우를 구분한다. 왼쪽은 왼쪽자식, 오른쪽은 오른쪽 자식이라고 한다.

 

이진 트리 종류

포화 이진 트리(좌), 완전 이진 트리(우)

포화 이진 트리(Perfect binary tree) - 모든 레벨에서 노드들이 꽉 채워져 있는 트리

완전 이진 트리(Complete binary tree) - 마지막 레벨(층)을 제외하고 노드들이 모두 채워져 있는 트리

정 이진 트리(Full binary tree) - 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

편향, 사향 트리(Skewed Binary Tree) - 한쪽으로 기울어진 트리(연결리스트도 트리의 일종이라고 보는게 이 종류다.) 모든 트리를 탐색해야 하므로 최악의 경우로 탐색시 시간복잡도가 O(n)이다. 이런 균형문제를 해결하고 시간복잡도 O(logN)을 보장하기 위해 'AVL tree'나 'red-black tree'를 쓴다고 한다.

균형 이진 트리(Balanced binary tree) - 모든 노드의 좌우 서브 트리 높이가 1이상 차이나지 않는 트리, 편향에 비해 탐색속도가 빨라서 중요하다.

이진 트리 특징

1. 포화 이진 트리의 높이가 h일 때 노드의 수는 2^(h+1)-1개이다.
2. 포화(or 완전) 이진 트리의 노드가 N개일 때, 높이는 logN이다.(소수점 버리고)
3. 이진 트리의 노드가 N개일 때 최대 가능 높이는 N이다.

이진 트리 순회(Traversal)

이진 트리 순회는 모든 노드를 빠뜨리거나 중복하지 않고 방문하는 연산을 말한다. 순회의 종류는 전위 순회, 중위 순회, 후위 순회, 레벨 순서 순회가 있다.  전위, 중위, 후위는 DFS, 레벨은 BFS에 속해있다.

전위 순회(Preorder Traversal = 중왼오)

현재 노드(중간 노드), 왼쪽 노드, 오른쪽 노드 순으로 순회하는 방법이다.

중위 순회(Inorder Traversal = 왼중오)

왼쪽 노드, 중간 노드, 오른쪽 노드 순으로 순회하는 방법이다.

후위 순회(Postorder Traversal = 왼오중)

왼쪽 노드, 오른쪽 노드, 중간 노 순으로 순회하는 방법이다.

레벨 순회(Level-order Traversal)

위쪽 레벨부터 왼쪽에서 오른쪽으로 순회하는 방법이다.

이진 트리 구현

이진트리를 구현하는데는 2가지 방법이 있다.

1. 배열 구현(1차원 or 2차원)

배열 구현은 레벨 순회 순으로 배열에 넣어주면 된다. 루트노드를 처음에 넣고, 왼쪽노드는 부모노드 인덱스*2+0, 오른쪽노드는 부모노드 인덱스*2+1이다. 편의상 위 그림에선 인덱스 1부터 보여줬는데 실제 구현상에서는 처음 인덱스가 0이므로 살짝 바뀐다.

 

배열구현(java)

class BinaryTree {
    char[] arr;

    BinaryTree(char[] data) {
        this.arr = data.clone();
    }

    public void preOrder(int idx) { // 전위 순회(중왼오)
        System.out.print(this.arr[idx] + " ");

        int left = 2 * idx + 1;
        int right = 2 * idx + 2;
        if (left < this.arr.length) {
            this.preOrder(left);
        }
        if (right < this.arr.length) {
            this.preOrder(right);
        }
    }

    public void inOrder(int idx) { // 중위 순회(왼중오)
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;

        if (left < this.arr.length) {
            this.inOrder(left);
        }

        System.out.print(this.arr[idx] + " ");

        if (right < this.arr.length) {
            this.inOrder(right);
        }
    }

    public void postOrder(int idx) { // 후위 순회(왼오중)
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;

        if (left < this.arr.length) {
            this.postOrder(left);
        }

        if (right < this.arr.length) {
            this.postOrder(right);
        }

        System.out.print(this.arr[idx] + " ");
    }

    public void levelOrder(int idx) { // 레벨 순회
        for (int i = idx; i < this.arr.length; i++) {
            System.out.print(this.arr[i] + " ");
        }
        System.out.println();
    }
}

2. 연결리스트 구현

값과 간선(엣지)를 관리하기 위한 노드로 연결리스트를 구성한다. 연결리스트 링크 두 개 해서 하나는 왼쪽노드, 하나는 오른쪽 노드를 가리키게 만들어주면 된다.

대부분 재귀함수로 구현 가능하지만 연결리스트 레벨순회는 잘 안되므로 큐에 넣어서 구현하면 된다.

class Node {
    char data;
    Node left;
    Node right;

    Node(char data, Node left, Node right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
}

class BinaryTree {
    Node head;

    BinaryTree() {}
    BinaryTree(char[] arr) {
        Node[] nodes = new Node[arr.length];
        for (int i = 0; i < arr.length; i++) {
            nodes[i] = new Node(arr[i], null, null);
        }

        for (int i = 0; i < arr.length; i++) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;

            if (left < arr.length) {
                nodes[i].left = nodes[left];
            }

            if (right < arr.length) {
                nodes[i].right = nodes[right];
            }

        }
        this.head = nodes[0];
    }

    public void preOrder(Node node) {
        if (node == null) {
            return;
        }

        System.out.print(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
    }

    public void inOrder(Node node) {
        if (node == null) {
            return;
        }

        inOrder(node.left);
        System.out.print(node.data + " ");
        inOrder(node.right);
    }

    public void postOrder(Node node) {
        if (node == null) {
            return;
        }

        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.data + " ");
    }

    public void levelOrder(Node node) {
        Queue<Node> queue = new LinkedList();
        queue.add(node);
        while (!queue.isEmpty()) {
            Node cur = queue.poll();

            System.out.print(cur.data + " ");
            if (cur.left != null) {
                queue.offer(cur.left);
            }

            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }
}

* 그래프와 트리의 차이

 

다음 포스팅에서는 이진 탐색 트리에 다뤄보도록 하겠다.