Tree
2019. 03. 04
비선형 구조
원소들 간에 계층관계를 가지는 계층형 자료구조
cycle이 없는 무향 그래프
I. 기본 구조
루트 노드: 최상위 노드
노드의 차수: 하나의 노드에 연결된 자식 노드의 갯수
트리의 차수: 트리의 노드의 차수 중에서 가장 큰 값
단말노드: 차수가 0인 노드
서브트리: 트리 안의 트리
높이: 루트에서 노드에 이르는 간선의 수. 해당 노드를 0으로 시작
- 레벨=0 : 높이=0
- …
II. 이진트리
모든 노드가 2개의 서브트리를 갖는 트리
트리의 차수가 2 이하
1. 특성
레벨 i에서 노드의 최대 갯수는 2^i개
높이가 h인 이진트리가 가질 수 있는 노드의 최소 갯수: h+1, 최대 갯수: 2^(h+1) - 1
2. 이진트리 종류
포화 이진트리: 모든 레벨에 노드가 포화상태로 차 있는 이진트리
완전 이진트리: 높이가 h이고 노드 수가 n개일 대 노드번호 1에서 n까지 빈자리가 없는 이진트리
편향 이진드리: 높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만 가진 이진트리
3. 이진트리 순회
순회: 트리의 노드들을 체계적으로 방문하는 것
전위 순회
루트노드 방문 후 좌, 우 자식노드 방문
def preorder(tree) :
if tree :
visited(tree)
preorder(tree.left)
preorder(tree.right)
중위 순회
좌측 자식노드 방문, 루트노드 방문 후 우측 자식노드 방문
def inorder(tree) :
if tree :
inorder(tree.left)
visited(tree)
inorder(tree.right)
후위 순회
좌, 우 자식노드 방문 후 루트노드 방문
def postorder(tree) :
if tree :
postorder(tree.left)
postorder(tree.right)
visited(tree)
4. 이진트리 표현
배열 사용
0번 index를 비우고 index 순서대로 자료 삽입
부모의 위치: child / 2
자식의 위치: parent * 2, parent * 2 + 1
또 다른 방법: 부모에 2개의 index(l, r)을 두어 자식 노드의 값만 저장
단점
메모리 낭비가 심하다
노드 삽입, 삭제에 대한 비용이 비싸다
연결리스트 사용
노드에 왼쪽, 오른쪽 자식 노드를 구성하여 구현
5. 수식 트리
수식을 표현하는 이진트리
연산자는 루트노드이거나 가지노드
피연산자는 모드 리프노드
III. 이진 탐색 트리
탐색작업을 효율적으로 하기 위한 자료구조
모든 원소는 서로 다른 유일한 키를 갖는다
key(왼쪽 서브트리) < key(루트 노드) < key(오른쪽 서브트리)
왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리
중위 순회하여 오름차순으로 정렬된 값을 얻을 수 있다
탐색 연산: log(n)
탐색이 효율적이기 위해서 depth를 낮춘 완전 이진트리를 이루는 것이 중요
- depth를 낮춘다: AVL tree, RB tree…
1. 연산
탐색 연산
key를 기준으로 탐색
없을 경우 삽입연산 수행
삽입 연산
먼저 탐색연산 수행
- 같은 원소가 트리에 있는지 탐색하여 확인
탐색이 실패한 위치에 원소를 삽입한다.
삭제 연산
말단 노드를 삭제: 그냥 삭제연산 수행
중간에 있는 노드 삭제: 바로 앞 혹은 뒤에 있는 노드가 대신하고 삭제
루트 노드를 삭제: 바로 앞 혹은 뒤에 있는 노드가 대신하고 삭제
대신하는 노드가 말단노드일 필요는 없다
2. 균형 이진 탐색트리
10, 9, 8… 식으로 주어질 경우 이진 탐색 트리가 O(n)에 수렴
탐색트리를 사용하는 이유가 없어짐
이를 막기 위해 균형을 이루면서 이진트리 구현
1. AVL 트리
balance factor: -1 ~ 1
- 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이
모든 노드가 balance factor 조건을 만족해야함
균형을 맞추는 방법
- LL, RL, LR, RR
IV. 허프만 트리
AAABBCDAA…
Greedy: 빈도수가 높은 문자에 짧은 코드를 부여하겠다
문자열에서 알파벳의 갯수를 센다
A: 400, B: 70, C: 20, D: 10 …
작은 순으로 정렬
작은 것을 2개씩 묶어 트리로 구현
- 갯수를 하나의 노드로 하고 그 밑에 문자와 갯수를 포함한 자식 노드가 존재
왼쪽 자식은 1, 오른쪽 자식은 0으로 표현
갯수가 많은 것 일 수록 적은 비트로 표현 가능
문자열을 비트로 표현하여 전송
V. 인덱스 테이블
1. 세그먼트 트리(인터벌 트리)
구간에 대한 수많은 연산이 필요한 경우 사용
인덱스 트리: 완전 이진트리
단말 노드: 데이터를 저장
부모 노드: 구간 정보를 저장
구간합: i와 j를 2로 나누면서 부모를 쫓아가 만나는 부분이 구간합
- 구간이 분할되었다면
- i: 짝수일 때만 올라가고, 홀수면 따로 처리
- j: 홀수일 때만 올라가고, 짝수면 따로 처리