자료구조 트리(Tree) 그림으로 쉽게 이해하기

자료구조 트리(Tree) 그림으로 쉽게 이해하기

 

안녕하세요.

로스윗의 코딩캠프입니다.

오늘은 자료구조 중에서 트리(Tree)에 대한 포스팅을 진행하겠습니다.

그림 으로 쉽게 이해할 수 있으니 끝까지 잘 따라와주세요 :)

 

- 트리(Tree)란?

우선 트리(Tree)는 한 노드(Node)가 여러 노드를 가리킬수 있는 비선형적 자료구조입니다.
리스트(list)나 스택(Stack), 큐(Queue)는 데이터의 이전 데이터나 다음 데이터의 순서가 존재했었죠.
물론 트리(Tree)도 내부적으로 순서정보를 가질 수 있도록 구현할 수도 있지만

트리라는 자료구조 자체에서 데이터의 순서는 그렇게 중요한 요소는 아닙니다.

트리(Tree)는 순서보다는 데이터 구조의 계층적인 상하관계를 표현할 때 주로 사용하고,

뒤에서 다루게 될 그래프라는 자료구조의 일종이라고 생각하시면 됩니다.

쉬운 예시로는 우리가 컴퓨터에서 쓰는 파일 폴더의 구조가 대표적인 계층형태 데이터 구조로 볼 수 있습니다.

 

대표적인 계층형태 구조인 파일 폴더 구조

 

 

- 트리구조 도식화

가장 상위 폴더가 있고 그 아래 하위 폴더가 있고 또 그 아래 또 하위폴더가 있는 구조겠죠.
이렇게 데이터 간에 상하위 관계가 존재하는 데이터 구조를 표현할 때 트리를 사용할 수 있습니다.
이것을 도식화하면 그림과 같은 모양으로 표현할 수 있습니다.

 

 

트리구조 도식화

 

 

- 트리의 노드(Node), 루트(Root), 엣지(Edge)

A데이터가 가장 상위에 있고, 하위에 B와 C의 데이터를 가지고 있죠.

그리고 B는 하위로 D,E,F의 데이터를, C는 G,H의 데이터를 가리키고 있습니다.

이렇게 트리를 구성하는 각 데이터 원소들을 노드(Node)라고 합니다.
그리고 트리에서 부모가 없는 최상의 노드를 루트노드(RootNode)라고 합니다.

루트(root)는 트리의 시작점이 되고, 트리는 최대 1개의 루트노드를 가질 수 있습니다.
그리고 이 노드를 연결하는 노드간에 선을 엣지(edge)라고 합니다.
그래서 트리는 루트(root)로 부터 시작해서 엣지(edge)로 연결된 노드(node)들로 구성되어 있다고 말할 수 있습니다.

 

 

트리구조의 루트와 엣지

 

 

- 트리의 부모노드, 자식노드, 형제노드, 리프(leaf)노드

그리고 이 트리의 계층적 속성에서 상위에 존재하는 노드를 부모노드,

부모노드의 하위에 위치한 노드는 자식노드가 됩니다.

그리고 같은 부모를 갖는 노드는 형제노드라고 할 수 있습니다.

 

그림에서 A는 부모노드가 될 수 있고, B와 C는 A노드의 자식 노드가 될 겁니다. 

그리고 같은 부모를 두었기 때문에 B와 C는 서로 형제노드라고 볼 수 있겠습니다.
그런데 이 B와 C는 A를 기준으로 했을 때는 자식노드였지만,

G와 H를 하위에 가지고 있기 때문에 G와 H노드에 있어서 C는 부모노드가 될 수 있는 것입니다.

마찬가지로 B도 A앞에는 자식노드였지만 하위로 가지고 있는 D,E,F앞에서는 부모노드가 될 수 있습니다.
그래서 루트(root)노드는 최상위에 있는 하나의 노드만을 가리키는 것이고,

부모노드와 자식노드는 트리내에서 상대적인 개념이라고 이해하시면 되겠습니다.

 

그리고 이때 각 노드의 자식수는 차수 degree로 표현합니다.
여기서 B노드는 자식을 셋을 가진 degree3의 노드가 되겠죠.
그리고 자식이 없는 노드는 낙엽을 뜻하는 리프(leaf)노드라고 부르고,

