위키원
"트리"의 두 판 사이의 차이
(→특징) |
(→이진 트리 (binary tree)) |
||
| 33번째 줄: | 33번째 줄: | ||
== 이진 트리 (binary tree) == | == 이진 트리 (binary tree) == | ||
| − | * '''이진 트리( | + | * '''이진 트리(binary tree)''' : 이진트리는 트리를 구성하는 노드들의 최대 차수(degree)가 2인 노드들로 구성되는 트리이다. |
:이진트리의 레벨 i에서 가질 수 있는 최대 노드의 수는 2^i이다. (i>=0) | :이진트리의 레벨 i에서 가질 수 있는 최대 노드의 수는 2^i이다. (i>=0) | ||
:깊이가 k인 이진트리가 가질 수 있는 최대 노드의 수는 2^k-1이다.(k>=1) | :깊이가 k인 이진트리가 가질 수 있는 최대 노드의 수는 2^k-1이다.(k>=1) | ||
| 48번째 줄: | 48번째 줄: | ||
:모든 레벨에 노드가 차있는 상태로 최대 노드 수인 2^k-1개로 채워져 있는 트리이다. | :모든 레벨에 노드가 차있는 상태로 최대 노드 수인 2^k-1개로 채워져 있는 트리이다. | ||
:전 이진 트리이면서 완전 이진 트리인 경우이다.<ref name='tree'></ref> | :전 이진 트리이면서 완전 이진 트리인 경우이다.<ref name='tree'></ref> | ||
| + | |||
| + | == 이진 탐색 트리 (binary search tree) == | ||
| + | * '''이진 탐색 트리(binary search tree)''' : 이진탐색과 연결리스트(linked list) 를 결합한 자료구조의 일종이다. | ||
| + | 이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됐다. | ||
| + | |||
| + | 예를들면 이진탐색의 경우 탐색에 소요되는 계산복잡성은 O(logN)으로 빠르지만 자료입력이나 삭제가 불가능하다. | ||
| + | 연결 리스트의 경우 자료입력, 삭제에 필요한 계산 복잡성은 O(1)로 효율적이지만 탐색하는 데에는 O(n)의 계산 복잡성이 발생한다. 이 두개의 장점을 살려보는 것이 이진 탐색트리의 목적이라고 할 수 있다. | ||
| + | |||
== 같이 보기 == | == 같이 보기 == | ||
* [[자료구조]] | * [[자료구조]] | ||
{{데이터|토막글}} | {{데이터|토막글}} | ||
2020년 8월 12일 (수) 09:19 판
트리(tree)는 일반적으로 대상 정보의 각 항목들을 계층적으로 연관되도록 구조화시키고자 할 때 사용하는 비선형 자료구조이다. 데이터 요소들의 단순한 나열이 아닌 부모-자식 관계의 계층적 구조로 표현이 된다.
목차
특징
- 그래프의 한 종류 이다. '최소연결 트리'라고도 불린다.
- 트리는 계층 모델이다.
- 임의의 노드에서 다른 노드로 가는 경로는 유일하다.
- 회로(cycle)가 존재하지 않는다.
- 모든 노드는 서로 연결되어 있다.
- 엣지를 하나 자르면 트리가 두개로 분리된다.
- 엣지의 수는 노드의 수에서 1을 뺀 것과 같다. (엣지 = 노드 - 1)
구조
- node: 트리를 구성하고 있는 각 요소
- Edge(간선): 트리를 구성하기 위해 노드와 노드를 연결하는 선
- Root Node: 최상위 계층에 존재하는 노드
- level: 트리의 특정 깊이를 가지는 노드의 집합
- degree(차수): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
- Terminal Node(=leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드
- Internal Node(내부노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.[1]
트리 순회 (tree traversal)
트리 순회란 트리의 각 노드를 체계적인 방법으로 방문하는 과정을 말한다. 하나도 빠뜨리지 않고 , 정확히 한번만 중복없이 방문해야한다.
노드를 방문 하는 순서에 따라 전위순회(preorder), 중위순회(inorder), 후위순회(postorder)세가지로 나뉜다.
전위순회 (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)라고 하는 특별한 트리 구조를 정의할 수 있다.[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)의 계산 복잡성이 발생한다. 이 두개의 장점을 살려보는 것이 이진 탐색트리의 목적이라고 할 수 있다.
같이 보기
