지금까지 배운 배열, 스택, 큐등은 모두 linear(선형) 구조입니다. 선형 구조라고 하면 데이터가 일렬로 늘어서 있는 형태를 의미합니다. [1, 2, 3, 4, 5] 이런식으로요! 이번에 알아볼 tree구조 같은 경우는 non-linear(비선형 구조)에 해당하는 대표적인 데이터 구조입니다. Tree에도 몇가지 종류가 있는데, 가장 기본적인 tree, binary tree(바이너리 트리) 그리고 binary search tree(BST, 바이너리 서치 트리)에 대해 알아보도록 하겠습니다.
데이터 구조의 형태가 마치 나무를 거꾸로 돌려놓은 듯한 모습이라고 하여 트리라고 부릅니다. 트리 구조에서 알고 있어야 할 명칭들이 몇가지 있는데 하나씩 알아보겠습니다.
먼저, 각각의 데이터를(위 그림에서 동그라미 부분!) node(노드)라고 부르고 parent node가 없는 최상단의 노드를 root라고 부릅니다. 그리고 root노드 아래로 뻗어 있는 노드들을 child node라고 부르고, 더 이상 child node가 없는 노드들을 leaf node라고 합니다. 하나의 큰 트리 구조 속에 있는 작은 트리들을 subtree(서브 트리)라고 하는데, 그 속에서 최상위 노드를 root라고 칭하기도 합니다. 그리고 노드와 노드 사이의 연결 선은 edge(간선)이라고 칭합니다.
Node의 위치를 표현하는 방법으로 level, depth 그리고 height이 있습니다.
- level이나 depth는 트리의 root node부터 얼마나 떨어져 있는지를 나타냅니다.
- height은 leaf를 시작점(leaf가 0)으로 하고 root node와 가장 멀리 떨어진 leaf node 사이의 edge의 수입니다. (모든 leaf는 height이 0이고 root node의 height은 가장 멀리 떨어진 leaf와의 사이에 있는 간선의 수와 동일합니다.
위에 나왔던 트리 구조의 level, depth 그리고 height을 표현하면 아래처럼 표현할 수 있습니다.
1. Binary Tree
Binary tree는 가질 수 있는 child node의 수에 제한이 있습니다. 각 노드는 0개에서 2개까지만 child node를 가질 수 있습니다. 왼편에 있는 node는 left node, 오른편에 있는 node는 right node라고 합니다.
2. Binary Search Tree
Binary Search Tree, 줄여서 BST(자꾸 BTS같네요😂)라고 불리는 이 트리구조는 이름에서도 알 수 있다시피 데이터 "search"를 용이하게 하기 위한 구조입니다. 그러다보니 데이터의 위치에 규칙이 있습니다. Root node의 값을 기준으로 하여 root보다 작은 데이터는 왼편에, 큰 데이터는 오른편에 정렬합니다. 그러면 트리 안에서 가장 작은 값은 제일 왼쪽에, 가장 큰 값은 제일 오른쪽에 위치한 값이겠죠? 그리고 각 데이터의 값은 유일하기 때문에, 중복된 데이터를 허용하지 않습니다.
BST를 사용하면 선형구조를 사용할 때보다 원하는 데이터를 빠르게 찾을 수 있습니다. 만약에 숫자 4를 찾고 싶다면, root node인 8보다 작은 숫자들만 놓여있을 왼편만 살펴보면 되겠죠. 그렇기 때문에 맨 처음부터 탐색할 데이터 수가 전체의 반정도로 줄어들게 됩니다. 그 다음에는 4가 3보다 크므로 3 노드의 오른편만 살펴보게됩니다. 이런식으로 탐색할 데이터를 절반씩 줄여나가므로 모든 데이터를 다 찾아보아야 하는 선형 데이터 구조에서보다 탐색이 빨라지게 되는 것입니다.
이렇게 tree 데이터 구조에 대한 기본적인 사항들을 간략하게 알아보았습니다. 내용은 대략적으로 알겠는데 어떻게 코드로 구현할 수 있는지 궁금하시죠! 다음번에는 직접 java로 어떻게 트리 구조를 만들어 내는지 코드로 살펴보도록 하겠습니다. 감사합니다. ☺️
참고자료
https://www.upgrad.com/blog/binary-tree-vs-binary-search-tree/
Binary Tree vs Binary Search Tree: Difference Between Binary Tree and Binary Search Tree | upGrad blog
Read this guide to learn Binary Tree vs Binary Search Tree from the leading domain experts. Learn everything about these two tree types and get familiar with some of the most prominent concepts.
www.upgrad.com
'Java > Data structure(자료구조)' 카테고리의 다른 글
| Graph class 만들기! (0) | 2022.06.01 |
|---|---|
| Non-linear(비선형)자료구조(2) - Graph(그래프) (0) | 2022.06.01 |
| Tree 구조 코드로 구현해보기 (0) | 2022.05.29 |
| Data structure(자료구조)란? - Stack & Queue(스택과 큐) (0) | 2022.05.27 |
