자료구조 - 비선형 구조: 트리 (미완성)

트리

트리(Tree) 라고 하면 대부분의 사람들은 나무를 떠올릴것이다. 하지만 우리는 미래의 개발자이니 자료구조 트리를 먼저 생각해야 한다. 재미 없어도 이렇게라도 세뇌 해서 하다보면 재밌어진다 ㅋㅋㅋㅋ

---

트리 개요

트리는 이름에서도 알 수 있듯이 나무 형태인 그래프 자료구조를 말한다. 우선 기본적인 형태를 살펴보자.

• 루트 노드: 트리의 최상단에 위치한 노드
• 간선: 노드와 노드를 잇는 선, 엣지 라고도 한다.
• 내부 노드: 루트 및 단말 노드가 아닌 내부에 존재하는 노드
  • ex) 2, 3, 4, 6은 내부 노드에 해당한다.
• 단말 노드: 자식이 없는 노드
• 부모 노드: 자신보다 하위 노드를 갖는 노드
  • ex) 7번 8번 노드의 부모 노드는 4번 노드이다.
• 자식 노드: 자신보다 상위 노드를 갖는 노드
  • ex) 4번의 자식 노드는 7번 8번 노드이다.
• 형제 노드: 부모 노드가 같은 노드
  • ex) 5번, 6번 노드는 형제 노드다.
• 노드 사이즈: 모든 노드의 개수
  • ex) 해당 트리의 노드 사이즈는 9다.
• 노드 뎁스: 해당 노드를 가기위해 거치는 간선의 개수
  • ex) 1번 노드의 뎁스는 0이고, 9번 노드의 뎁스는 3이다.
• 노드의 레벨: 같은 뎁스를 갖는 노드들의 집합
  • ex) 4레벨인 노드는 7, 8, 9번 노드이다.

이정도면 트리의 구조에 대한 설명이 끝이난다.

---

트리 특징

1. 계층 구조를 갖는 그래프다.
2. 노드에서 노드로 이동할 때 갈 수 있는 경로는 유일하다.
3. 반드시 하나의 루트노드가 존재해야 한다.
4. 그래프의 사이클 순회가 불가능하다.

---

트리 종류

트리의 종류에는 상당히 여러가지가 있다. 트리 종류는 크게 이진트리, 비 이진트리  가 있다. 

1 - 1. 이진 트리(Binary Tree): 단말 노드가 아닌 모든 노드의 자식노드가 2개 이하인 트리 그래프 

이진 트리의 경우 2^(최대 Level ) - 1 만큼의 노드를 가질 수 있다. (단, 레벨이 0인 경우 1개의 노드를 갖는다)

그렇다면 이진트리의 종류에 대해 살펴보자.

1. 포화 이진 트리(Perfect binary tree)
   
   단말 노드를 제외한 모든 노드가 2개의 자식 노드를 갖는 트리를 말한다.
2. 완전 이진 트리(Complete binary tree)
   
   단말 노드를 제외한 모든 노드가 2개 이하의 자식 노드를 가지며, 자식 노드는 좌측부터 채워져 있어야 한다.
   
   
3. 정 이진 트리(Full binary tree)
   
   단말 노드를 제외한 모든 노드가 0개 혹은 2개의 자식노드를 갖는 트리를 말한다.
   
   
4. 편향 이진 트리(Skewed binary tree)
   
   루트부터 단말노드 까지 모든 노드가 한 방향으로 뻗어있는 트리를 말한다.
   
   
5. 이진 탐색 트리(Binary search tree)
   
   이진 트리 중 가장 중요한 파트라 생각한다. 특징은 다음과 같다. 주요 용도는 데이터 검색에 주로 사용한다.
   1. 각 노드에 값이 존재한다.
   2. 값들은 전순서가 존재한다.
   3. 형제 노드 중 좌측 노드는 부모 노드보다 값이 작아야 하고, 우측 노드는 부모보다 값이 커야 한다.
   4. 모든 서브 트리는 이진 탐색 트리다.

 

이진 트리는 그래프를 프로그래밍 할 때도 큰 이점을 얻게된다. 
현재 노드의 부모 노드를 X라고 했을 때, 노드가 배열에 존재하는 위치는 다음과 같다.

좌측 자식노드 = X * 2
우측 자식노드 = X * 2 + 1

위 사진과 같이 단순 연산으로 배열로 나타내는것이 가능하다. 이것은 어떤 노드가 부모 노드인지 알 수 있다는것을 의미한다.
이런 방식을 통해 Heap Sorting을 구현할 수 있다.

하지만 단점으로 낭비되는 메모리가 많다는점을 들 수 있다. 사진의 하단에 완성된 배열을 살펴보자. 해당 배열에서 레벨이 3인 노드는 값이 2인 노드 하나밖에 없다. 이 하나를 배열에 표현하기 위해 7개의 메모리를 잡아먹은 것이다.

속도적인 측면에서 효율은 좋지만, 메모리적 측면에서 효율이 좋지 않다.

---

1 - 2. 이진 탐색 트리

