[STUDY] 자료구조(Data Structure) - 비선형 자료구조(Non-Linear Data Structure)

1. 자료구조

https://woder.tistory.com/24

[STUDY] 자료구조(Data Structure) - 선형 자료구조(Linear Data Structure)

 

2. 비선형 자료구조(Non-Linear Data Structure)

 

1) 트리(Tree)

· 데이터(Data, 노드(node)) 간 부모-자식 관계의 계층적 자료구조 (디렉토리, 가계도 등)

트리(Tree)

· A 와 B 는 부모-자식 관계 (parent-child)

· B 와 C 는 형제-자매 관계 (sibiling)

· 크기 (size) : 자신(self)을 포함한 자식 노드 전체 개수 

  ※ B 의 크기는, 3 (B, D, E)

· 깊이, 높이 : 루트 노드( A )에서 부터 자신(self)까지 도달하기 위해 거치는 간선의 개수 

  ※ D 의 크기는, 2

  ※ 최대 깊이, 높이는 트리에서 가장 큰 깊이, 높이 값

· 차수 (degree) : 자식 노드의 개수 

  ※ B 의 차수는, 2 ( D, E )

  ※ 최대 차수는 트리에서 가장 큰 차수 값

 

① 이진 트리 (Binary Tree)

· 자식 노드(차수)의 최대 값이 2 인 트리 

· 자식 노드(차수)의 최대 값이 3 이상 인 경우 삼항 트리(Ternary Tree)

 

a. 이진 검색 트리 (Binary Search Tree)

이진 검색 트리 (Binary Search Tree)

· 이진 검색 트리는 부모 노드를 기준으로, 자식 노드의 왼쪽은 오른쪽 보다 작은 값으로 배치된 트리 

· 일반적으로 이진 트리는 노드 간 대소 관계를 생각하지 않음 

 

b. 완전 이진 트리 (Complete Binary Tree)

 

이진 트리	완전 이진 트리

· 완전 이진 트리는 단말 노드가 왼쪽부터 배치되는 트리 

· 단말 노드를 제외한 모든 서브 트리(sub-tree) 레벨이 같아야 함 

 

c. 전 이진 트리 (Full Binary Tree)

 

완전 이진 트리	전 이진 트리

· 전 이진 트리는 자식 노드가 없거나 꽉 찬(2개) 트리

 

d. 포화 이진 트리 (Perfect Binary Tree)

 

전 이진 트리	포화 이진 트리

· 포화 이진 트리는 모든 노드의 자식 노드가 꽉 찬(2개) 완전한 피라미드 형태 트리 

 

2 ) 그래프 (Graph)

· 노드(node, vertice)와 노드 간 연결하는 간선(arcs)으로 관계를 나타내는 자료구조

· 트리는 위 (root node)에서 아래 (reaf, terminal node) 방향으로 흐르는 방향 그래프의 일종

 

무방향 그래프 (Undirected Graph)	방향 그래프 (Directed Graph)
· 노드(정점)와 노드(정점) 간 연결된 간선에 방향이 없음  · 그래프 흐름이 양방향으로, (A, B) 로 표시	· 노드(정점)와 노드(정점) 간 연결된 간선에 방향이 있음 · 그래프 흐름 방향이 A → B, <A, B> 로 표시

 

· 그래프는 간선이 없는 경우도 있고, 부모 자식관계는 존재하지 않음 

· 인접정점 (adjacent vertex) : 간선에 연결된 노드(정점)

· 차수 (degree) : 무방향 그래프에서 한 노드(정점)에 인접한 정점 개수 

· 진출차수 (out-degree) : 방향 그래프에서 자신(self)에서 외부로 향하는 간선의 수 

  ※ A 의 진출차수, 2 (A→B, A→D)

· 진입차수 (in-degree) : 방향 그래프에서 외부에서 자신(self)으로 들어오는 간선의 수 

  ※ A 의 진입차수, 1 (C→A)

 

순환 / 비순환 그래프 (Cyclic / A cyclic Graph)

 

비순환 그래프 (A cyclic graph)	순환 그래프(Cyclic graph)