트리

트리의 개념

• 비선형 구조
• 1:n 관계를 가지는 자료구조
• 원소들 간에 계층관계를 가지는 계층형 자료구조
• 상위 원소에서 하위원소로 내려가면서 확장되는 나무 구조

용어 정리

• 한 개 이상의 노드로 이루어진 유한 집합

  • 노드 중 최상위 노드를 루트(root)라 함
  • n개의 분리 집합(부트리)으로 분리 될 수 있음

• 노드(node) - 트리의 원소

  • 트리 T의 노드 - A,B,C,D,E,...,J,K

• 간선(edge) - 노드를 연결하는 선. 부모 노드와 자식 노드를 연결

• 루트 노트(root node) - 트리의 시작 노드

  • 트리 T의 루트노드 - A

• 형제 노드(sibling node) - 같은 부모 노드의 자식 노드들

  • B,C,D는 형제 노드

• 조상 노드 - 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들

• 서브트리 - 부모노드와 연결된 간선을 끊었을 때 생성되는 트리

• 자손 노드 - 서브 트리에 있는 하위 레벨의 노드들

  • B의 자손 노드 - E,F,K

• 차수(degree)

  • 노드의 차수 : 노드에 연결된 자식 노드의 수
  • 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값
  • 단말 노드 : 차수가 0인 노드, 자식 노드가 없는 노드

• 높이

  • 노드의 높이 : 루트에서 노드에 이르는 간선의수, 노드의 레벨 (상대적임 0부터시작 / 1부터 시작)
  • 트리의 높이 : 트리에 있는 노드의 높이 중에서 가장 큰 값

이진트리

• 모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리
• 각 노드가 자식 노드를 최대 2개 까지만 가질 수 있는 트리
• 이진 트리의 예
  

특성

• 레벨 i에서의 노드의 최대 개수는 2^i 개
• 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1)개가 되며, 최대 개수는 (2^(h+1) - 1) 개가 됨

종류

포화 이진 트리(Full Binary Tree)

• 모든 레벨에 노드가 포화 상태로 차 있는 이진트리
• 높이가 h일 때, 최대의 노드 개수인 (2^(h+1) - 1)의 노드를 가진 이진트리
• 루트를 1번으로 하여 (2^(h+1) - 1)까지 정해진 위치에 대한 노드 번호를 가짐
  

완전 이진 트리 (Complete Binary Tree)

• 높이가 h이고 노드 수가 n개 일때 (단, 2^h <= n < (2^(h+1) - 1)), 포화 이진 트리의 노드 번호 1번 부터 n번까지 빈 자리가 없는 이진 트리
  (중간 번호가 빠지는 것은 안됨)
  

편향 이진 트리(Skewed Binary Tree)

• 높이 h에 대한 최소 개수의 노드르 가지면서 한쪽 방향의 자식 노드만을 가진 이진 트리
  

순회

• 순회한 트리의 각 노드를 중복되지 않게 전부 자문 하는 것
• 트리는 비선형 구조이기 때문에 선형구조에서와 같이 선후 연결관계를 알 수 없음
  -> 따라서 특별한 방법이 필요

순회(traversal) : 트리의 노드들을 체계적으로 방문하는 것

3가지의 기본적인 순회 방법

• 전위 순회 : VLR
  • 부모노드 -> 자식노드 (좌 -> 우)
• 중위 순회 : LVR
  • 왼쪽 가식노드 -> 부모노드 -> 오른쪽 자식노드
• 후위 순회 : LRV
  • 자식노드 (좌 -> 우) -> 부모노드
    

이진트리의 표현

배열을 이용한 이진트리의 표현

• 이진트리에 각 노드 번호를 다음과 같이 부여
• 루트의 번호를 1로함
• 레벨 n에 있는 노드에 대하여 왼쪽부터 오른쪽으로 2^n 부터 2^(n+1)-1 까지 번호를 차례로 부여

노드 번호의 성질

