1. Tree
- 트리는 일반적으로 대상정보의 각 항목들을 계층적으로 연관되도록 구조화 시키고자 할때 사용하는 비선형 자료구조입니다.
- 데이터 요소들의 단순한 나열이 아닌 부모-자식 관계의 계층적 구조로 표현이 됩니다.
- 트리는 그래프(Graph)의 한 종류이며 사이클이 없습니다.
- 트리 자료구조는 여러유형이 있지만 그 중 가장 기본은 binary tree(이진 트리)구조가 대표적입니다.
- 이진 트리는 두개의 자식노드를 가진 트리 형태입니다.
- 트리 자료구조는 데이터를 거꾸로된 나무 형태로 저장하는 모양입니다.
- 계층적인 관계의 표현에 쓰이고, 윈도우와 리눅스의 파일시스템 구조도 트리로 표현됩니다. 대용량의 데이터를 저장할때도 많이 쓰입니다.
2. 용어
- Node : 트리 구조의 교점입니다. Node가 데이터를 가지고 있고 또한 자식노드를 가지고 있습니다. 트리 자료구조는 노드를 기본으로 구성됩니다.
- Root Node: 트리구조의 가장 위 노드. 즉 시작점이 되는 노드입니다.
- Edge: 트리를 구성하기 위해 노드와 노드를 연결하는 선 입니다.
- level: 트리의 특정 깊이를 가지는 노드의 집합 입니다.
- degree: 하위 트리개수 / 각 노드가 지닌 가지의 수를 말합니다.
- Internal Node : Leaf노드를 제외한 중간에 위치한 노드들을 말합니다.
- Leaf Node: 하위에 다른 노드가 연결되어 있지 않은 노드입니다.
- 트리의 속성 중 가장 중요한 것이 '루트 노드를 제외한 모든 노드는 단 하나의 부모노드만을 가진다'는 것입니다.
3. 트리의 탐색
- 트리의 순회란 트리의 각 노드를 체계적인 방법으로 방문하는 과정을 말합니다.
노드를 방문하는 순서에 따라 전위순회, 중위 순회, 후위순회 세가지로 나뉩니다.
-
전위순회(preorder)
루트노드 - 왼쪽 서브트리 - 오른쪽 서브트리 순으로 순회하는 방식입니다.
'깊이 우선 순회'라고도 합니다. -
중위순회(inorder)
루트노드에서 시작해서 왼쪽 서브트리 - 노드 - 오른쪽 서브트리 순으로 순회하는 방식입니다.
'대칭 순회' 라고도 합니다.
-
후위 순회(postorder)
루트노드에서 시작해서 왼쪽 서브트리 - 오른쪽 서브트리 - 노드 순으로 순회하는 방식입니다.
4. 이진 트리와 이진 탐색 트리
-
이진 트리는 최대 차수가 2인 트리를 말합니다.
-
이는 하나의 노드에 LEFT or RIGHT만 존재한다고 표현합니다.
-
이진 트리에는 여러 유형이 존재합니다.
1. 편향 이진 트리(skewed binary tree)
편향이진 트리는 하나의 차수로만 이뤄져 있는 경우를 말합니다. 이런 구조는 배열과 같은 선형 구조이기
때문에 Leaf Node (가장 끝 노드)탐색시 결국 모두 읽어 들여야 한다는 단점이 있어서 효율이 떨어진다고 말합니다. 이같은 점을 보완하기 위해 '높이 균형 트리'라는 것이 있습니다.- 포화 이진 트리(Full Binary Tree)
- 포화 이진 트리(Full Binary Tree)
포화이진 트리는 Leaf Node를 제외한 모든 노드의 차수가 두개로 이뤄진 경우를 말합니다. 이 경우에는 해당 차수에 몇개의 노드가 존재하는지 바로 알수 있어 개수 파악이 용이하다는 장점이 있습니다.
- 완전 이진 트리(Complete Binary Tree)
포화 이진트리와 같은 개념으로 생성하지만 모든 노드가 왼쪽부터 차근차근 생성되는 이진 트리를 말합니다.
-
이진 탐색 트리(Binary Search Tree)?
이진 탐색 트리에서는 항상 부모 노드가 왼쪽 자식보다는 크고, 오른쪽 자식보다는 작습니다.
이러한 특성 덕분에 이진탐색트리에서는 한번 확인할때 마다 보아야 하는 원소의 개수가 절발씩 줄어든다는 점에서 '완전 이진 트리'인 경우 탐색시간에 O(logN)의 시간복잡도를 가집니다.이진 탐색 트리에서 탐색(traverse)을 할 때는 찾고자 하는 값이 부모 노드보다 작을 경우 왼쪽 자식으로, 찾고자 하는 값이 부모 노드보다 클 경우 오른쪽 자식으로 이어 나가면서 방문 합니다.
이진 탐색트리는 이진 탐색이 항상 동작하도록 구현하여 탐색속도를 극대화 시킨 자료구조를 이진 탐색 트리라고 합니다.
