정보처리기사 필수 학습: 자료 구조- 비선형구조 완전 정복!

 

비선형구조

TREE

• 노드와 간선으로 이루어진 자료구조
• 계층적으로 시킬떄 사용
• 데이터간 부모-자식 관계

 

분류	설명
노드(Node)	- 트리의 기본 구성 요소
근노드(Root node)	- 가장 상위에 있는 노드 (이미지에선1)
레벨	- 근노드를 기준으로 특정 노드 까지 길이 - 1 인 근노드에서 15는 레벨 3
조상노드(Ancestors Node)	- 특정노드에서 경로상 노드 -6기준으로 조상노드는 2와 1
자식 노드(child node)	- 특정 노드 다음의 노드 - 2기준 4랑6
부모 노드(parent node)	- 특정노드 이전의 노드 - 6기준 2
형제노드(Sibing)	- 같은 부모를 가진 노드 -2의 형제는 3 , 4의 형제는 6
깊이(Depth)	- 가장 깊은 레벨의 수 - 위에 트리는 레벨이4 까지니 4
차수(Degree )	- 특정 노드에 연결된 자식의수  - 6의 차수는 2명 - 이 트리의 차수는 (가장 많은) 2명
트리의 차수	- 트리의 최대 차수 2명
단말노드 (Rerminal node , Leaf Node)	- 트리의 맨마지막 노드 10, 7

 

 

트리의 순회방법

• 전위 순회(Pre-Order) : 먼저 부모를 방문 C->L->R

 

 

• 중위 순회(in-Order) : 중간으로 지나감 L->c->R

• 후위 순회(Post-Order) :  부모를 마지막으로 방문함 L->R->C

 

 

트리의 종류

• 이진 트리(Binary Tree)
• - 최대 두개의 자식을 가진 노드로 구성된 트리
• - 깊이가 H인 이진트리의 최대 노드수는 2의 h승 - 1
• - 특정 레벨 L에서 최대 노드수 2에 L -1 승

 

 

- 깊이가 H인 이진트리의 최대 노드수는 2의 h승 - 1

-> 사진의 H는 4개 따라서 2에 4승 -1  = 2x2x2x2 -1 = 15

-특정 레벨 L에서 최대 노드수 2에 L -1 승

->3레벨일 경우 L=3 따라서 2에 2승 = 4 = 그림과 동일

 

 

• 완전 이진 트리(Complete Binary Tree)

• - 마지막 레벨을 제외하고 모든 레벨이 채워진트리
• - 마지막 레벨에서는 노드가 왼쪽부터 차례대로 채워져야한다.

 

• 포화 이진 트리(Full Binary Tree)

• - 모든 레벨에서 노드가 완전히 채워진 트리
• - 깊이가 H인 포~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 

 

 

 

종합.

 

 

 

• 편향 이진트리(Skewed Binary Tree)

모든 노드가 한쪽 방향의 자식노드만을 가진 트리

삽입/삭제 연산 효율이 낮다.

노드가 N개인 평향 이진 트리높이는 최악의경우 0(n) 이 될수있다.

 

• 균형 이진트리(Balanced Binary Tree)

모든 노드에서 왼쪽과 오른쪽 서브 트리의 높이 차이가 1이하인 트리

삽입/삭제 연산 효율이 좋다

 

• 이진 탐색트리(Binary Search Tree)

노드를 정렬된 순서로 유지하는 이진트리각 노드의 왼쪽 서브트리에는 해당 노드값보다 작은값을 오른쪽은 큰값을 위치

 

 

• AVL Tree

자동으로 균형을 유지하는 이진탐색 트리

 

• B-Tree

데이터 베이스와 파일 시스템에 적합한 트리

• 신장트리

원래 그래프에서 모든 노드들을 포함해 사이클 없는 부분 그래프

 

그래프

• 그래프는 V와 E로 이루어진 자료구조이다.
• v = Vertex = 정점 : 노드들의 집합
• E =Edge:상허 연결의 집합

① 무방향 그래프

• 간선을 표현하는 두정점 사이의 순서가 없는 그래프
• n개의 정점으로 구성된 무방향 그래프 최대 간선수는 n(n-1)/2개

② 방향 그래프

• 간선을 표현하는 두정점 사이의 순서가 있는 그래프
• n개의 정점으로 구성된 무방향 그래프 최대 간선수는 n(n-1)개