이진 탐색 트리는 기존 트리의 탐색 속도를 개선할 수 있는 장점이 있다. 주로 데이터 검색에 사용된다.

이진 탐색 트리가 기존 트리보다 탐색 속도에서 이점을 얻는 이유는

1. 형제 노드 중 좌측 노드는 부모 노드보다 값이 작아야 하고, 우측 노드는 부모보다 값이 커야 한다.

여기에서 시작된다. 다음 사진을 보자.

위와 같은 이진 탐색 트리가 존재한다. 노드의 좌측은 자신보다 작은값이, 우측은 자신보다 큰 값이 존재한다. 

예시로 12를 찾는 노드 탐색 과정을 살펴보자.

1. 루트 노드에서 부터 시작하며, 현재 노드의 값은 5이다.
2. 찾아야 하는 값은 12이고, 자신보다 크므로 좌측 노드는 무시한다. (1, 3, 4번 노드를 검색에서 제외시킨다.)
3. 9 값을 갖는 노드로 이동한다.
4. 찾아야 하는 값은 12이고, 자신보다 크므로 좌측 노드는 무시한다. (6번 노드를 검색에서 제외시킨다.)
5. 12 값을 갖는 노드로 이동한다.
6. 찾아야 하는 값이 12이므로 현재 노드를 반환한다.

이진 탐색 트리가 아닌경우를 살펴보자.

1. 루트 노드에서 부터 시작하며, 현재 노드의 값은 5이다.
2. 다음 노드는 3이며, 12가 아니다.
3. 다음 노드는 9이며, 12가 아니다.
4. 다음 노드는 1이며, 12가 아니다.
5. 다음 노드는 4이며, 12가 아니다.
6. 다음 노드는 6이며, 12가 아니다.
7. 다음 노드는 12이며, 찾아야 하는 값과 일치하므로 노드를 반환한다.

두 과정을 비교했을 때, 거쳐가는 노드의 수는 루트노드를 포함해 이진 탐색 트리는 3개, 아닌 경우는 7개이다. 이런 이유로 이진 탐색 트리는 데이터 탐색 효율에 큰 이점을 갖게 된다.

추가로, 이진 탐색 트리를 만들기 위해선 우선 정렬된 배열이 필요하다. 또, 정렬된 배열이 오름차순 혹은 내림차순에 맞춰 코드를 변경해야 한다. 구현된 코드는 다음과 같다.

class Main {
  public static void main(String[] args) {
    int[] sortArray = {1,3,4,5,6,9,10,12};
    
    int BSTLength = 1;
    
    while (BSTLength <= sortArray.length) {
      BSTLength *= 2;
    }
    
    int[] BST = new int[BSTLength];
    
    setBST(sortArray, BST, 0, sortArray.length - 1, 1);
    
    for(int i : BST) {
      System.out.print(i + " ");
    }

    System.out.println();
    getData(BST, 10, 1);
  }
  
  public static void setBST(int[]sortArray, int[] BST, int start, int end, int index) {
    int mid = (start + end) / 2;
    
    BST[index] = sortArray[mid];
    
    if (start < mid)
      setBST(sortArray, BST, start, mid - 1, index * 2);
    
    if (mid < end)
      setBST(sortArray, BST, mid + 1, end, index * 2 + 1);
  }
  
  public static void getData(int[] BST, int target, int index) {
    if(target == BST[index]) {
      System.out.println("Data found: " + BST[index]);
      
      return;
    }
    
    if(BST[index] < target) {
      System.out.println("target bigger than data: " + BST[index]);
      getData(BST, target, index * 2 + 1);
    }
    else {
      System.out.println("target smaller than data: " + BST[index]);
      getData(BST, target, index * 2);
    }
  }
}

/*
출력:
0 5 3 9 1 4 6 10 0 0 0 0 0 0 0 12 
target bigger than data: 5
target bigger than data: 9
Data found: 10
*/

---

1 - 3. 세그먼트 트리

Segment Tree (구획 나무), 즉 범위를 저장하기 위한 트리를 말한다.

우선 세그먼트 트리를 구현하기 위해서는 이진 트리라는 선행 조건이 만족되어야 한다. 배열을 이진트리 형태로 만들어야 한다. 바로 아래처럼.

1 부터 8까지 원소를 갖는 정수형 배열이 있다 가정했을 때, 세그먼트 트리로 배열을 나타내면 위 사진과 같다. 말단 노드는 기존의 배열을, 부모 노드는 자식노드들의 범위를 나타내 세그먼트 트리를 작성할 수 있다.

하지만 우리는 이 상태로 세그먼트 트리를 활용하지 않는다. 단말 노드를 제외한 모든 노드는 자식노드의 합을 값으로 가진 상태로 바꿔 사용해야 한다. [1, 2, 3, 4, 5, 6] 원소를 갖는 배열을 세그먼트 트리로 나타내면 다음과 같다.

 

[여기서부터 작성]

---

2. 비 이진 트리(Non-binary Tree): 이진 트리에 해당하지 않는 모든 트리 그래프, 그냥 트리 라고도 부른다.

트리 중, 이진트리에 해당하지 않는 모든것을 말한다.

 

---