데이터의 끝부분이기 때문에 터미널 노드라고도 합니다.
그림에서는 D, I, J, F, K, H가 리프(leaf)노드가 될 수 있습니다.

 

 

부모노드 자식노드 형제노드 리프노드 설명 그림

 

 

- 트리의 경로(Path)

노드에서 다른 노드에 이르는 사이에 노드순서는 경로(path)라고 합니다.
그래서 A노드부터 K노드까지의 경로는 [A - C - G - K] 노드가 될 것이고,

이때의 경로는 중복 노드를 포함하지 않습니다.

예를 들어서 A부터 F까지의 경로는 [A - B - F]로 표현을 하지,

[A - B - E - B - F] 이런식으로 표현하지 않는다는 것이죠.

 

 

트리의 경로(Path)

 

 

- 트리의 깊이(Depth)

그 다음으로 노드에서 root까지의 거리를 깊이(Depth)라고 합니다.
노드 B와 C는 루트로부터 깊이(Depth)가 1인 거리에 위치해 있죠.
그리고 노드 D, E, F, G는 깊이(Depth)가 2인 위치에 존재합니다.
그리고 노드 H, I, J는 깊이(Depth)가 3으로 여기서 가장 깊은 깊이(Depth)를 가지게 되겠죠.
이렇게 가장 큰 깊이(Depth)는 트리의 높이라고 표현을 합니다.

 

 

트리의 깊이(Depth)

 

 

- 트리의 레벨(Level)

그리고 같은 깊이(Depth)를 가진 노드의 집합을 그 트리의 레벨(Level)이라고 합니다.
우선 루트(Root)노드는 level 0에 있게 되고, B와 C는 동일한 level 1에 있는 노드가 되고,

D, E, F, G는 깊이(Depth)가 2로 같은 level 2에 위치한 노드들이 될 것이고,
마지막으로 H, I, J는 level 3에 위치한 노드의 집합이 되겠습니다.

 

 

트리의 레벨

 

 

- 트리의 서브트리(SubTree)

그 다음으로 트리의 하위 노드는 서브 트리를 구성한다는 재귀적인 특성을 갖습니다.
다시 말해서 A를 루트(root)로하는 전체 데이터는 당연히 트리를 구성을 하고 있겠죠.
그리고 A의 자식인 B도 B를 루트로하는 하나의 서브트리로 볼 수 있는 것입니다.
그리고 B의 자식인 D도 마찬가지로 자신의 서브트리를 구성할 수 있게 되죠
그래서 트리는 재귀적인 구조를 가지고 있다는 것이 굉장히 중요한 특징입니다.

 

 

트리는 트리의 하위노드는 서브트리를 구성한다는 재귀적인 특징이 있다

 

 

- 트리의 경사트리

그래서 트리는 우리가 앞에서 본 것처럼 예쁘게 그려지는 모양도 트리가 되지만,
아래 그림처럼 하위의 노드를 하나씩만 가지는 트리도 트리입니다.
이렇게 모든 노드가 하나의 자식만을 가질 경우를 [경사트리]라고 부릅니다.

그리고 모든 노드가 왼쪽에 자식을 가진다면 왼쪽 경사트리라고 하고,
마찬가지로 오른쪽에만 자식을 같는다면 오른쪽 경사트리라고 합니다.

그리고 왼쪽 오른쪽 왼쪽 오른쪽인 모양의 트리도 경사트리의 일종이 됩니다.

 

 

경사트리 도식화

이런 트리는 특성에 따라서 여러 종류로 세분화 될 수 있습니다.

예를들면, 이진트리, AVL트리, 레드-블랙 트리, B-트리, B+트리, 세그먼트 트리, 트라이 등이 있습니다.

 

이 중에서 이진트리는 또 다른 파생트리들의 기초로 가장많이 활용되는 트리구조이기 때문에
다음 포스팅에서는 이진트리에 대해 알아보도록 하겠습니다.

감사합니다.

 

로스윗의 코딩캠프는

미래의 개발자 여러분을 응원합니다.

모두 화이팅!!

 

알고리즘 퀵정렬(Quick sort) 그림으로 쉽게 이해하기

 

원형큐(Circular Queue)를 반드시 사용해야 하는 이유 (ft. 그림으로 쉽게 설명)