트리 구조란?
트리 구조란 그래프의 일종으로 비선형 계층적 자료구조를 말한다.
트리의 구성
트리 구조는 노드와 간선으로 이루어져 있으며
최상위에 있는 노드를 루트 노드, 가장 하위에 있는 노드를 단말 노드 혹은 리프 노드(잎)라 부른다.
트리 자체가 나무를 뜻하기도 하고 트리 구조라는 게 나무를 뒤집어 놓은 모양으로
연상하면 이해가 쉽다.
최상위와 최하위 중간에 있는 노드는 중간 노드 혹은 내부 노드라 부른다.
트리와 관련된 용어
형제 노드 - 같은 부모를 가진 노드
노드의 크기 - 자신을 포함한 모든 자식 노드의 개수
노드의 깊이 - 루트에서부터 특정 노드까지 도달하기 위해 거쳐야 하는 간선의 수
노드의 레벨 - 트리의 특정 깊이를 가지는 노드의 집합
노드의 차수 - 하부 트리의 개수 / 간선의 수. 각 노드가 가진 가지의 수를 말한다.
트리의 차수 - 트리의 최대 차수
트리의 깊이 - 루트 노드에서 가장 깊숙히 위치한 노드까지를 말한다.
트리의 특징
- 방향성이 있는 비선형 계층 모델(DAG - Directed Acyclic Graphs)
- 최소 연결 트리
- 노드가 N개인 트리는 반드시 N-1개의 노드를 가진다.
- 루트에서 어떤 노드로 가든, 그 경로는 유일하다.(노드 간 이동도 한 가지 경로만 존재함)
- 1개의 루트 노드만이 존재하며, 모든 자식 노드는 하나의 부모 노드만을 갖는다.
- 순회는 pre-order, in-order, post-order로 이루어진다.
- 트리의 종류로는 이진 트리, 이진 탐색 트리, 균형 트리, 비균형 트리,
완전 이진 트리, 전 이진 트리, 포화 이진 트리, 이진 힙 등이 있다.
이진 트리란?
자식 노드가 최대 2개인 노드들로 구성된 트리를 말한다.
이진 트리의 종류
- 정 이진 트리(full binary tree)
모든 레벨에서 노드들이 꽉 채워진 트리 구조를 말한다.
(리프 노드를 제외한 모든 노드가 자식 노드를 2개 가지고 있다.)
- 완전 이진 트리(complete binary tree)
마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉 채워진 형태의 트리 구조를 말한다.
- 균형 이진 트리(balanced binary tree)
모든 리프 노드 깊이의 차가 많아야 1인 트리이다.
균형 이진 트리는 예측 가능한 깊이를 가지며, 노드가 n개인 균형 이진 트리의 깊이는 log n을 내림한 값이 된다.
이진 탐색 트리란?
아래와 같은 속성이 있는 자료 구조를 말한다.
- 각 노드에 값이 있다.
- 부모 노드는 왼쪽 자식 노드보다 크고 오른쪽 자식 노드보다 작다.
- 자식 노드 역시 각각 다시 이진 탐색 트리여야 한다.
이진 탐색 트리에서의 검색
해당 노드가 존재하면 반환하고 존재하지 않는다면 null을 반환한다.
- 먼저 루트 노드와 비교해 일치하면 루트 노드 반환
- 일치하지 않고 루트 노드보다 작다면 왼쪽 서브 트리에서 재귀적으로 검색
- 일치하지 않고 루트 노드보다 크다면 오른쪽 서브 트리에서 재귀적으로 검색
삽입
- 삽입 전 검색을 수행한다.
- 키와 일치하는 노드가 없다면 마지막 노드에서 키와 노드의 크기 비교 후
그에 맞게 왼쪽 혹은 오른쪽에 새로운 노드를 삽입한다.
삭제
- 자식 노드가 없다면 해당 노드를 단순히 삭제하면 된다.
- 자식 노드가 1개라면 해당 노드 삭제하고 그 위치에 자식 노드를 넣는다.
- 자식 노드가 2개라면 삭제하려는 노드의 값을 왼쪽 서브 트리 중 가장 작은 값으로 변경한 후 원래 삭제하려던 노드의 값을 삭제한다.
