자료구조, 트리

자료구조란?

데이터를 처리하는 여러 방법들을 정의한 자료의 집합

자료구조를 왜 사용하나?
데이터를 사용하는데 효율성을 높이기 위해

Tree

노드로 이루어진 자료 구조, 비선형 자료구조이며 계층적 관계를 표현한다.

tree 특징

1. tree는 하나의 루트 노드를 갖는다.
2. 루트 노드는 0개 이상의 자식 노드를 갖는다.
3. 자식 노드도 0개 이상의 자식 노드를 갖는다.
4. 노드들과 노드들을 연결하는 간선(edge)로 구성되어있다.
5. 트리에는 cycle이 존재하지 않는다.
   사이클이란? 시작 노드 -> B -> C -> 시작노드로 돌아오는 것
   
6. 트리는 하나의 연결 그래프로 트리의 노드는 self-loop 안된다.
   
7. n개의 노드를 갖는 트리는 항상 n-1개의 간선을 갖는다.
8. 모든 자식 노드는 한 개의 부모 노드만을 갖는다.

트리 용어

• 루트 노드 - 부모가 없는 단 하나의 루트 노드 ex) A
• 단말 노드 - 자식이 없는 노드 = terminal노드 ex) H, I, J, F, G
• 내부 노드 - 단말 노드가 아닌 노드 ex) A, B, C, D, E
• 간선 - 노드를 연결하는 선
• 형제 (sibling) - 같은 부모 노드를 갖는 노드들 ex) H,I / F,G
• 노드의 깊이 (depth) - 루트 노드에서 어떤 노드로 가기 위해 거쳐야 하는 간선 수 ex) D의 depth : 2
• 노드의 레벨 - tree의 특정 깊이를 가지는 노드의 집합
• 노드의 차수 (degree) - 자식 노드의 개수
• 트리의 차수 - 트리의 최대 차수 ex) 위 트리의 차수는 2

트리 종류

이진트리 (Binary Tree)
각 노드가 최대 2개의 자식을 갖는 트리
--> 전위순회, 중위순회, 후위순회를 통해 탐색 가능

L -> left, V -> visit, R -> right
1. 중위순회 LVR 탐색 즉, 왼쪽부터 탐색
출력 : D B H E A F C I G

2. 전위순회 VLR 탐색 즉, 위에서 왼쪽으로
   출력 : A B D E H C F G I
   완전이진트리

3. 후위순회 LRV 탐색 즉, 왼쪽 서브트리에서 오른쪽 서브트리에서 루트노드
   출력 : D H E B F I G C A

완전 이진 트리 (Complete Binary Tree)

특징
1. 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져있다.
2. 마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 한다.
3. 마지막 레벨h 에서 1~2h-1 개의 노드를 가질 수 있다.
4. 배열을 사용해 효율적으로 표현 가능하다.

전 이진 트리 (Full Binary Tree)
모든 노드가 0 또는 2개의 자식 노드를 갖는 트리

포화 이진 트리 (Perfact Binary Tree)
특징
1. 모든 레벨이 노드로 꽉 차 있는 트리
2. 전 이진트리 성질을 만족한다.
3. 모든 말단 노드가 동일한 깊이 또는 레벨을 만든다.
4. 트리의 노드 개수가 정확히 2^k-1개, k는 높이

이진 탐색 트리 (Binary Search Tree)

이진탐색 트리 기준
1. 각 노드에 중복되지 않는 key가 있다.
2.루트 노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져있다. 부모 > 노드
3. 루트 노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다 부모 < 노드
4. 좌우 서브 트리도 모두 이진 탐색 트리여야 한다.

특징
1. 기존 이진트리보다 탐색이 빠르다.
탐색 연산. 트리의 높이가 h라면 0(h)의 시간 복잡도를 가진다.

*이진 탐색 트리의 탐색

1. 루트 노드의 key와 찾고자 하는 값을 비교한다. 찾고자 하는 값이라면 탐색 종료
2. 찾고자 하는 값이 루트 노드의 key보다 작다면 왼쪽 서브 트리 탐색
3. 찾고자 하는 값이 루트 노드의 key보다 크다면 오른쪽 서브 트리 탐색

이진 탐색 트리의 삽입

1. 삽입할 값을 루트 노드와 비교해 같다면 오류 발생. 중복 불허용
2. 삽입할 값이 루트 노드의 key보다 작다면 왼쪽 서브 트리를 탐색해 비어있다면 추가, 비어있지 않다면 다시 값 비교한다.
3. 삽입할 값이 루트 노드의 key보다 크다면 오른쪽 서브 트리를 탐색해 비어있다면 추가, 비어있지 않다면 다시 값 비교한다.

이진 탐색 트리의 삭제
1.삭제하려는 노드가 단말노드일 경우

2. 삭제하려는 노드의 서브 트리가 하나인 경우

3. 삭제하려는 노드의 서브트리가 2개인 경우
--> 2가지의 방법이 있으나 오른쪽 서브 트리의 가장 작은 자손을 해당 노드의 자리로 올리는 것을 많이 사용