트리

1. 트리

가. 트리의 개념

• 비선형 자료 구조이다.
• 원소들 간에 1:n 관계를 가지는 자료구조이다.
• 원소들 간에 계층 관계를 가지는 계층형 자료구조이다.
• 상위원소에서 하위원소로 내려가면서 확장되는 트리모양의 구조이다.

나. 트리 구조

노드

• 트리의 원소
• 한개 이상의 노드로 이루어진 유한 집합이며 다음 조건을 만족한다.

  • 루트 : 노드 중 최상위 노드
  • 나머지 노드들은 N개의 분리집합으로 분리될 수 있다. 이것을 서브트리라고하다.

간선
노드와 노드를 연결하는 선으로 부모와 자식 노드를 연결한다.

다. 용어

형제 노드 : 같은 부모노드의 자식 노드들
조상 노드 : 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드
서브트리 : 부모노드와 연결된 간선을 끊었을 때 생성되는 트리
자손 노드 : 서브 트리에 있는 하위레벨의 노드
차수(degree) : 노드에 연결된 자식 노드의 수
트리의 차수 : 트리에 있는 노드 중에서 가장 큰 값
단말 노드 : 차수가 0인 노드, 자식 노드가 없는 노드
노드의 높이 : 루트에서 노드에 이르는 간선의 수. 노드의 레벨
루트레벨 : 0
트리의 높이 : 트리에 있는 노드의 높이중에서 가장 큰 값

2. 이진트리

가. 이진트리의 개념

• 차수가 2인 트리
• 각 노드가 자식노드를 최대한 2개 까지만 가질 수 있는 트리이다.
• 모든 노드들이 최대 2개의 서브트리를 갖는 특별한 형태의 트리이다.

나. 특징

• 높이 i에서 노드의 최대 개수는 2^i 개이다.
• 높이가 h인 이진트리가 가질 수 있는 노드의 최소개수는 h+1개 , 최대는 2^h+1 -1 개이다.

다. 이진 트리의 종류

포화 이진 트리
모든 레벨에 노드가 포화상태로 차 있는 이진트리
높이가 h일때, 최대 노드 개수인 2^h+1 -1 노드를 가진 이진트리

완전 이진 트리
높이가 h이고 포화 이진트리의 노드번호 1번 부터 n번까지 빈자리가 없는 트리이다.

편향 이진 트리
높이 h에 대해, 최소 개수의 노드를 가지면서 한쪽방향의 자식 노드만을 가진 이진 트리이다.

라. 배열을 이용한 이진 트리의 표현

• 트리를 배열로 표현하는 것이다.
• 이진 트리에 각 노드 번호를 다음과 같이 부여한다.
• 루트의 번호를 1번으로해서, 각 레벨n에 있는 노드에 대해 왼쪽에서 오른쪽까지 번호를 차례대로 구현한다.

특징
부모의 노드 번호는 2로 나누면 된다.
단점
사용하지않는 배열 원소에 대해 메모리 낭비가 난다.

3. 트리 사용

가. 트리 탐색

• 트리, 그래프에서 각 노드를 중복되지 않게 전부 방문하려고 한다.
• 선형 구조 처럼 선후 관계를 알수 없다. 따라서 특별한 방법이 필요하다.
• 비선형 자료구조를 완전 탐색하기 위해서는 다음과 같은 방법을 사용한다.

• 너비 우선 탐색
• 깊이 우선 탐색

나. 너비 우선 탐색 (BFS)

• 루트 노드의 자식노드를 모두 차례로 방문한 후에, 방문했던 자식 노드 들을 기준으로하여 다시 해당 노드의 자식노드들을 차례로 방문하는 방식이다.
• 인접한 노드들에 대해 탐색한후, 차례로 다시 너비 우선 탐색을 하기 때문에 선입 선출형태의 자료구조인 큐를 활용한다.

큐생성 -> 
루트노드를 큐에 삽입 ->
큐가 비어있지 않은 동안 :
    T : 큐의 첫번째 원소
    T 를 방문하고,
        for( T와 연결된 모든 간선에 대해 ){
            U : T의 자식 노드
            U를 큐에 삽입 하기
        }

다. 깊이 우선 탐색 (DFS)

• 루트 노드에서 출발하여 한 방향으로 갈 수 있는 경로가 있는 곳 까지 탐색하다가 갈수 없게 되면 가장 마지막에 만났던 갈림길 간선이 있는 노드로 되돌아와서 다른 방향의 노드로 탐색을 반복하여 모든 노드를 방문하는 순회방법
• 마지막의 갈림길의 노드로 되돌아 가야하기 때문에 재귀 또는 스택으로 구현다.

dfs(v){
    v 방문
    for(v의 모든 자식 노드 w) {
        dfs(w)
    }
}

라. 순회

• 트리의 노드를 체계적으로 방문하는 것이다.
• 3가지의 기본 순회 방법

  전위 순회 VLR : 자신(부모)를 먼저 처리하고, 자식 노드를 좌우 순서로 방문한다.

  중위 순회 LVR : 왼쪽자식 -> 자신(부모) -> 오른쪽 자식노드

  후위 순회 LRV : 좌 -> 우 -> 자신

마. 수식트리

• 수식을 표현하는 이진트리
• 수식 이진트리라고도 한다.
  • 연산자 : 루트 노드 / 가지 노드
  • 피연산자 : 잎노드

---

힙

1. 힙

가. 개요

완전 이진 트리에 있는 노드 중에서 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조

나. 최대 힙

• 키값이 가장 큰 노드를 찾기 위한 완전 이진트리
• 부모 노드의 키값 > 자식 노드의 키값
  • 루트 노드 : 키 값이 가장 큰 노드

다. 최소 힙

• 키 값이 가장 작은 노드를 찾기 위한 완전 이진트리
• 부모 노드의 키값 < 자식 노드의 키 값
  • 루트 노드 : 가장 키값이 작은 노드

라. 힙에서의 연산

• 루트노드의 원소만을 삭제 할 수 있다.
• 종류에 따라 최대값, 최소 값을 구할 수 있다.

마. Java에서 활용

• 우선순위 큐

  • java.util.Priority.Queue()
    원소들의 natual Ordering에 따라 Heap 유지한다.
    따라서 모든 원소는 Comparable 인터페이스를 유지해야한다.
  • Comparator comparator - 명시된 구현에 따라 원소들의 순서를 유지한다.