트리
비선형구조(선형구조(스택, 큐 등)는 데이터의 삽입 및 출력 등에, 비선형구조는 표현에 초점을 둠)
계층 모델
사이클 없음
모든 자식 노드는 하나의 부모 노드만 가짐
관련 용어
- 노드(node) : 데이터를 구성하고 있는 각 요소
- 루트 노드(root node) : 트리 구조에서 최상위 노드
- 단말 노드(leaf node) : 자식 노드가 없는 노드
- 간선(ddge) : 노드와 노드를 연결하는 선. 노드가 n개인 트리의 간선 개수는 n-1개
- 서브트리(sub tree) : 트리에 속하는 트리
- 형제(sibiling) : 같은 부모를 가지는 노드
- 레벨(level) : 트리의 각 층, 루트 노드로부터 얼마나 떨어져 있는지에 대한 값으로, 루트 노드의 레벨은 0
- 차수(degree) : 노드가 갖는 자식의 수
- 깊이(depth) : 루트 노드에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
- 높이(height) : 루트 노드에서 가장 멀리 있는 노드의 깊이
트리 순회 방식
- 루트 노드를 언제 방문하는가에 따라 정해짐
- 전위 순회 : 부모노드 → 좌측 자식노드 → 우측 자식노드
- 중위 순회 : 좌측 자식노드 → 부모노드 → 우측 자식노드
- 후위 순회 : 좌측 자식노드 → 우측 자식노드 → 부모노드
이진트리(Binary tree)
- 자식 노드가 2개 이하인 트리 (그냥 '트리'라고만 하면 자식노드 개수 제한x)
- 노드가 비어 있는 경우, 공집합으로 취급
편향 이진트리(Skewed binary tree)
- 차수가 1로만 이루어진 경우
- 단말 노드 탐색 시 모든 데이터를 탐색해야 하므로 시간복잡도 O(n)으로 비효율적
전 이진트리(Full binary tree)
- 루트 노드를 중심으로 나눠지는 서브트리가 이진트리이며, 서브트리의 서브트리 또한 이진트리인 트리
- 자식 노드가 0개 또는 2개인 경우
포화 이진트리(Perfect binary tree)
- 모든 레벨이 꽉 찬 이진트리
- 즉, 모든 단말 노드의 레벨이 동일한 이진트리
- 포화 이진트리의 노드 개수는 2^h-1개
완전 이진트리(Complete binary tree)
- 위에서 아래로, 좌측에서 우측으로 노드가 채워진 형태
- 마지막 레벨을 제외한 레벨은 노드가 모두 채워져야 함
- 마지막 레벨의 경우 끝까지 채울 필요는 없으나 좌측부터 채워져 있어야 함
- n개의 노드를 저장할 수 있는 완전 이진트리의 높이는 log n
- 힙(heap)이 완전 이진트리의 일종
이진 탐색 트리(Binary search tree)
- 데이터 탐색 시 주로 적용
- 조건1 : 부모 노드를 기준으로 좌측 서브트리의 모든 노드 값은 부모 노드의 값보다 작아야 하며,
- 조건2 : 우측 서브트리의 모든 노드 값은 부모 노드의 값보다 커야 함
- 조건3 : 중복된 값을 갖는 노드는 없음
- 이진 탐색 트리의 시간복잡도
- 이진 탐색 트리의 탐색 시간복잡도는 O(logn)
- 편향된 트리의 경우 시간복잡도가 O(n)인데, 개선해주는 AVL tree, RedBlack tree가 있으며, 이들은 최악의 경우에도 O(logn)의 시간복잡도를 유지
- 이진 탐색 트리의 연산에 걸리는 시간은 h(높이)에 비례하기 때문에, 편향된 트리일 수록 비효율적이고 균형 잡힌 트리일 수록 효율적 → 편향된 트리의 경우 노드의 개수가 n개일 때 높이도 n, 균형잡힌 트리인 경우 노드의 개수가 n개일 때 높이가 log(n)
- 이진 탐색 트리의 데이터 탐색
- 현재 노드의 값이 찾는 데이터보다 크면 우측, 작으면 좌측으로 이동하며 찾는 방식으로, 배열에 비해 탐색 속도를 개선할 수 있음
- 중위 순회를 통해 오름차순으로 노드를 얻을 수 있음
- 이진 탐색 트리의 데이터 삽입
- 트리에서 삽입할 값의 위치를 탐색하여 삽입 (삽입되는 값이 루트 노드보다 작으면 좌측, 크면 우측으로)
- 새로 삽입되는 값은 항상 단말 노드에 삽입함
- 노드의 값은 유일해야 하므로 중복 삽입 불가 -> 탐색에 실패한 위치가 데이터를 삽입할 위치
- 이진 탐색 트리의 데이터 삭제
- 자식노드가 없는 경우 : 즉 단말 노드인 경우 → 그냥 삭제!
- 자식노드가 1개인 경우 : 삭제할 노드x와 자식노드 위치 swap, 자식노드 위치로 옮겨진 x 삭제 (즉, 단말 노드 삭제)
- 자식노드가 2개인 경우
- 삭제할 노드 x의 좌측 서브트리에서 가장 큰 값, 혹은 우측 서브트리에서 가장 작은 값과 x의 위치를 swap, 단말 노드로 이동한 x를 삭제 → 이렇게 할 경우 기준이 되는 노드의 좌측 서브트리는 작은 값, 우측 서브트리는 큰 값이 있어야 한다는 규칙을 유지할 수 있음
- 18을 지우고자 할 때, 어떻게 해야할까?
1. 좌측 서브트리에서 가장 큰 값 찾기
→ 12와 18의 위치 swap, 단말로 이동된 18 삭제
2. 우측 서브트리에서 가장 작은 값 찾기
→ 22를 18의 위치로 이동
→ 23을 22의 위치로 이동
→ 18을 23의 위치로 이동, 단말로 이동된 18 삭제
이진트리의 순차 표현(배열로 표현)
트리를 배열로 표현하는 경우, 편의상 0이 아닌 1부터 시작함. 즉, 루트노드의 인덱스는 1
부모노드의 인덱스가 i일 때, 좌측 자식노드의 인덱스는 i * 2, 우측 자식노드의 인덱스는 i * 2 + 1
자식노드의 인덱스가 i일 때, 부모노드의 인덱스는 i/2
루트 노드 : 배열의 중간값
좌측 배열 : 좌측 서브트리
우측 배열 : 우측 서브트리
어떠한 형태의 이진트리든 표현할 수 있으나, 편향 이진트리의 경우 공간 낭비가 심하다는 단점이 있음
비어 있는 자식노드를 모두 null로 표현해주는데, 순차 표현이므로 다음 노드(값이 있는 노드)가 나올 때까지 배열 내에서 공간을 차지하기 때문
이진트리의 연결 표현(연결리스트로 표현)
이진트리를 연결리스트로 표현할 경우, 배열로 표현했을 때의 단점을 보완할 수 있음
각 노드들은 left, data, right로 표현
left : 좌측 노드
data : 노드의 값
right : 우측 노드
서브트리가 비어 있는 경우 null로 표현
연결리스트로 표현할 경우 부모노드를 찾기가 어렵다는 단점이 있음
이진탐색과 이진탐색트리
이진탐색
정렬된 데이터에서 반씩 분할하며 특정 값을 검색하고자 할 때 유용
배열은 삽입, 삭제가 비효율적(데이터 이동 필요)
이진탐색트리
이진탐색트리에 삽입할 데이터가 정렬되어야 할 필요는 없으나, 되도록 중위값을 찾아서 root값으로 설정해주면 균형잡힌 이진트리가 될 수 있음.
참고
https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html
https://velog.io/@kimdukbae/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8A%B8%EB%A6%AC-Tree
https://yoongrammer.tistory.com/71
https://mattlee.tistory.com/30
https://kingpodo.tistory.com/27
'자료구조&알고리즘' 카테고리의 다른 글
| 완전탐색(Brute-Force Search) (0) | 2022.06.04 |
|---|---|
| 해시(Hash) (0) | 2022.05.29 |
| 우선순위 큐(Priory Queue), 힙(Heap) (0) | 2022.05.29 |
| 정렬(Sorting) (0) | 2022.05.29 |