[자료구조] 트리 (Tree)

1. 트리 (Tree)

• 계층적인 구조를 표현할 때 사용하는 자료구조
  

  

• 관련 용어
  • 루트 노드 (root node)
    • 부모가 없는 최상위 노드
  • 단말 노드 (leaf node)
    • 자식이 없는 노드
  • 크기 (size)
    • 트리에 포함된 모든 노드의 개수
  • 깊이 (depth)
    • 루트 노드부터의 거리
  • 높이 (height)
    • 깊이 중 최댓값
  • 차수 (degree)
    • 각 노드의 (자식 방향) 간선 개수
• 기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1개

2. 이진 탐색 트리 (Binary Search Tree)

• 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조
• 특징
  • 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
    • 부모 노드보다 왼쪽 자식 노드가 작음
    • 부모 노드보다 오른쪽 자식 노드가 큼
      

      

• 예시
  • 이진 탐색 트리가 이미 구성되어 있다고 가정하고 데이터 조회하는 과정
  • 찾고자 하는 원소: 37
  • [Step 1] 루트 노드부터 방문하여 탐색
    1. 현재 노드와 찾는 원소 37 비교
    2. 찾는 원소가 더 크므로 오른쪽 방문
       

       

  • [Step 2] 현재 노드와 값 비교
    1. 현재 노드와 찾는 원소 37 비교
    2. 찾는 원소가 더 작으므로 왼쪽 방문
       

       

  • [Step 3] 현재 노드와 값 비교
    1. 현재 노드와 찾는 원소 37 비교
    2. 원소를 찾았으므로 탐색 종료
       

       

  • 위와 같이 이상적인 경우의 시간 복잡도는 O(logN)
  • 최악의 경우, O(N)

3. 트리의 순회 (Tree Traversal)

• 트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법
  • 트리의 정보를 시각적으로 확인 가능
• 대표적인 트리 순회 방법
  • 전위 순회 (pre-order traverse)
    • 루트 먼저 방문
    • 루트 - 왼쪽 자식 - 오른쪽 자식
  • 중위 순회 (in-order traverse)
    • 왼쪽 자식을 방문한 뒤 루트 방문
    • 왼쪽 자식 - 루트 - 오른쪽 자식
  • 후위 순회 (post-order traverse)
    • 오른쪽 자식을 방문한 뒤 루트 방문
    • 왼쪽 자식 - 오른쪽 자식 - 루트
• 예시
  

  

  • 전위 순회 (pre-order traverse)
    
    • A → B → D → E → C → F → G
  • 중위 순회 (in-order traverse)
    • D → B → E → A → F → C → G
  • 후위 순회 (post-order traverse)
    • D → E → B → F → G → C → A
• 예제
  

  private Node<E> root;
  
  // 전위 순회 (Pre-order Traversal)
  private Queue<E> preOrder(Node<E> link){
      Queue<E> res = new Queue<E>();
  
      if(link != null) {
          res.enqueue(link.getData());
      }
  
      if(link.getLeftChild() != null) {
          res.concat(preOrder(link.getLeftChild()));
      }
  
      if(link.getRightChild() != null) {
          res.concat(preOrder(link.getRightChild()));
      }
  
      return res;
  }
  
  // 중위 순회 (In-order Traversal)
  private Queue<E> inOrder(Node<E> link) {
      Queue<E> res = new Queue<E>();
  
      if(link.getLeftChild() != null) {
          res.concat(inOrder(link.getLeftChild()));
      }
      if(link != null) {
          res.enqueue(link.getData());
      }		
      if(link.getRightChild() != null) {
          res.concat(inOrder(link.getRightChild()));
      }
  
      return res;
  }
  
  // 후위 순회 (Post-order Traversal)
  private Queue<E> postOrder(Node<E> link) {
      Queue<E> res = new Queue<E>();
  
      if(link.getLeftChild() != null) {
          res.concat(postOrder(link.getLeftChild()));
      }
      if(link.getRightChild() != null) {
          res.concat(postOrder(link.getRightChild()));
      }
      if(link != null) {
          res.enqueue(link.getData());
      }
  
      return res;
  }​