• 노드 번호가 i인 노드의 부모 노드 번호 : i // 2
• 노드 번호가 i인 노드의 왼쪽 자식 노드 번호 : 2*i
• 노드 번호가 i인 노드의 오른쪽 자식 노드 번호 : 2*i + 1
• 레벨 n의 노드 번호 시작 번호 : 2^n
• 노드 번호를 배열의 인덱스로 사용
• 높이가 h인 이진 트리를 위한 배열의 크기
  • 레벨 i의 최대 노드 수 : 2^i
  • 따라서 1+2+4+8+...+2^i = 2^(h+1)-1

배열을 이용한 이진 트리의 표현의 단점

• 편향 이진 트리의 경우에 사용하지 않는 배열 원소에 대한 메모리 공간 낭비 발생
• 트리의 중간에 새로운 노드를 삽입하거나 기존의 노드를 삭제할 경우 배열의 크기 변경 어려워 비효율적

이진 트리의 저장

부모 번호를 인덱스로 자식 번호를 저장

부모	0	1	2	3	4	5
자식1	0	2	0	4	0	0
자식2	0	3	0	5	0	0

자식 번호를 인덱스로 부모 번호를 저장

• 부모나 조상을 찾을 때 유용

자식	0	1	2	3	4	5
부모	0	0	1	1	3	3

루트 찾기, 조상 찾기

트리의 표현 연결리스트

• 배열을 이용한 이진 트리의 표현의 단점을 보완하기 위해 연결리스트를 이용하여 트리를 표현할 수 있음
• 연결 자료구조를 이용한 이진트리의 표현
  • 이진 트리의 모든 노드는 최대 2개의 자식 노드를 가지므로 일정한 구조의 단순 연결리스트 노드를 사용하여 구현

수식 트리

• 수식을 표현하는 이진 트리
• 수식 이진 트리라고 부르기도 함
• 연산자는 루트 노드이거나 가지 노드
• 피연산자는 모두 잎 노드

수식 트리의 순회

• 중위 순회 : A/B*C*D+E
• 후위 순회 : A B/C*D*E+
• 전위 순회 : +**/ABCDE

이진 탐색 트리

• 탐색작업을 효율적으로 하기 위한 자료구조
• 모든 원소는 서로 다른 유일한 키를 가짐
• 왼 KEY(서브트리) < KEY(루트노드) < 오른 KEY(서브트리)
• 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리
• 중위 순회하면 오름차순으로 정렬된 값을 얻을 수 있음
  

연산

탐색 연산

• 루트에서 시작
• 탐색할 키 값 x를 루트 노드의 키 값과 비교
  • x == KEY : 탐색 성공
  • x > KEY : 오른쪽 서브트리에 대해 탐색 수행
  • x < KEY : 왼쪾 서브트리에 대해 탐색 수행
• 탐색 연산
  • 13탐색의 예
    

삽입 연산

1. 먼저 탐색 연산 수행
2. 탐색 실패한 위치에 원소를 삽입
   

성능

• 탐색, 삽입, 삭제 시간은 트리의 높이 만큼 시간이 걸림
  • O(h)
• 평균의 경우
  • 이진 트리가 균형적으로 생성되어 있는 경우
  • O(log n)
• 최악의 경우
  • 한쪽으로 치우친 경사 이진트리의 경우
  • O(n)
  • 순차 탐색과 시간복잡도가 같음

힙(heap)

• 완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해서 만든 자료구조

• 최대 힙(max heap)

  • 키값이 가장 큰 노드를 찾기 위한 완전 이진 트리
  • 부모노드의 키값 > 자식노드의 키값
  • 루트 노드 : 키값이 가장 큰 노드

• 최소 힙(min heap)

  • 키값이 가장 작은 노드를 찾기 위한 완전 이진 트리
  • 부모노드의 키값 < 자식노드의 키값
  • 루트 노드 : 키값이 가장 작은 노드

• 힙이 아닌 이진 트리

  • 포화 이진 트리가 아닌 경우
  • 부모와 자식의 값이 같은 경우