Tree
트리 구조는 노드가 계층을 이루고 있는 자료구조로, 나무의 가지형태를 닮아서 트리 구조라고 불린다.
최상위 노드를 루트 노드라고 부르며 하나의 노드 바로 아래에 연결된 노드를 자식 노드라고,
자식 노드의 바로 상위 노드를 부모 노드라고 부른다.
또한, 자식 노드가 없는 노드를 리프 노드, 리프 노드를 제외한 노드를 내부 노드라고 부른다.
외의 용어를 아래에 정리하겠다.
- 깊이 - 루트 노드에서 노드까지의 경로 길이를 말한다.
- 높이 - 루트 노드에서 가장 깊은 노드까지의 경로 길이를 말한다.
- 형제 노드 - 동일한 부모 노드를 공유하는 노드를 말한다.
- 서브 트리 - 하위 트리의 집합을 말한다.
아래와 같이 시각화할 수 있다.
Ternary Tree
Ternary Tree는 각 노드가 최대 3개의 하위 노드를 가질 수 있는 트리 구조를 말한다.
일반적으로 트리를 지칭할 때에는 이진 트리를 사용하여 일부 교재에는 빠져있는 경우도 있다.
이진 트리(Binary Tree)
이진트리는 각 노드가 최대 2개의 하위 노드를 가질 수 있는 트리 구조이다.
따라서 자식 노드가 왼쪽 자식 노드, 오른쪽 자식 노드로 나뉘며 쉽게 L과 R이라고 부른다.
이 이진 트리는 이진 검색 트리, 정 이진 트리, 포화 이진 트리, 완전 이진 트리로 나뉘는데
배열보다 공간 소요는 크지만 데이터의 추가/삭제가 용이하고 시간복잡도가 동일하다는 면에서 활용된다.
이진 탐색 트리 (Binary Search Tree)
이진 탐색 트리는 한 노드의 좌측 서브트리는 해당 노드보다 작은 값을,
우측 서브트리는 해당 노드보다 큰 값을 가지는 조건을 만족하는 이진 트리이다.
이진 탐색 트리에서의 탐색 과정은 아래와 같이 나타낼 수 있다.
- 찾고자 하는 값이 해당 노드의 값보다 작은지 큰지 판별한다.
- 작다면 좌측 서브트리로, 크다면 우측 서브트리로 탐색을 진행한다.
- 이 과정을 루트 노드에서부터 반복 진행한다.
정 이진 트리(Full Binary Tree)
정 이진 트리는 이진 트리의 모든 노드가 0개 혹은 2개의 자식 노드를 갖는 조건을 만족하는 이진트리이다.
완전 이진 트리(Complete Binary Tree)
완전 이진 트리는 마지막 레벨을 제외한 모든 노드가 2개의 자식 노드를 갖는 이진 트리이다.
또한 마지막 레벨의 노드는 오른쪽 자식 노드만 가질 수 없으며, 추가할 경우에도 왼쪽 자식 노드부터 삽입하고 삭제할 경우에는 오른쪽 자식 노드부터 삭제해야 한다.
포화 이진 트리(Perfect Binary Tree)
포화 이진 트리는 정 이진 트리이면서 완전 이진 트리를 만족하는 이진 트리이다.
즉, 모든 레벨의 노드가 가득 채워져있는 형태를 의미한다.
Tree 순회
트리의 순회는 각 노드를 한 번만, 체계적으로 방문하며 탐색하는 과정을 의미한다.
노드를 방문하는 순서에 따라서 전위, 중위, 후위로 나뉘며 이진트리에서 작성되는게
대부분이지만 모든 트리에서 일반화 가능하다.
전위 순회(Preorder)
- 노드를 탐색한다.
- 좌측 자식 노드를 탐색한다.
- 우측 자식 노드를 탐색한다.
- 반복한다.
위의 트리로 예시를 들면 5 -> 7 -> 1 -> 8 -> 2 -> 11가 된다.
중위 순회(Inorder)
- 좌측 자식 노드를 탐색한다.
- 노드를 탐색한다.
- 우측 자식 노드를 탐색한다.
위의 트리로 예시를 들면 1 -> 7 -> 8 -> 5 -> 2 -> 11가 된다.
후위 순회(Postorder)
- 좌측 자식 노드를 탐색한다.
- 우측 자식 노드를 탐색한다.
- 노드를 탐색한다.
위의 트리로 예시를 들면 1 -> 8 -> 7 -> 11 -> 2 -> 5가 된다.
Graph
그래프는 정점(Vertex)과 간선(Edge)로 이루어진 자료구조이다.
검색엔진, 네비게이션 등에서 활용되며 정점은 노드를, 간선은 노드간의 연결을 의미한다.
그래프 또한 인접 행렬, 인접 리스트 등 구현방법이 나뉘어지고,
무방향 그래프, 방향 그래프, 가중치 그래프, 완전 그래프로 종류가 다양하지만
다음에 기회가 된다면 다뤄보도록 하겠다.
