-
요즘 프로그래밍을 공부하는 사람들을 만나면, 다들 '자료구조 = 코딩테스트 준비' 라는 생각을 하고 있는 것 같습니다.
저는 수학에 사칙연산이 기본이라면, 코드를 작성할 때는 자료구조가 그 역할을 한다고 생각하는데요.
일하면서 트리에 익숙하지 않아서 고생했던 적들이 있어서, 트리에 관한 글을 써보려고 합니다.
1. Tree 란?
트리는 노드(Node)와 간선(Edge)로 이루어져있고, 순환이 존재하지 않는 계층적 자료 구조입니다.
https://www.programiz.com/dsa/trees 간단하게 생각해보면, 트리는 이름에서 알 수 있듯이 나무를 뒤집어 놓은 모양입니다.
하나씩 살펴보면, 노드(Node)를 가지가 뻗어져 나오는 마디라고 생각하고 간선(Edge)을 마디라고 생각하면 좋을 것 같네요.
그리고 순환이 존재하지 않는다는 것은 노드가 자기 자신을 다시 방문할 수 없다는 것 입니다. (아래에서 다시 살펴볼게요)
마지막으로 계층적 구조라는 것은 노드간의 상하 관계가 있는 것 입니다.
(여유가 되시는 분들은 트리가 재귀적이라는 표현에 대해서 생각해 봐도 좋을 것 같네요)
2. 왜 Tree를 사용해야할까
여러가지 이유들이 있겠지만, 저는 두 가지 관점에서 이야기를 해보고 싶습니다.
1) 계층구조를 직관적으로 표현할 수 있다.
쇼핑몰의 카테고리 이미 현실세계에서 많은 개념들은 계층 구조를 이루고 있습니다. 위의 예시는 쇼핑몰 카테고리를 트리 구조로 한번 나타내 보았습니다.
이런 구조를 가지고 있는 개념을 컴퓨터로 옮겨오기에는 트리가 가장 적절하지 않을까요?
이 뿐만 아니라 회사의 조직도, 가족관계도 같은 개념들도 모두 계층 구조를 이루고 있기 때문에 트리를 사용한다면 직관적으로 표현할 수 있습니다.
https://www.freecodecamp.org/news/what-is-the-dom-document-object-model-meaning-in-javascript/ 컴퓨터 세상에서는 어느 곳에서 트리를 쓰고 있을까요?
우리가 html을 작성하면 브라우저가 그 것을 tree 형태로 파싱해서 사용하고 있습니다.
또 더 가까이에서 살펴본다면 폴더 구조도 계층을 이루고 있다는 것을 확인할 수도 있습니다.
우리는 이미 알게 모르게 트리 구조를 많이 사용하고 있었던 것을 알게 되었네요.
2) 탐색 성능의 효율성 증가
위에 언급한 내용은 사람의 인지적 측면에서 유리함이 있다는 내용이었습니다.
그렇다면 컴퓨터 공학적인 측면에서는 어떨까요?
트리는 다양한 형태로 표현될 수 있는데, 이 중 특정 조건을 만족하는 트리들에서는 효율적인 데이터 검색이 가능합니다.
https://velog.io/@heyday_7/Binary-Search-Tree 위의 경우는 이진 검색 트리라는 형태로 데이터를 구조화하였고, 이런 경우에는 특정 노드를 찾는데 평균적으로 O(logN) 효율을 낼 수 있습니다.
https://rebro.kr/167 위 이미지는 조금 더 복잡해 보이죠?
B tree를 표현하는 이미지 입니다. B tree는 데이터베이스의 index에 사용되는 자료구조인데, 역시 빠른 데이터 검색을 위해사용 되는 자료 구조입니다.
여러가지 예시를 소개해드렸는데, 자세한 내용은 이어지는 글에서 소개하겠습니다.
지금은 이런 이유들로 트리 구조를 사용한다고 봐주시면 좋을 것 같습니다.
3. 트리에 사용되는 용어들
1) 루트 (Root)
가장 최 상단에 위치한 노드(Node)를 가리키는 용어 입니다.
2) 부모노드 (Parent)
계층 구조를 부모 자식으로 흔히 표현합니다.
자신 노드와 직접 연결된 상위 노드를 의미합니다.
3) 자식노드 (Children)
반대로 자신 노드의 하위에 연결된 노드를 의미합니다.
트리 형태에 따라 자식 노드의 숫자가 달라질 수 있습니다.
4) 형제노드 (Sibiling)
같은 부모를 가지고 있는 노드를 의미합니다.
5) 레벨 (Level)과 높이 (Height)
1개의 부모와 1개의 자식으로 이루어진 트리는
2개의 Level을 가지고 높이가 1이라고 할 수 있습니다.
6) 리프노드 (Leaf)
노드 중 가장 말단에 위치한 노드입니다.
자식 노드를 가지고 있지 않은 노드를 의미합니다.
구체적인 트리의 형태와 구현에 대해서는 다음 글들에서 알아보도록 하겠습니다.
[이미지 출처]
https://www.freecodecamp.org/news/what-is-the-dom-document-object-model-meaning-in-javascript/https://velog.io/@heyday_7/Binary-Search-Tree
'CS > 자료구조' 카테고리의 다른 글
BST - Binary Search Tree (1) 2023.12.29