[Java] Tree

트리

• 일반적인 트리는 실제 트리를 거꾸로 세워놓은 형태의 자료 구조
• HTML과 XML의 문서 트리, 자바 클래스 계층 구조, 운영체제의 파일 시스템, 탐색트리, 이항 힙, 피보나치 힙과 같은 우선순위큐에서 사용
• 일반적인 트리의 정의
  • 트리는 empty이거나 empty가 아니면 루트노드 R과 트리의 집합으로 구성되는데
    단, 트리의 집합은 공집합일 수도 있다.

용어

• 루트(Root) 노드 : 트리 최상위에 있는 노드
• 자식(Child) 노드 : 노드 하위에 연결된 노드
• 차수(Degree) : 자식 노드의 수
• 부모(Parent) 노드 : 노드의 상위에 연결된 노드
• 리프(Leaf) 노드 : 자식이 없는 노드 (단말(Terminal) 혹은 외부 노드라고 하기도 함)
• 내부(Internal) 노드 : 비단말(Non-Terminal) 노드로 리프노드가 아닌 노드
• 형제(Sibling) 노드 : 동일한 부모를 가지는 노드
• 조상(Ancestor) 노드 : 루트노드까지의 경로상에 있는 모든 노드 집합
• 후손(Descendant) 노드 : 노드 아래로 매달린 모든 노드들의 집합
• 서브트리(Subtree) : 노드 자신과 후손노드로 구성된 트리
• 레벨(level) : 루트노드는 레벨 1, 아래 층으로 내려가며 레벨이 1씩 증가 (깊이와 같음)
• 높이(Height) : 트리의 최대 레벨
• 키(key) : 탐색에 사용되는 노드에 저장된 정보

표현

일반 표현

일반적인 트리를 메모리에 저장하려면 각 노드에 키와 자식 수만큼의 레퍼런스 저장 필요

• N개의 노드가 있는 최대 차수가 k인 트리 null 레퍼런스 수
  null 레퍼런스 수 = Nk - (N - 1) = N(k-1) + 1
  • Nk = 총 레퍼런스 수
  • N-1 트리에서 부모-자식을 연결하는 레퍼런스 수
• 즉, k가 클수록 메모리 낭비가 심해지는 것은 물론 트리를 탐색하는 과정에서 null 레퍼런스를 확인해야 하므로 시간적으로도 매우 비효율적

왼쪽자식-오른쪽 형제 표현

노드의 왼쪽 자식과 왼쪽 자식의 오른쪽 형제노드를 가리키는 2개의 레퍼런스만 사용

트리의 응용

• 조직이나 기관의 계층구조
• 컴퓨터 운영체제의 파일 시스템
• 자바 클래스 계층 구조 등
• 트리는 일반적인 트리와 이진트리로 구분
• 다양한 탐색트리, 힙 자료구조, 컴파일러의 수식을 위한 구문트리 (Syntax Tree)등의 기본이 되는 자료구조로서 광범위하게 응용

이진트리

• 이진트리(Binary Tree)는 각 노드의 자식 수가 2 이하인 트리
• 컴퓨터 분야에서 널리 활용되는 기본적인 자료구조
• 이진트리가 데이터의 구조적인 관계를 잘 반영하고, 효율적인 삽입과 탐색을 가능하게 하며, 이진트리의 서브트리를 다른 이진트리의 서브트리와 교환하는 것이 쉽기 때문이다.
• 이진트리에 대한 용어는 일반적인 트리에 대한 용어와 동일

→ 이진트리는 empty이거나, empty가 아니면 루트노드 2개와 이진트리인 왼쪽 서브트리와 오른쪽 서브트리로 구성

특별한 형태의 이진 트리

포화이진트리(Full Binary Tree)

각 내부노드가 2개의 자식 노드를 가지는 트리

완전이진트리(Complete Binary Tree)

마지막 레벨을 제외한 각 레벨이 노드들로 꽉 차있고, 마지막 레벨에는 노드들이 왼쪽부터 빠짐없이 채워진 트리

편향이진트리(Skewed Binary Tree)

편향이진트리를 배열에 저장하는 경우, 트리의 높이가 커질수록 메모리 낭비가 심화된다. 따라서 일반적인 노드는 키와 2개의 레퍼런스 필드 left, right를 가지는데 left와 right만 연결시키고 나머지는 null 처리

이진트리 속성

