Tree 에 대해서 알아보자! (자료구조, 알고리즘)

안녕하세요 원재입니다 ^ㅡ^ 이번 글에서는 빠른 탐색을 위해 사용되는 트리 자료구조에 대해서 알아보려고 합니다!

Tree 는?

Tree 는 말 그대로 나무입니다 ^ㅡ^ 읽어주셔서 감사합니다가 아니라 생뚱맞게 왜 자료구조를 공부하기 위해 작성된 게시글에서 갑자기 나무 사진을 들고 여러분들에게 소개를 하고있을까요? 한번 위에 있는 나무를 뒤집어 볼까요?

독자분들이 물구나무서기를 할 필요없이 제가 완벽하게 뒤집었습니다. 근데 이게 무슨 소용이 있길래 제가 어마무시한 노력과 정성 그리고 시간을 들여 나무를 뒤집어버렸을까요? 바로 아래 배울 자료구조로서의 트리의 생김새가 마치 나무를 뒤집은 것과 비슷하게 생겼기 때문입니다.

위 그림이 우리가 알아볼 트리입니다. 꽤나 비슷하게 생기지 않았나요? 사실 저도 뒤집어놓고 아직은 잘 모르겠네요. 하지만  트리를 구성하고 있는 여러가지 배울 용어들이 '나무' 와 관련된 용어들로 구성되어있습니다. 속는샘 치고 천천히 개념과 용어에 대해서 알아볼까요?

Tree 의 구성

위 그림을 보면서 차근차근 알아보겠습니다.

노드(node)로 구성되어 있는 트리는 나무와 마찬가지로 항상 루트(root) 노드라는 뿌리를 가지고 있습니다. 다시 말하자면 루트 노드는 부모가 없는 노드로 트리는 오직 하나의 루트 노드만을 가지게 됩니다.

나무와 같이 뿌리를 가지고 가지를 통해 노드들을 연결합니다. 이 때 우리는 노드를 연결하는 선을 브랜치(branch, 가지의 영어단어!), 링크, 간선, 엣지라고 부릅니다.

루트 노드는 Level 0 에서 시작합니다. 여기서 Level이란 depth, 즉 트리의 깊이를 얘기합니다. 루트 노드는 하나만 가질 수 있으므로 Level 0 로 정의합니다! 따라서 위 그림의 Level 은 3, 즉 깊이가 3이라는 것을 알 수 있겠네요.

그림을 잘 보시면 노드들끼리 위 혹은 아래로 연결되있는 것을 확인 할 수 있을텐데요, 이때 한 노드의 아래에 달려있는 노드를 자식 노드 라고 합니다. 그렇다면 위에 달려있는 노드는 당연히 부모 노드라고 하겠네요. 그리고 하나의 부모 밑에 달려있는 자식들은 형제기 때문에 형제 노드라고 부릅니다! 이런 구조를 반복해서 트리를 구성하게 됩니다.

Tree 의 종류

흔히 알아둬야 할 트리는 이진 트리와 이진 탐색 트리가 있습니다. 이진 탐색 트리를 통해 우리는 보다 빠른 데이터 검색이 가능케 할 수 있습니다. 이진 탐색 트리는 이진 트리에서 조건이 추가적으로 붙은 트리를 얘기합니다. 먼저 이진 트리를 살펴보면서 시작하겠습니다.

이진 트리는 위와 같이 노드의 최대 branch 가 2인 트리를 얘기합니다. 여기서 최대라는 것은 2를 넘어서지 않는 다는 얘기로, 0~2 까지의 branch 를 가질 수 있는 경우를 얘기합니다. 간단하죠?

이 간단한 이진 트리에서 우리는 추가적인 조건을 하나 붙일려고 합니다. 앞으로 하나의 노드에 달린 노드들 중 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지도록 하겠습니다. 글로만 보면 조금 어려울 수 있으니 한번 그림을 통해 이해해볼까요?

출처(https://blog.penjee.com/5-gifs-to-understand-binary-search-tree/#binary-search-tree-insertion-node)

조건이 이해가 되시나요? 루트에 21 노드로부터 시작된 후 만약 작다면 왼쪽, 크다면 오른쪽 이동을 반복하며 트리가 구성됩니다. 우리는 이 트리는 이진 탐색 트리(Binary Search Tree, BST) 라고 부릅니다.

그렇다면 대체 이 트리가 어떻게 해서 빠른 탐색을 가능토록 할까요? 우리는 자료 저장시 주료 배열을 사용합니다. 배열과 이진탐색트리에서 원하는 값을 찾는다고 상황을 가정하고 아래의 그림을 통해 상황을 진행해보도록 하겠습니다.

트리와 배열 둘다 같은 숫자들로 구성되있습니다. 타겟 넘버 27을 찾기위해 배열에서 무려 10번을 움직이는 동안 이진 탐색 트리에서는 단 3번만의 스텝을 통해 값을 찾는데 성공했습니다!

엄청나....!

하지만 언제나 이렇게 빠른 속도로의 탐색이 가능한 것은 아닙니다. 역시 최악의 경우를 한 번 살펴 봐야겠죠? 만약 아래와 같이 트리가 구성된다면 어떨까요?

??????

 

ㅡㅡ;;

만약 이렇게 된다면 우리는 배열과 다름없이 똑같이 O(N) 의 속도를 가지게 됩니다. 이 경우를 제외하면  대부분의 탐색에서는 O(logN) 의 속도를 가질수 있다는 장점을 가지고 있습니다. 참고로 이과를 나온 대부분의 여러분들이 밑이 없는 로그는 상용로그로 10을 가진다고 생각하실텐데요 알고리즘에서는 밑이 없는 경우 2를 밑으로 가지고 있다고 생각하시면 됩니다! 로그 2의 N 승이에요!

마치며

이번에는 트리에 대해서, 특히 이진 트리와 이진 탐색 트리에 대해서 알아봤습니다. 대단한 내용보다는 '트리란 이런거구나~' 라는 부분을 쉽게 알 수있도록 정리해봤어요 ^ㅡ^ 날이 슬슬 풀리려고 하는 조짐이 보이는것 같습니다! 이럴 때 일수록 감기 조심하시고 다들 화이팅이에요!