[자료구조] 노드..? 그래프..? 트리..? 난모르겠어!

노드.. 그래프.. 트리..? 모르시겠다구요? 제가 쉽게 알려드릴게요

노드란 아래 그림과 같이, 현재 정보와, 다음 정보의 경로를 담고있는 자료구조를 뜻한다.

Java에서 List의 자료구조가 바로 노드를 이용한 연결이다.

List.add를 하게되면, 새로운 노드가 생성되고 마지막 노드의 경로가 새로운 노드를 가리킨다.
그럼 List.remove를 하게되면, 노드가 삭제되고 경로가 바뀌겠죠?

장점이 뭐길래?

기존의 배열구조는 연속적인 메모리를 갖고있어야 할당할 수있다.

그러나 Node로 연결된 자료구조의 경우 그럴필요가 없다!

그럼 단점은?

배열에서는 중간값을 인덱스를 통해 바로 알 수 있다

그러나 Node로 연결된 자료구조의 경우 O(N)만큼 시간이 소요된다. (오버헤드 발생)

노드 어디다 써요?

이러한 노드를 갖고 여러가지 자료구조를 만들 수 있는데

대표적인 자료구조는 스택,큐,트리,그래프가 존재한다

스택

스택의 경우 FILO의 특성을 갖고있는 자료구조이다.

First in Last Out.. 무슨 의미 이겠는가? 처음 들어온 자료는 마지막에 나간다는 소리이다.

그림을 통해 확인하자

꺼낼때는 Top에서 하나씩 꺼낸다.

큐

큐의 경우 FIFO의 특성을 갖고있는 자료구조이다.

First in First Out 스택이 저렇다면 큐는 어떻겠는가?

그림을 통해 확인하자

꺼낼때는 front에서 하나씩 꺼낸다.

트리

사실 위의 두개는 굉장히 쉬운 자료구조이다.

이제 본격적으로 어려운 자료구조에 입문했다.

트리란 무엇인가?
나무?

이건 그림을 먼저보자.

조금 나무처럼 생겼는가?

그렇다! 노드로 이루어진,사이클이 없는 무방향 그래프는 트리이다!

여기서 무방향이란, A에서 C를 갈수도, C에서 A를 갈수도있는 양방향으로 이동할 수 있는 걸 의미한다.

사이클은..? 말그대로 서로 다른 두 노드 사이에 정확히 하나의 경로만 존재하는 것을 의미한다.

그래프는 뭔데!?

굉장히 쉽다. 이따 살펴보자

정리하자면. 트리는 서로 다른 두 노드 사이에 정확히 하나의 경로만 존재하는 그래프이다.

아무튼 위의 그림의 경우, 한개의 노드에 최대 두개의 노드만 연결되어있지 않은가?

• 그림은 이진트리이다.

그 밖에도 AVL 균형트리,레드-블랙 트리,B-트리/B+ 트리,세그먼트 트리,트라이..등 다양하게 존재한다.

어려우니 나중에 다루겠다.

그래프

굉장히 쉽다.

여러 노드들이 서로 연결되어 있는 구조를 그래프라고한다.

어? 트리는 그래프인가요?

네 맞습니다

그래프는 트리인가요?

그건 아닙니다

그래프가, 트리를 포함한다.

이러한 그래프도 다양한 형태를 띌 수 있는데, 그림을 보자

기초인 만큼, 어려우면 굉장히 어렵다.

1+1=2 증명이 어려운것처럼..