• 레벨 k에 있는 최대 노드 수 $2^{k-1}$
• 높이가 h인 포화이진트리에 있는 노드 수 $2^h-1$
• N개의 노드를 가진 완전 이진트리 높이 $log_2(N+1)$
• 높이가 h인 완전이진트리에 존재할 수 있는 최대 노드 수 $2^{h-1}$~$2^h-1$

배열 저장

배열에 저장하면 노드의 부모노드와 자식노드가 배열의 어디에 저장되어 있는지 다음과 같은 규칙을 통해 쉽게 알 수 있다 (단 트리에 N개의 노드가 있다고 가정)

• a[i]의 부모노드는 a[i/2]에 있음 (단 i > 1)
• a[i]의 왼쪽 자식노드는 a[2i] (단 2i ≤ N)
• a[i]의 오른쪽 자식노드는 a[2i+1]에 있음 (단, 2i+1 ≤ N)

이진트리를 위한 클래스

Node 클래스

// generic 타입 Key는 Comparable 메소드를 통해 2개 키를 비교)을 구현한 클래스만 들어올 수 있게 하는 것
// Comparable 인터페이스는 compareTo() 메소드 통해 2개 키를 비교하기 위해서
public class Node<Key extends Comparable<Key>> {
    private Key item;
    private Node<Key> left;
    private Node<Key> right;
    public Node(Key newItem, Node lt, Note rt) {
        item = newItem; left = lt; right rt;}
    public Key getKey() {return item;}
    public Node<Key> getLeft() {return left;}
    public Node<Key> getRight() {return right;}
    public void setKey(Key newItem) {item = newItem;}
    public void setLeft(Node<Key> lt) {left = lt;}
    public void setRight(Node<Key> rt) {right = rt;}
}

BinaryTree 클래스

// generic 타입 Key는 Comparable을 구현한 클래스만 들어올 수 있게 하는 것
import java.util.*;
public class BinaryTree<Key extends Comparable<Key>> {
    private Node root;
    public BinaryTree() {root = null;}
    public Node getRoot() {return root;}
    public void setRoot(Node newRoot) {root = newRoot;}
    public boolean imsEmpty() {return root == null;}
    // preorder(), inorder(), postorder(), levelorder() 순회 메소드 선언
    // size(), hegith(), isEqual() 기본 메소드 선언
}

이진트리의 연산

• 이진트리에서 수행되는 기본 연산들은 트리를 순회하며 이루어진다.
• 순회는 항상 트리의 루트노드부터 시작한다.
• 전위, 주위, 후위 순회는 트리를 순회하는 중에 노드를 방문하는 시점에 따라 구분한다.
  (노드 방문 시 지나치는 지, 나중에 방문하는 지 따라 구분)
• 트리의 각 노드를 반드시 1번씩 방문해야 순회가 종료된다.
• 표현할 때 사용하는 것 중 N은 노드 방문 V는 방문을 의미, L은 왼쪽, R은 오른쪽 서브트리로 순회 진행한다는 뜻

전위순회(Preorder Traversal)

• 노드 x에 도착했을 때 x를 먼저 방문
• 그 다음에 x의 왼쪽 자식노드로 순회 계속
• x의 왼쪽 서브트리의 모든 노드들을 방문한 후에는 x의 오른쪽 서브트리의 모든 후손 노드들을 방문
• 각 서브트리의 방문은 동일한 방식으로 순회
• 전위순회 순서를 NLR 또는 VLR로 표현

Public void preorder(Node n) {
    if (n != null) {
        System.out.print(n.getKey() + " ");
        preorder(n.getLeft());
        preorder(n.getRight());
    }
}

중위순회(Inorder Traversal)

• 노드 x에 도착하면 x의 방문을 보류하고 x의 왼쪽 서브트리로 순회를 진행
• 왼쪽 서브트리의 모든 노드들을 방문한 후에 x를 방문
• x를 방문한 후에는 x의 오른쪽 서브트리를 같은 방식으로 방문
• 중위순회 순서를 LNR 또는 LVR로 표현

public void inorder(Node n) {
    if (n != null) {
        inorder(n.getLeft());
        System.out.print(n.getKey() + " ");
        inorder(n.getRight())
    }
}

후위순회(Postorder Traversal)

• 노드 x에 도착하면 x의 방문을 보류하고 x의 왼쪽 서브트리로 순회를 진행
• x의 왼쪽 서브트리를 방문한 후에는 x의 오른쪽 서브트리를 같은 방식으로 방문
• 마지막에 x를 방문
• 후위순회 순서를 LRN 또는 LRV로 표현

