7. 트리
트리: 계층적인 구조를 나타내는 자료구조
- 가족의 가계도, 회사의 조직도, 컴퓨터의 디렉터리 구조 등
- 트리는 부모-자식 관계의 노드들로 이루어짐
트리의 용어
- 노드: 트리의 구성요소
- 루트: 부모가 없는 노드
- 서브 트리: 하나의 노드와 그 노드들의 자손들로 이루어진 트리
- 단말 노드: 자식이 없는 노드
- 비단말 노드: 적어도 하나의 자식을 가지는 노드
- 자식, 부모, 형제, 조상, 자손 노드
- 레벨: 트리 각층의 번호
- 차수: 노드가 가지고 있는 자식 노드의 개수
이진트리
이진트리:모든 노드가 2개의 서브 트리를 가지고 있는 트리
- 서브 트리는 공집합일 수 있음.
- 최대 2개까지의 자식 노드가 존재
- 모든 노드의 차수가 2 이하가 됨
- 서브 트리 간의 순서가 존재
이진트리의 성질
- 노드의 개수가 n개면 간선의 개수는 n-1
- 높이가 h인 이진트리의 경우, 최소 h개의 노드를 가지며 최대 2^h-1개의 노드를 가짐
- n개의 노드를 가지는 이진트리의 높이는 최대 n, 최소 log2 (n+1) 이다.
이진트리의 분류
- 포화 이진 트리(full binary tree)
- 완전 이진 트리(complete binary tree)
- 기타 이진 트리
포화 이진 트리: 트리의 각 레벨에 노드가 꽉 차있는 이진트리
- 포화 이진 트리에는 각 노드에 번호를 붙일 수 있다. (위에서 부터 왼쪽에서 오른쪽으로))
완전 이진트리:1부터 k-1까지는 노드가 모두 채워져 있고,, 마지막 레벨 k에서는 왼쪽에부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리
배열 표현법
- 모든 이진트리를 포화 이진트리라고 가정하고 각 노드에 번호를 붙여서 그 번호를 배열의 인덱스로 삼아 노드의 데이터를 배열에 저장하는 방법
부모와 자식 인덱스 관계
- 노드 i의 부모 노드 인덱스 = i/2
- 노드 i의 왼쪽 자식 노드 인덱스 = 2i
- 노드 i의 오른쪽 자식 노드 인덱스 = 2i+1
링크 표현법
- 포인터를 이용하여 부모 노드가 자식 노드를 가리키게 하는 방법
링크의 구현
- 노드는 구조체로 표현
- 링크는 포인터로 표현
이진트리의 순회
순회: 트리의 노드들을 체계적으로 방문하는 것
3가지의 기본적인 순회 방법
- 전위순회(VLR): 자손 노드보다 루트 노드를 먼저 방문
- 중위순회(LVR): 왼쪽 자손, 루트, 오른쪽 자손 순으로 방문
- 후위순회(LRV): 루트 노드보다 자손을 먼저 방문한다.
전위 순회
1. 루트 노드를 방문
2. 왼쪽 서브 트리를 방문
3. 오른쪽 서브트리를 방문
중위 순회
1. 왼쪽 서브트리를 방문
2. 루트 노드를 방문
3. 오른쪽 서브트리를 방문
후위 순회
1. 왼쪽 서브트리를 방문
2. 오른쪽 서브트리를 방문
3. 루트 노드를 방문
레벨 순회: 각 노드를 레벨 순으로 검사하는 순회 방법
- 레벨 순회는 큐를 사용한 순회 법
수식 트리: 산술식을 트리 형태로 표현한 것
- 비단말노드: 연산자, 단말노드: 피연산자
- 후위순회를 사용하며 서브 트리의 값을 순환 호출로 계산
- 비단말노드 방문 시 양쪽 서브 트리 값을 노드에 저장된 연산자를 이용해 계산
스레드 이진 트리
- 이진트리의 NULL 링크를 이용하여 순환 호출 없이도 트리의 노드들을 순회
- NULL 링크에 중위 순회시에 후속 노드인 중위 후속자를 저장시켜 놓은 트리
- 단말노드와 비단말노드의 구별을 위해 is_thread 필드가 필요 (TRUE면 중위 후속자가 있다는 것)
이진탐색트리
- 탐색 작업을 효율적으로 하기 위한 자료구조
- key(왼쪽서브트리) <= key(루트노드) <= key(오른쪽서브트리)
- 이진탐색트리를 중위순회하면 오름차순으로 정렬된 값을 얻을 수 있음
이진탐색트리 탐색 연산 과정
- 주어진 키와 결과가 같으면 탐색이 성공적으로 끝남
- 주어진 키 값이 루트 노드의 키 값보다 작으면 현재 루트 노드의 왼쪽 자식을 기준으로 다시 탐색
- 주어진 키 값이 루트 노드의 키 값보다 크면 현재 루트 노드의 오른쪽 자식을 기준으로 다시 탐색
이진탐색트리 삽입연산
- 원소를 삽입하기 위해 먼저 탐색 과정이 필요
- 탐색에 실패한 위치가 새로운 노드를 삽입하는 위치
이진탐색트리 삭제연산
1. 삭제하려는 노드가 단말 노드일 경우
2. 삭제하려는 노드가 왼쪽이나 오른쪽 서브 트리 중 하나만 가지고 있는 경우
3. 삭제하려는 노드가 두 개의 서브 트리 모두 가지고 있는 경우
이진탐색트리의 성능 분석
- 최선의 경우 O(log n)의 시간 복잡도를 갖는다
- 최악의 경우 O(n)의 시간 복잡도를 갖는다.
자료 출처: 천인국 외 1명, C언어로 쉽게 풀어쓴 자료구조, 생능출판(2019)