트리
계층적인 구조를 나타내는 자료 구조 (비선형 구조)
부모 자식 관계의 노드들로 이루어진다.
[응용 분야]
1. 계층적인 조직 표현
2. 컴퓨터 디스크의 디렉토리 구조
트리 용어
노드 - 트리의 구성요소
간선 - 노드와 노드를 연결하는 선
루트 - 최상위 노드
서브 트리 - 하나의 노드와 그 노드들의 자손들로 이루어진 트리
단말 노드 - 자식이 없는 노드
레벨 - 트리의 각층 번호
높이 - 트리의 최대 레벨
차수 - 노드가 가지고 있는 자식 노드의 수
이진트리
모든 노드는 최대 2개의 서브 트리를 가질 수 있다.
서브트리는 공집합일 수 있음
**** 이진트리에는 서브 트리 간의 순서가 존재
왼쪽 서브트리, 오른쪽 서브트리
이진트리 성질
1. 노드의 개수가 n개이면 간선의 개수는 n-1개이다.
2. 높이가 h인 이진트리의 경우 최소 h개의 노드를 가지며 최대 2^h -1개의 노드를 가진다.
포화 이진트리
모든 레벨이 꽉 찬 경우 이진트리
완전 이진트리
루트부터 마지막 리프노드까지 중간에 비어있는 부분이 없는 이진트리
Ex) 크기 100인 배열이 있을 때
0 ~ 30까지 모든 원소가 존재한다면 이는 완전이진트리
0 ~ 99까지 꽉 차 있다면 포화이진트리
이진트리 부모와 자식 인덱스 관계
노드 i의 부모 노드 인덱스 - i / 2
노드 i의 왼쪽 자식 노드 인덱스 - 2i
노드 i의 오른쪽 자식 노드 인덱스 - 2i + 1
이진트리 순회
전위 순회
루트 - 왼쪽 - 오른쪽 순회
중위 순회
왼쪽 - 루트 - 오른쪽 순회
후위 순회
왼쪽 - 오른쪽 - 루트 순회
순회
def preorder(x) :
if x != NULL :
print(x)
preorder(Left(x))
preorder(Right(x))
def inorder(x) :
if x != NULL :
inorder(Left(x))
print(x)
inorder(Right(x))
def postorder(x) :
if x != NULL :
postorder(Left(x))
postorder(Right(x))
print(x)
이진탐색트리
**** 트리 높이에 비례하는 시간에 수행됨.
왼쪽 서브 트리 < 루트 < 오른쪽 서브 트리
이진 탐색을 수행하려면 정렬되어 있어야 함 // 평균 logN, 최악 N
이진 탐색이 종료되는 조건
1. 검색하고자 하는 key를 찾은 경우
2. 검색하고자 하는 key를 찾지 못한 경우
B트리
** B tree는 완전 균형 트리
-> 모든 리프노드가 동일한 높이를 가져야하는 것을 의미
많은 데이터베이스에서 정보를 저장하기 위해 B트리를 사용
- 비트리는 M차 트리이므로 이진트리인 RB 트리보다 높이가 낮다.
B tree의 시간 복잡도는 평균 lgN, 최악 lgN 여기서 N은 레코드(행) 수를 의미
일반적으로 B tree는 높이가 h일 때, 최대 h번 I/O 입출력을 수행
-> 높이가 최소화되는 것이 I/O 입출력을 최소화하는 것을 의미
B tree는 균형 이진 트리와 유사하여 데이터를 효율적으로 검색할 수 있다.
** B 트리 단점
1. 균형 유지를 위한 오버헤드 발생
2. 구현 복잡함
3. 각 노드가 여러 키와 포인터를 저장하므로, 단일 노드 크기가 큼
4. 빈번한 삽입 삭제가 있는 경우 균형 유지를 위한 재조정 작업이 자주 발생하여 성능에 영향을 줌
** 디스크 한 번 접근은 10만 개 이상의 명령을 처리하는 시간을 소비
Red Black Tree
** RB tree는 균형 이진 탐색 트리
완전히 동일한 높이를 요구하지 않음, 좌우 서브트리의 높이 차이가 일정 범위 내에 있는 것
** 즉, 최악의 경우에도 logN을 보장하기 위해서 고안된 트리
이진 트리의 경우 삽입 삭제가 빈번한 경우 트리의 높이가 길어질 수 있다.
이를 해결하고자 RB tree는 재조정을 수행하여 균형을 유지하므로써 높이를 최소화한다.
검색, 삽입, 삭제에 O(logN)에 근접한 시간이 소요 됨
평균 - logN, 최악 - logN
AVL 트리
** AVL tree는 균형 탐색 트리
RB 트리보다 더 엄격한 균형을 유지
삽입 삭제 시 빈번한 재조정이 필요
** 더 엄격한 균형 유지를 통해 검색 성능이 더 좋을 수 있음
삽입 삭제가 많은 경우 RB 트리에 비해 느릴 수 있음
삽입, 삭제 보다 검색이 빈번한 경우 적합
검색, 삽입, 삭제
평균 - logN, 최악 - logN