public void postorder(Node n) {
    if (n != null) {
        postorder(n.getLeft());
        postorder(n.getRight())l
        System.out.print(n.getKey() + " ");
    }
}

레벨순회(Levelorder Traversal)

루트노드가 있는 최상위 레벨부터 시작하여 각 레벨마다 좌에서 우로 노드들을 방문

public void levelorder(Node root) {
    Queue<Node> q = new LinkedList<Node>();
    Nodet t;
    q.add(root)
    while(!q.isEmpty()) {
            t = q.remove();
            System.out.print(t.getKey() + " ");
            // 제거된 노드의 왼쪽 자식이 null이 아니면 큐에 왼쪽 자식 삽입
            if (t.getLeft() != null)
                q.add(t.getLeft());
            // 제거된 노드의 오른쪽 자식이 null이 아니면 큐에 오른쪽 자식 삽입
            if (t.getRight() != null)
                q.add(t.getRight());
        }
}

기타 이진트리 연산

• size() : 트리의 노드 수 계산 (후위 순위 기반)

  • 트리의 아래에서 위로 각 자식의 후손 노드 수를 합하며 올라가는 과정을 통해 수행되며, 최종적으로 루트 노드에서 총 합을 구함

  • 트리의 노드수 = 1(루트노드 자신) + (루트노드의 왼쪽 서브트리에 있는 노드 수) + (루트노드의 오른쪽 서브트리에 있는 노드 수)

    public int size(Node n) {
      if (n == null)
          return 0;
      else
          return (1 + size(n.getLeft()) + size(n.getRight()));
    }

• height() : 트리의 높이 계산 (후위 순위 기반)

  • 아래에서 위로 두 자식을 각각 루트노드로 하는 서브트리의 높이를 비교하여 보다 큰 높이에 1을 더하는 것으로 자신의 높이를 계산하며, 최종적으로 루트노드의 높이가 트리의 높이가 됨

  • 트리의 높이 = 1(루트노드 자신) + max(루트의 왼쪽 서브트리의 높이, 루트의 오른쪽 서브트리의 높이)

    public int height(Node n) {
      if (n == null)
          return 0;
      else
          return (1 + Math.max(height(n.getLeft()), height(n.getRight())));
    }

• isEqual() : 2개의 이진트리에 대한 동일성 검사 (전위 순위 기반)

  • 2개의 이진트리를 비교하는 것은 다른 부분을 발견하는 즉시 비교 연산을 멈추기 위해 전위순회 방법을 사용

  • 전위순회 과정에서 다른 점이 발견되는 순간 false를 리턴

  • 둘다 null이면 true 리턴, 한 쪽만 null이면 트리가 다른 것으로 false를 리턴

    public static boolean isEqual(Node n, Node m) {
      if(n == null || m == null)
          return n == m;
      if (n.getKey().compareTo(m.getKey()) != 0)
          return false;
      return (isEqual(n.getLeft(). m.getLeft()) && isEqual(n.getRight(), m.getRight())); 
    }

수행시간

• 앞서 설명된 각 연산은 트리의 각 노드를 한 번씩만 방문하므로 O(N) 시간이 소요

요약

• 트리는 계층적 자료구조로 배열이나 연결리스트의 단점을 보완하는 자료 구조
• 왼쪽자식-오른쪽형제 표현은 노드의 차수가 일정하지 않은 일반적인 트리를 구현하는 매우 효율적인 자료 구조
• 포화이진트리는 각 내부노드가 2개의 자식노드를 가지는 트리
• 완전이진트리는 마지막 레벨을 제외한 각 레벨이 노드들로 꽉 차있고, 마지막 레벨에는 노드들이 왼쪽부토 빠짐없이 채워진 트리이다.
• 포화이진트리는 완전이진트리이다.
• 이진트리 순회방법
  • 전위순회(NLR)
  • 중위순회(LNR)
  • 후위순회(LRN)
  • 레벨 순회 : 큐 자료구조를 사용해서 구현
• 이진트리 높이 계산과 노드 수의 계산에는 후위순회가 적합, 이진트리의 비교에는 전위순회가 적합
• 이진트리의 높이 및 노드 수의 계산, 각 트리 순회, 동일성 검사는 트리의 모든 노드들을 방문해야 하므로 각각 O(N) 시간이 소요

[출처] 경기대학교|소프트웨어중심대학산업