자료구조 개념 정리 - 트리 개념 및 기초

트리는 노드로 이어진 트리형태의 자료 구조를 뜻합니다.
먼저 트리의 특징에 대해 알아보도록 하죠.
트리는 여러 노드들의 집합이라 볼 수 있습니다. 이 집합의 노드들은 각각의 서로 다른 자식 노드들을 가지고 그 노드들은 재사용이 되지않는 구조입니다.
자료구조의 비선형구조 분류에 속한 구조로 1:N 즉, 하나의 노드에 여러가지의 자식들이 할당 되는 구조입니다.

이 그림을 보시면 하나의 노드에 여러 노드들이 할당되는 구조입니다.
선형구조에 대해 알아보았을대 선형구조는 1:1 형태의 특징을 갖고 있었고, 비선형구조는 1:n특징을 갖고 있었습니다.
이해하기 쉽게 예를들어 트리를 이해하자면 트리메뉴가 있죠. 트리 구조 형태의 메뉴
즉, 루트를 부모로 해서 여러 자식노드를 가지는 구조라 트리메뉴라고 불리죠.
이처럼 나무의 뿌리형태처럼 하나의 루트를 가지고 가지치기를 하는 형태입니다.
그래서 최상위 부모를 root라고 부르고,
최하위 노드를 leaf라고 부릅니다.

용어 정리
뿌리(Root) 노드 - 최상위 노드
자식(Child) 노드 - 어떤 노드의 하위 노드
부모(Parent) 노드 - 어떤 노드의 상위 노드
형제(Brother,Sibling) 노드 - 어떤 노드의 같은 등급의 노드
잎(Leaf) 노드 - 자식 노드가 존재하지 않는 노드
가지(Branch) 노드 - 자식 노드가 하나라도 존재하는 노드중에 Root가 아닌 노드
깊이(Depth) - 루트에서 어떤 노드까지의 경로의 갯수
레벨(Level) - 같은 깊이의 집합
높이(Height) - 이 트리에서 가장 높은 깊이
차수(Degree) - 어떠한 노드의 자식의 갯수
간선(Edge,Link) - 한 노드와 다른노드 사이의 연결선

트리는 많은 양의 데이터 저장에도 용이하고 계층형 구조의 자료를 구현해야 할 경우 용이합니다.

트리의 종류도 한번 알아볼까요?

이진트리 - 이진 트리가 되려면, 루트 노드를 중심으로 둘로 나뉘는 두 개의 서브트리도 이진 트리이어야 하고, 그 서브 트리의 모든 서브 트리도 이진트리여야 합니다.
포화 이진 트리(Full Binary Tree) - 모든 레벨이 꽉 찬 이진 트리
완전 이진 트리(Complete Binary Tree) - 포화 이진 트리처럼 모든 레벨이 꽉 찬 상태는 아니지만, 차곡차곡 빈 틈 없이 노드가 채워진 이진 트리