패스트캠퍼스 챌린지 8일차

기본 자료구조 가운데 가장 복잡하고 활용성높다는 트리. 정보처리기사 시험 벼락치기때 트리 구조를 이해하느라 약간 애를 먹었던 기억이 있다. 너무 복잡하고 전혀 이해하지 못하겠다~ 는 당연히 아니었지만 단순암기식 시험에서 이해력을 요구하는 몇 안되는 파트였기 때문에... 출제빈도가 낮은 파트였더라면 신경쓰지 않았을텐데 정말 중요한 부분이라고 해서 나름대로 주의를 기울여 공부했었다. 일단 여기 하나에 달린 용어들만 해도 한두개가 아니다보니 익숙해지지 않으면 정말로 헷갈리기 쉬운 파트라고 생각한다.

 

트리에는 데이터의 계층 개념이 들어간다. 트리는 기본적으로 노드, 그리고 노드들을 잇는 가지(edge)로 구성된다. 최상위에 있는 노드는 루트 노드, 하위 노드가 존재하지 않는 트리의 끝 노드를 리프 노드라고 한다. 리프를 제외한 노드를 '비단말 노드(non-termonal node)'라고 부르며, 루트 노드 또한 비단말 노드에 포함됨에 주의한다. non-terminal node를 internal node라고도 부른다.

같은 부모를 공유하는 자식노드들을 sibling, 즉 형제노드라고 부르고 상속처럼 ancestor, desecendand, parent, child의 개념이 적용된다. 한 노드의 자손 노드들로 구성된 트리를 서브트리라고 한다. 반면 노드와 가지가 전혀 없는 트리를 None tree 내지는 Null tree라고 부른다.

왠지 디그리와 레벨을 자주 헷갈리곤 했는데, 각 노드가 가지는 자식의 수를 디그리(차수)라고 하며 트리에 포함된 노드들의 디그리 가운데 가장 큰 것을 해당 트리의 디그리라고 한다. 예를 들어, 어떤 트리 a에 포함된 노드들의 디그리<=n이라면 해당 트리는 n진 트리이다. 반면 레벨은 루트에서 얼마나 멀리 떨어져 있는지, 즉 쉽게 말해 트리의 층같은 개념이다. 루트노드의 레벨은 0이며, 밑으로 가지가 하나씩 내려갈때마다 레벨이 1씩 추가된다. 루트에서 가장 멀리 떨어진 리프까지의 거리를 트리의 높이height라고 한다.

 

 

 

 

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

※ 본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.