트리 편집하기

'''트리'''(tree)는 일반적으로 대상 정보의 각 항목들을 계층적으로 연관되도록 구조화시키고자 할 때 사용하는 비선형 [[자료구조]]이다. 데이터 요소들의 단순한 나열이 아닌 부모-자식 관계의 계층적 구조로 표현이 된다.
== 특징 ==
* 그래프의 한 종류 이다. '최소연결 트리'라고도 불린다.
* 트리는 계층 모델이다.
* 임의의 노드에서 다른 노드로 가는 경로는 유일하다.
* 회로(cycle)가 존재하지 않는다.
* 모든 노드는 서로 연결되어 있다.
* 엣지를 하나 자르면 트리가 두개로 분리된다.
* 엣지의 수는 노드의 수에서 1을 뺀 것과 같다. (엣지 = 노드 - 1)

== 구조 ==
[[파일:트리.png|600픽셀]]<ref name='tree'>adam2,〈[https://velog.io/@adam2/TREE 자료구조 Tree]〉, 2020년 4월 5일</ref> <br>
* '''node''': 트리를 구성하고 있는 각 요소
* '''Edge(간선)''': 트리를 구성하기 위해 노드와 노드를 연결하는 선
* '''Root Node''': 최상위 계층에 존재하는 노드
* '''level''': 트리의 특정 깊이를 가지는 노드의 집합
* '''degree(차수)''': 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
* '''Terminal Node(=leaf Node, 단말 노드)''' : 하위에 다른 노드가 연결되어 있지 않은 노드
* '''Internal Node(내부노드, 비단말 노드)''' : 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.<ref name='tree'></ref>
== 트리 순회 (tree traversal) ==
트리 순회란 트리의 각 노드를 체계적인 방법으로 방문하는 과정을 말한다. 하나도 빠뜨리지 않고 , 정확히 한번만 중복없이 방문해야한다.<br>
노드를 방문 하는 순서에 따라 전위순회(preorder), 중위순회(inorder), 후위순회(postorder)세가지로 나뉜다.<br>
[[파일:트리순회.png]]
=== 전위순회 (preorder) ===
루트 노드에서 시작해서 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순으로 순회하는 방식. 깊이 우선순회(depth-first-traversal) 라고도 한다.
- 1 -> 2 -> 4 -> 5 -> 3
=== 중위순회 (inorder) ===
루트노드에서 시작해서 왼쪽 서브트리노드 -> 오른쪽 서브트리 순으로 순회하는 방식. 대칭 순회(symmetric traversal)이라고도 불린다.
- 4 -> 2 -> 5 -> 1 -> 3
=== 후위순회 (postorder) ===
루트 노드에서 시작해서 왼쪽 서브트리 -> 오른쪽 서브트리 -> 노드 순으로 순회하는 방식
- 4 -> 5 -> 2 -> 3 -> 1

== 이진 트리 (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)라고 하는 특별한 트리 구조를 정의할 수 있다.<ref name='tree'></ref>
=== 완전 이진 트리 (completable binary tree) ===
[[파일:완전이진트리.png|700픽셀]]<ref name='tree'></ref><br>
:트리를 구성하고 있는 임의의 두 단말 노드의 레벨 차이가 1 이하이고 마지막 레벨을 제외한 모든 레벨에 존재할 수 있는 모든 노드를 갖고 있으며, 왼쪽에서 오른쪽으로 채워지는 이진트리이다.

=== 전 이진 트리 (full binary tree) ===
[[파일:전이진트리.png|700픽셀]]<ref name='tree'></ref><br>
:모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리이다.

=== 포화 이진 트리 (perfect binary tree) ===
:모든 레벨에 노드가 차있는 상태로 최대 노드 수인 2^k-1개로 채워져 있는 트리이다.
:전 이진 트리이면서 완전 이진 트리인 경우이다.<ref name='tree'></ref>

== 이진 탐색 트리 (binary search tree) ==
* '''이진 탐색 트리(binary search tree)''' : 이진탐색과 연결리스트(linked list) 를 결합한 자료구조의 일종이다.
:이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됐다.
:예를들면 이진탐색의 경우 탐색에 소요되는 계산복잡성은 O(logN)으로 빠르지만 자료입력이나 삭제가 불가능하다.
:연결 리스트의 경우 자료입력, 삭제에 필요한 계산 복잡성은 O(1)로 효율적이지만 탐색하는 데에는 O(n)의 계산 복잡성이 발생한다. 이 두개의 장점을 살려보는 것이 이진 탐색트리의 목적이라고 할 수 있다.

== 같이 보기 ==
* [[자료구조]]

{{데이터|토막글}}
@@ 19번째 줄: / 19번째 줄: @@
 * '''Internal Node(내부노드, 비단말 노드)''' : 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.<ref name='tree'></ref>
 == 트리 순회 (tree traversal) ==
-트리 순회란 트리의 각 노드를 체계적인 방법으로 방문하는 과정을 말한다. 하나도 빠뜨리지 않고 , 정확히 한 번만 중복 없이 방문해야 한다.<br>
+트리 순회란 트리의 각 노드를 체계적인 방법으로 방문하는 과정을 말한다. 하나도 빠뜨리지 않고 , 정확히 한번만 중복없이 방문해야한다.<br>
-노드를 방문하는 순서에 따라 전위순회(preorder), 중위순회(inorder), 후위순회(postorder) 세 가지로 나뉜다.<br><ref name='binary_search_tree'>hanrimjo,〈[https://velog.io/@hanrimjo/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%ED%8A%B8%EB%A6%AC-Binary-Search-Tree-8gk6ablvfx 이진 탐색 트리]〉, 2020년 2월 7일</ref>
+노드를 방문 하는 순서에 따라 전위순회(preorder), 중위순회(inorder), 후위순회(postorder)세가지로 나뉜다.<br>
-[[파일:트리순회.png]]<ref name='binary_search_tree'></ref>
+[[파일:트리순회.png]]
 === 전위순회 (preorder) ===
-루트 노드에서 시작해서 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순으로 순회하는 방식. 깊이 우선순회(depth-first-traversal)라고도 한다.
+루트 노드에서 시작해서 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순으로 순회하는 방식. 깊이 우선순회(depth-first-traversal) 라고도 한다.
-- 1 -> 2 -> 4 -> 5 -> 3<ref name='binary_search_tree'></ref>
+- 1 -> 2 -> 4 -> 5 -> 3
 === 중위순회 (inorder) ===
-루트노드에서 시작해서 왼쪽 서브트리노드 -> 오른쪽 서브트리 순으로 순회하는 방식. 대칭 순회(symmetric traversal)라고도 불린다.
+루트노드에서 시작해서 왼쪽 서브트리노드 -> 오른쪽 서브트리 순으로 순회하는 방식. 대칭 순회(symmetric traversal)이라고도 불린다.
-- 4 -> 2 -> 5 -> 1 -> 3<ref name='binary_search_tree'></ref>
+- 4 -> 2 -> 5 -> 1 -> 3
 === 후위순회 (postorder) ===
 루트 노드에서 시작해서 왼쪽 서브트리 -> 오른쪽 서브트리 -> 노드 순으로 순회하는 방식
-- 4 -> 5 -> 2 -> 3 -> 1<ref name='binary_search_tree'></ref>
+- 4 -> 5 -> 2 -> 3 -> 1
 == 이진 트리 (binary tree) ==
@@ 53번째 줄: / 53번째 줄: @@
 :이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됐다.
 :예를들면 이진탐색의 경우 탐색에 소요되는 계산복잡성은 O(logN)으로 빠르지만 자료입력이나 삭제가 불가능하다.
-:연결 리스트의 경우 자료입력, 삭제에 필요한 계산 복잡성은 O(1)로 효율적이지만 탐색하는 데에는 O(n)의 계산 복잡성이 발생한다. 이 두개의 장점을 살려보는 것이 이진 탐색트리의 목적이라고 할 수 있다.<ref name='binary_search_tree'></ref>
+:연결 리스트의 경우 자료입력, 삭제에 필요한 계산 복잡성은 O(1)로 효율적이지만 탐색하는 데에는 O(n)의 계산 복잡성이 발생한다. 이 두개의 장점을 살려보는 것이 이진 탐색트리의 목적이라고 할 수 있다.
-[[파일:이진탐색트리.png]]<ref name='binary_search_tree'></ref>
-=== 속성 ===
-* 각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값을 지닌 노드들로 이루어져 있다.
-* 각 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 값을 지닌 노드들로 이루어져 있다.
-* 중복된 노드가 없어야 한다.
-*왼쪽 서브트리, 오른쪽 서브트리 또한 이진 탐색트리이다.
-*이진 탐색트리를 순회할 때에는 중위순회(inorder)방식을 사용한다.
-:- 왼쪽 서브트리 -> 노드 -> 오른쪽 서브트리 순으로<ref name='binary_search_tree'></ref>
-[[파일:이진탐색트리속성.png]]<br><ref name='binary_search_tree'></ref>
-위의 그림에서 중위순회를 사용한다면, 순서는 1, 3, 5, 7, 8, 10 순서로 순회한다.<ref name='binary_search_tree'></ref>
-{{ 각주 }}
-== 참고자료 ==
-* adam2,〈[https://velog.io/@adam2/TREE 자료구조 Tree]〉, 2020년 4월 5일</ref>
-* hanrimjo,〈[https://velog.io/@hanrimjo/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%ED%8A%B8%EB%A6%AC-Binary-Search-Tree-8gk6ablvfx 이진 탐색 트리]〉, 2020년 2월 7일
 == 같이 보기 ==
 * [[자료구조]]
-{{데이터|검토 필요}}
+{{데이터|토막글}}