트리자료구조_on c[1]

본 포스트는 c언어를 중심으로 작성되었습니다.

 

트리자료구조_on c[1]

 

저번 스택, 큐에 이어 트리 자료구조에 대해 포스팅을 할까 합니다. 트리 말 그대로 트리입니다. 나뭇가지 처럼 뻗어져 나가는 것 처럼 생겼습니다!

 

출처 : howstuffworks

아주 쭉쭉 뻗어져 나가는 것이 보기 좋습니다! 위를 보듯 트리자료구조는 리스트, 스택, 큐 와 다르게 1:1 선형구조가 아니라 1:다, 즉 1:n 의 비선형 자료구조를 지닙니다. 흔히 계층형 자료구조라고도 합니다.

 

우리가 흔히 볼 수 있는 가족 관계도, 기관의 조직도 등이 이에 속한다고 보시면 됩니다.

 

트리자료 논리적 구조

위의 논리적 구조를 따릅니다. 최상단에 위치한 노드가 최상위 노드, 즉 트리의 시작점이 됩니다. 최상단 트리는 현재 7개의 노드를 가지고 있습니다. 보통 시작하는 노드를 루트라고 합니다. 검은 원은 단말 노드로써 더이상 상속하는 노드가 없다는 의미를 지닙니다. 혹은 리프(leaf)노드라고도 불리웁니다!

 

이런 트리들이 하나가 있을땐 단개 트리이지만, 여러개의 집합체를 두고 포레스트 트리라고 합니다. 

 

그렇다면 이런 트리자료구조는 어떻게 이해할까요?

 

우선 이진트리 자료구조를 확인 해보겠습니다

 

이진 트리 자료구조는 트리의 모든 노드 차수를 2 이하로 제한하여, 모든 트리의 노드 차수를 2 이하로 만들어 놓은것을 의미합니다. 

 

또한, 이진트리에서는 루트에서 내려오는 자식노드 한쪽이 공백노드라고 하여도, 이진트리라고 합니다.

이진 트리의 논리구조

 

이해를 돕기 위해 이진트리의 논리구조를 작성하였습니다. 이진트리는 앞서 설명했듯, 최소 두개 이하의 노드가 부모 노드를 상속하고 있어야 한다 말씀드렸습니다.

 

총 노드가 n개 있다고 가정해볼때 이진트리는 항상 간선이 n-1개를 갖습니다. 여기서 간선이란, 노드 간 연결된 선을 의미합니다. 

 

또한 사용자 정의 트리 노드의 레벨이 n개가 되기 위해선, 최소한 한개의 노드가 필요홥니다 .무슨말인 즉슨, 이진트리의 레벨이 m이라고 가정한다면, 위의 조건을 이어받아, 최소한 두개 이하의 노드를 구성하는 것이 이진트리라고 하였듯,최소한 한개의 노드가 위하여야 한다는 뜻입니다. 즉 레벨이 0부터 시작하기 때문에 높이가 m인 이진트리의 최소 노드 개수는 m + 1개가 됩니다. 잠시 위의 트리구조 사진을 보게되면 알 수 있듯이, 레벨 2의 노드개수는 알다시피 4개가 존재합니다. 또한 앞선 조건 중 트리는 두개 이하의 노드를 구성해야 하기 때문에 레벨 l에서는 노드 개수는 2^l이 성립합니다. 따라서 사용자 정의 노드의 레벨이 n이 되기 위해서 최대 노드 개수를 구해볼때  sigma(h, l=0) 2^l = 2^n+1 -1 이 성립함을 알 수 있습니다. 

 

그렇다면 이진 자료구조의 종류에는 어떤 것이 존재할지 확인해보겠습니다.

 

이진트리의 종류

 

위 사진과 같은 이진트리를 우리는 일반 이진트리라고 할 수 있겠습니다. 일반적인 모델이라는 뜻입니다. 반면 레벨과 노드의 수에 따라서 형성되는 모델은 포화 이진트리, 완전 이진트리, 편향이진트리 가 존재합니다.

 

포화 이진 트리(Full Binary Tree)	모든 레벨에 노드가 포화상태라 레벨을 늘리지 않는 한 노드를 더이상 추가할 수 없는 말 그대로 포화 상태의 이진트리입니다.
완전 이진 트리(Complete Binary Tree)	레벨이 m일때, 노드 수가 n개 일때, 노드의 인덱스 1번으로 부터, n번까지의 위치가 일치 하는 이진 트리입니다.
편향 이진 트리(Skewed Binary Tree)	말그대로 한쪽에 편향(치우져 있다)되어 있는 트리 입니다. 한쪽으로만 서브 트리를 지닌 트리입니다.

쓰다보니 너무 내용이 많아 정리하기가 힘드네요ㅜㅜ 좀 더 정리해서 내일 포스팅 하도록 하겠습니다.

 

 

 

댓글 피드백 감사합니다!