비선형 자료구조 (그래프, 트리, 힙, 맵, 셋, 해시 테이블)

비선형 자료구조

• 비선형 자료구조란 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 것이다.
• 자료들 간의 앞뒤 관계가 1:n, 또는 n:n 의 관계
• 트리와 그래프가 대표적이며 계층적 구조를 나타내기에 적절하다.

 

그래프(Graph)

정점과 간선으로 이루어진 자료구조입니다.

 

*정점과 간선
어떠한 곳에서 어떠한 곳으로 무언가를 통해 간다한다했을때 어떠한 곳은 정점(vertex)이 되고 무언가는 간선(edge)이 됩니다.

 

 

 

 

방향 그래프
: 두 정점을 연결하는 간선에 방향이 존재하는 그래프

 

방향그래프

 

 

무방향 그래프
: 두 정점을 연결 하는 간선에 방향이 존재하지 않는 그래프

 

무방향 그래프

 

 

가중치 그래프 
: 두 정점을 이동할때 비용이 드는 그래프
 * 가중치란? : 간선과 정점 사이에 드는 비용을 뜻함

 

가중치 그래프

 

트리(Tree)

그래프 중 하나로 그래프의 특징 처럼 정점과 간선으로 이루어져있고 트리 구조로 배열된 일종의 계층적 데이터의 집합입니다. 참고로 트리로 이루어진 집합을 숲 이라고 합니다.

 

 

트리는 루트노드, 내부노드, 리프노드로 이루어져있습니다

 

- 루트노드
  : 가장 위에 있는 노드를 뜻합니다. 보통 트리 문제가 나오고 트리를 탐색할때 루트노드를 중심으로 탐색하면 문제가 쉽게 풀리는 경우가 있습니다.

- 내부노드
  : 루트노드와 내부노드 사이에있는 노드를 뜻합니다.

- 리프노드 
  : 자식 노드가 없는 것을 뜻합니다.

 

 

트리의 높이와 레벨

 

다음은 트리와 높이와 레벨을 설명한 그림입니다.

 

- 깊이
  : 트리에서의 깊이는 각 노드마다 다르며, 루트 노드로부터 특정 노드까지 최단 거리로 갔을때의 거리를 말합니다. 예를 들어 4번 노드의 깊이는 2입니다.

- 높이
  : 트리의 높이는 루트 노드르부터 리프노드까지 거리 중 가장 긴 거리를 의미하며, 앞 그림의 트리의 높이는 3 입니다.

- 레벨
  : 트리의 레벨은 주어지는 문제마다 조금씩 다르지만 보통 깊이와 같은 의미를 지닙니다. 1번 노드를 0레벨 이라고 하고 , 2번노드, 3번 노드까지의 레벨을 1레벨이라고 할 수 있고, 1번 노드를 1레벨이라고 한다면 2번 노드와 3번 노드는 2레벨이 됩니다.

- 서브트리 
  : 트리 내의 하위 집합을 서브트리라고 합니다. 트래 내에 있는 부분 집합이라고도 보면 됩니다. 지금 보면 5,6,7번 노드가 이 트리의 하위 집합으로 서브트리라고 합니다.

// 노드 생성
function createNode(content, children = []) {
  return {
    content,
    children,
  };
}

// 트리를 생성
const tree = createNode("hello", [
  createNode("world"),
  createNode("and"),
  createNode("fun", [createNode("javascript")]),
]);

// 트리를 순회하는 함수

function traverse(node) {
  console.log(node.content); // 현재 노드의 콘텐츠 출력
  for (let child of node.children) {
    traverse(child); // 각 자식에 대해 재귀적으로 traverse함수 호출
  }
}

// 트리 순회 시작
traverse(tree);

// hello
// world
// and
// fun
// javascript

 

 

 

힙 (Heap)

완전이진트리(링크)의 일종

최대값과 최소값을 빠르게 찾기 위한 자료구조

- 최대힙(max heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 (부모노드 : 최대값) 

- 최소힙(min heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 (부모노드 : 최소값) 

최대값 or 최소값 검색시 : O(1)

삽입, 삭제시 : O(logn) 

 

 

맵 (Map)

: 특정 순서에 따라 키(Key)와 매핑된 값(Value)의 조합으로 형성된 자료 구조
- 리스트나 배열처럼 순차적으로 해당 요소 값을 구하지 않고, Key 를 통해 Value를 얻을 수 있음

- Key는 중복될 수 없으며, Value는 중복 값을 허용함

- 자바에서 Map은 인터페이스로, 인터페이스를 구현 Map자료형에는 HashMap, LinkedHashMap, TreeMap 등이 있음

 

 

집합 (Set)

: 집합과 관련된 것을 쉽게 처리하기 위해 만들어진 자료형

- 데이터의 중복을 허용하지 않으며, 순서가 없음 (인덱싱을 통해 값을 얻을 수 없음)
- 자바에서는 HashSet, TreeSet, LinkedHashSet 등이 존재

 

 

 

해시 테이블(HashTable)

: Key와 Value를 1:1로 연관지어 저장하는 자료구조 (연관 배열 구조)

- 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색속도를 가짐

- 특정한 값을 탐색하는데 고유 index(key)로 접근하기 때문에 시간복잡도는 O(1)을 가짐

 

 

 

 

참고

https://erinh.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Java-%EB%B9%84%EC%84%A0%ED%98%95-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%E2%91%A3-%EB%A7%B5-Map-%EC%A7%91%ED%95%A9-Set

[자료구조 Java] 비선형 자료구조 ④ 맵 (Map), 집합 (Set), 해시테이블