[자료구조] 트리(Tree)구조, 이진트리(Binary Tree)
나무를 거꾸로 뒤집어 놓은 듯한 이 자료구조를
트리구조라고 한다.
하나의 뿌리(가장 맨위 root)로부터 가지가 사방으로 뻗은 모양이 특징이다!
트리구조 =
- 단방향 그래프 : 아래로만 뻗어나간다 (사이클 X)
- 계층적 자료구조 : 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향(-)으로 연결되어있음!
- 비선형 구조 : 하나의 데이터 아래에 여러개 데이터 존재 가능
트리 구조, 특징
루트 : 데이터의 시작 노드, 하나의 꼭짓점
간선 : 여러개의 데이터를 잇는 선
노드 : 트리를 이루는 모든 개별 데이터
(1) 부모 노드 : 두 개의 노드가 상하 계층으로 연결될 경우 루트에서 가까운 노드
ex) 위의 구조에서는 2는 6과 7 노드의 부모노드
(2) 자식 노드 : 상하 계층 연결될 경우 루트에서 먼 노드
ex) 8과 9는 3의 자식노드
(3) 리프 노드 : 자식이 없는 노드, 트리의 끝 지점
ex) 6, 14, 8, 9, 15, 16...
깊이 (depth) : 루트로부터 하위 계층의 특정 노드까지의 깊이
레벨 (level) : 같은 깊이를 가지고 있는 노드들을 묶어서 표현
*형제노드 : 같은 레벨에 있는 노드들
높이 (height) : 리프 노드(0)를 기준으로 루트까지의 높이
서브트리 : 큰 트리 내부에 트리 구조를 갖춘 작은 트리
이진트리 (Binary Tree)
: 자식 노드가 최대 두 개인 노드들로 구성된 트리 (왼쪽 자식 노드 / 오른쪽 자식 노드)
모든 왼쪽 자식의 값 < 루트, 부모
모든 오른쪽 자식 값 > 루트, 부모
* 이진트리 = 자료 삽입, 삭제에 따라 나뉨
정이진트리 (Full binary tree) : 각 노드가 0개 or 2개의 자식 노드를 가짐
완전이진트리 (Complete binary tree) : 마지막 레벨을 제외한 모든 노드가 가득참
마지막 레벨 노드는 전부 차있지 않아도 왼쪽은 채워져 있을것!
포화이진트리 (Perfect binary tree) : 정이진트리 && 완전이진트리
모든 리프 노드 레벨 동일, 모든 레벨이 가득 채워져 있음
