트리에 관하여 00

웹 크롤러 제작 중, 관련 라이브러리가 트리 형식으로 데이터를 저장하여 아름아름 알아가던 트리에 관해 정리하고자 해당 포스팅을 작성한다.

[1] Tree 소개

Tree 는 기존의 자료구조(선형 자료구조)와는 조금 다른 특징을 가진다.

기존의 자료구조가 데이터를 와르르 저장했다가 와르르 가져다 쓰는 용도였다면, 트리는 데이터의 '표현'에 초점이 맞춰진 자료구조이다.

(그림으로 표현하면 위와 같은 형태의 데이터 구조를 가지고 있다.)

가장 큰 특징이라면 데이터의 구조가 계층적 이라는 것!

트리 형태의 자료구조는 위에서 언급 했듯이 표현 에 적합한 자료구조라서 관련 코드를 작성하거나 분석할 때, 아래와 같이 접근해야 한다.

"트리의 구조로 이뤄진 무엇인가를 표현하기에 적절히 정의되어 있는가?"

트리는 계층적인 자료를 표현하기에 가장 적절한 자료구조이다. 컴퓨터의 디렉터리 구조, 기업 및 장부의 조직도 등이 그 예 이다.

또한 "Yes or No"를 연속적으로 사용하여 의사결정을 수행하는데 필요한 자료구조 역시 트리를 이용해 구현이 가능하다.

(의사결정 트리, Decision Tree 라고 한다.)

(Decision Tree의 예)

자 그럼 본격적으로 Tree에 관해 알아가기 앞서, 한가지 확실히 해두고 가야 할 개념이 있다.

"트리를 이용해서 무엇인가를 저장하고 꺼내야 한다는 생각은 지우고, 무엇인가를 표현하는 도구 라고 생각하자"

계속해서 강조하지만 Tree는 표현을 위한 자료구조 이다!

[2] Tree 용어 정리

사용처가 조금은 특이한 자료구조 답게 트리와 관련해서는 제법 많은 용어들이 정의되어 있다.

이를 하나씩 알아가며 정리해 보도록 하자.

1. Node

다양한 자료구조에서도 사용하는 용어이다. 트리에서도 역시 사용된다. 노드는 트리의 가장 기본적인 구성요소를 표현할 때 사용하는 용어이다.

위 그림에서 A, B, C, D, E, F, G, H, I 가 노드에 해당된다.

2. 간선

노드와 노드를 연결하는 연결선 이다.

3. Root node

트리구조 최상위에 위치한 노드 이다.

4. Terminal node

아래로 또 다른 노드가 연결되어 있지 않은 단말노드 이다. (H, I, J 가 해당)

5. Internal node

단말노드(Terminal node)를 제외한 모든 노드 이다.

그리고 노드의 관계에 대해 설명하는 다른 용어도 있다. 부모(Parent), 자식(Child), 형제(Sibling)과 같은 용어가 있다.

Example)

- 노드 A는 B, C의 부모 노드 이다.

- B, C는 A의 자식 노드 이다.

- B, C는 부모 노드가 동일 하므로, 서로가 서로에게 형제 노드 이다.

가볍게 가볍게 읽으면서 정보를 아름아름 얻어 가는 곳 이 블로그 아니겠는가!

그 본연의 목적에 부합하도록 슬슬 머리 아파 올쯤 에 쉬었다가 다음 포스팅에서 쭉 다루고자 한다!

오늘은 트리 자료구조가 뭔지 에 대해 간략히 알아봤다. 다음 포스팅에 이어서 이진트리(일반 트리와는 다르다!) 와 그 이진트리의 구현에 관해서 알아보도록 하겠다.

PS)

혹 질문사항이 있거나 물어보고 싶은게 있으시면 댓글을 적극 이용 부탁 드립니다 :)