[자료 구조] 비선형 구조

비선형 구조

자료의 삽입,삭제에 중점인 선형구조와 다르게, 자료의 표현에 중점을 맞춘 것
하나의 자료 뒤에 여러개의 자료가 존재하는 형태

트리

Node와 Branch를 이용해 사이클로 이루어지지 않도록 구성된 그래프

Node(노드) : 트리의 기본 요소, data와 다른 Branch 정보를 합친 것
Branch(가지) : 노드와 노드를 연결하는 간선
Degree(차수) : 각 노드에서 뻗어나온 가지의 수
Level(레벨) : Root Node의 레벨이 1로 가정하면 자식 Node로 갈 수록 +1이 된다.

트리의 특징

• 방향성 존재
• Node는 어떤 자료형으로도 표현 가능
• 사이클 존재 불가
• Node가 N개인 트리는 항상 N-1개의 Branch를 가짐

이진 트리

각 Node가 최대 두 개의 자식 Node를 갖는 트리
모든 Node가 왼쪽 자식 Node <= n <= 오른쪽 자식 Node 라는 특정 순서를 모두 따르는 이진 트리

완전 이진트리

마지막 Level을 제외하고 모든 Level이 완전히 채워져 있는 트리

균형 이진트리

모든 Node가 0개 또는 2개 자식 Node 갖는 트리

포화 이진트리

균형이진 트리이면서 완전 이진트리
모든 단말 Node는 같은 Level, 모든 내부 Node는 두 개의 자식 Node

균형 트리 (B-Tree)

레드블랙트리, AVL트리가 일종, 시간복잡도 O(logN)에 삽입, 찾기 등이 가능한 균형 잡힌 트리

그래프

Node와 Node를 연결하는 Edge(간선)를 하나로 모아 놓은 자료구조
연결되어 있는 객체 간의 관계를 표현할 수 있음

Node(정점) : 데이터의 위치를 나타내는 개념
Edge(간선) : Node를 연결하는 선
인접 정점 : Edge에 의해 직접 연결된 정점
Degree(차수) : 무방향 그래프에서 하나의 Node에 인접한 Node의 수
- in-Degree(진입 차수) : 방향 그래프에서 외부에서 오는 Edge 수
- out-Degree(진출 차수) : 방향 그래프에서 외부로 향하는 Edge 수

그래프의 특징

• 네트워크 모델
• 2개 이상의 경로가 가능
• 부모 - 자식 관계 개념이 없음
• 방향 그래프 / 무방향 그래프 구분 됨

가중치 그래프

Edge에 비용이나 가중치가 할당된 그래프

무방향 그래프

Edge를 통해 양방향으로 갈 수 있음
Node A와 Node B를 연결하는 Edge는 (A,B) 또는 (B,A) 와 같이 Node의 쌍으로 표현

방향 그래프

Edge에 방향성이 존재하는 그래프

비연결 그래프

무방향 그래프에서 특정 Node 쌍 사이에 경로가 존재하지 않는 그래프

연결 그래프

무방향 그래프에 있는 모든 Node쌍에 대해서 항상 경로가 존재하는 경우

트리가 해당 됨

비순환 그래프

사이클이 없는 그래프

순환 그래프

단순 경로의 시작 Node와 종료 Node가 동일한 그래프

완전 그래프

그래프에 속해 있는 모든 Node가 서로 연결 되어 있는 그래프

무방향 완전 그래프의 Node 수 n일 때 Edge 수 n*(n-1)/2