📙 #자료구조_트리
정의
노드라고 하는 정보 항목이 간선으로 연결되어 계층적 구조를 이루는 비선형 구조
용어 설명
노드 : 트리의 각 항목 ex) 2,7,2,4…
차수 : 어떤 노드의 서브트리 수를 그 노드의 차수/분기수 라고 한다.
ex) 2번의 차수는 2, 4번의 차수는 0
단말 노드 : 차수가 0인 노드를 리프/단말 노드라고한다
트리의 차수 : 어떤 트리의 차수는 트리 내의 노드 차수 가운데 최대 차수를 의미. 아래 트리의 차수는 2
레벨 : 루트 노드로부터의 거리를 의미. 루트 자체는 거리가 0 이므로 레벨이 0.
높이/깊이 : 트리에 속하는 노드 중에서 가장 큰 레벨에 1을 더한 것
숲 : 분리된 트리의 집합. 트리에서 루트를 제거하면 숲이 된다. 아래 그림에서 루트를 제거하면 두개의 트리로 된 숲이 된다.
트리 종류
순서 트리/비순서 트리/대등한 트리/이진 트리 등 여러가지 트리가 존재.
여러 항목이 있으므로 필요할 때 검색
📙 #자료구조_이진트리
정의
각 노드의 차수가 2이하인 순서트리
스레드 이진트리, 이진 탐색 트리와 같이 다양한 형태로 여러 영역에서 사용됨
일반 트리와의 차이점
일반트리 : 최소 한 개 이상의 노드를 가져야 한다 / 자식의 순서를 구분하지 않음
이진트리 : 0개의 노드를 가진 공백도 이진 트리에 포함 / 자식의 순서를 구분해 왼쪽,오른쪽 서브트리로 나눈다.
이러한 점에서 둘은 다른 자료객체라 할 수 있다.
특성
- 레벨 i에서의 최대 노드의 수는 2^i 이다 (단, i >= 0 )
- 기타 특성 존재
이진 트리의 종류
- 포화 이진 트리 : 모든 단말노드의 높이가 같음
- 전 이진 트리 : 모든 노드의 차수가 0이거나 2
- 완전 이진 트리 : 마지막 레벨을 제외한 모든 레벨에서 왼쪽부터 오른쪽으로 노드가 채워져 있음
- 균형 이진 트리 : 모든 단말 노드의 깊이 차이가 많아야 1인 트리
댓글