위키원
트리
트리(tree)는 일반적으로 대상 정보의 각 항목들을 계층적으로 연관되도록 구조화시키고자 할 때 사용하는 비선형 자료구조이다. 데이터 요소들의 단순한 나열이 아닌 부모-자식 관계의 계층적 구조로 표현이 된다.
목차
특징
- 그래프의 한 종류 이다. '최소연결 트리'라고도 불린다.
- 트리는 계층 모델이다.
- 임의의 노드에서 다른 노드로 가는 경로는 유일하다.
- 회로(cycle)가 존재하지 않는다.
- 모든 노드는 서로 연결되어 있다.
- 엣지를 하나 자르면 트리가 두개로 분리된다.
- 엣지의 수는 노드의 수에서 1을 뺀 것과 같다. (엣지 = 노드 - 1)
구조
- node: 트리를 구성하고 있는 각 요소
- Edge(간선): 트리를 구성하기 위해 노드와 노드를 연결하는 선
- Root Node: 최상위 계층에 존재하는 노드
- level: 트리의 특정 깊이를 가지는 노드의 집합
- degree(차수): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
- Terminal Node(=leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드
- Internal Node(내부노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.[1]
트리 순회 (tree traversal)
트리 순회란 트리의 각 노드를 체계적인 방법으로 방문하는 과정을 말한다. 하나도 빠뜨리지 않고 , 정확히 한번만 중복없이 방문해야한다.
노드를 방문 하는 순서에 따라 전위순회(preorder), 중위순회(inorder), 후위순회(postorder)세가지로 나뉜다.
[2]
[2]
전위순회 (preorder)
루트 노드에서 시작해서 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순으로 순회하는 방식. 깊이 우선순회(depth-first-traversal) 라고도 한다. - 1 -> 2 -> 4 -> 5 -> 3[2]
중위순회 (inorder)
루트노드에서 시작해서 왼쪽 서브트리노드 -> 오른쪽 서브트리 순으로 순회하는 방식. 대칭 순회(symmetric traversal)이라고도 불린다. - 4 -> 2 -> 5 -> 1 -> 3[2]
후위순회 (postorder)
루트 노드에서 시작해서 왼쪽 서브트리 -> 오른쪽 서브트리 -> 노드 순으로 순회하는 방식 - 4 -> 5 -> 2 -> 3 -> 1[2]
이진 트리 (binary tree)
- 이진 트리(binary tree) : 이진트리는 트리를 구성하는 노드들의 최대 차수(degree)가 2인 노드들로 구성되는 트리이다.
- 이진트리의 레벨 i에서 가질 수 있는 최대 노드의 수는 2^i이다. (i>=0)
- 깊이가 k인 이진트리가 가질 수 있는 최대 노드의 수는 2^k-1이다.(k>=1)
- 이진트리는 완전 이진 트리 (completable binary tree)와 포화 이진 트리(Perfect Binary Tree), 전 이진 트리(Full Binary Tree)라고 하는 특별한 트리 구조를 정의할 수 있다.[1]
완전 이진 트리 (completable binary tree)
- 트리를 구성하고 있는 임의의 두 단말 노드의 레벨 차이가 1 이하이고 마지막 레벨을 제외한 모든 레벨에 존재할 수 있는 모든 노드를 갖고 있으며, 왼쪽에서 오른쪽으로 채워지는 이진트리이다.
전 이진 트리 (full binary tree)
- 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리이다.
포화 이진 트리 (perfect binary tree)
- 모든 레벨에 노드가 차있는 상태로 최대 노드 수인 2^k-1개로 채워져 있는 트리이다.
- 전 이진 트리이면서 완전 이진 트리인 경우이다.[1]
이진 탐색 트리 (binary search tree)
- 이진 탐색 트리(binary search tree) : 이진탐색과 연결리스트(linked list) 를 결합한 자료구조의 일종이다.
- 이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됐다.
- 예를들면 이진탐색의 경우 탐색에 소요되는 계산복잡성은 O(logN)으로 빠르지만 자료입력이나 삭제가 불가능하다.
- 연결 리스트의 경우 자료입력, 삭제에 필요한 계산 복잡성은 O(1)로 효율적이지만 탐색하는 데에는 O(n)의 계산 복잡성이 발생한다. 이 두개의 장점을 살려보는 것이 이진 탐색트리의 목적이라고 할 수 있다.[2]
속성
- 각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값을 지닌 노드들로 이루어져 있다.
- 각 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 값을 지닌 노드들로 이루어져 있다.
- 중복된 노드가 없어야 한다.
- 왼쪽 서브트리, 오른쪽 서브트리 또한 이진 탐색트리이다.
- 이진 탐색트리를 순회할 때에는 중위순회(inorder)방식을 사용한다.
- - 왼쪽 서브트리 -> 노드 -> 오른쪽 서브트리 순으로[2]
[2]
위의 그림에서 중위순회를 사용한다면, 순서는 1, 3, 5, 7, 8, 10 순서로 순회한다.[2]
같이 보기
