[자료구조/알고리즘] Tree와 Graph

omegle·2022년 11월 18일
0

Tree 개념과 특징


트리는 그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져 있고, 트리 구조로 배열된 일종의 계층적 데이터의 집합이다. 루트 노드, 내부 노드, 리프 노드 등으로 구성되며, 트리로 이루어진 집합을 숲이라고 한다.

  • 트리는 그래프의 일종이며 부모, 자식 계층 구조를 갖는다. 같은 경로상에서 어떤 노드보다 위에 있으면 부모, 아래에 있으면 자식 노드가 된다.
  • 임의의 두 노드 사이의 경로는 '유일무이'하게 '존재'한다. 즉, 트리 내의 어떤 노드와 어떤 노드까지의 경로는 반드시 있다.
  • V-1=E 라는 특징이 있다. (노드 수 -1 = 간선 수)

비선형 자료 구조

  • 비선형 자료 구조란 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말한다.
  • 일반적으로 트리나 그래프를 말한다.

정점과 간선

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

그래프와 트리

  • 자료구조중 그래프와 트리는 둘 다 데이터(노드)간의 관계를 간선으로 정리하는 형태의 자료구조이다.
  • 그래프는 정점과 간선으로 이루어진 자료 구조를 말한다.
  • 그래프는 네트워크 형태로, 서로가 연결되어 순환이 가능한 형태의 자료구조를 나타내며, 계층적 형태가 아닌 서로가 수평적 관계를 갖기 때문에 루트노드라고 불리는 최상위 노드라는 존재가 없다.
  • 트리는 노드간 계층적 형태의 관계를 갖는다.

트리의 구성

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

  • 루트노드 : 가장 위에 있는 노드이다. 보통 트리 문제가 나오고 트리를 탐색할 때 루트 노드를 중심으로 탐색하며 문제가 쉽게 풀리는 경우가 많다.
  • 내부 노드: 루트 노드와 내부 노드 사이에 있는 노드를 뜻한다.
  • 리프 노드: 리프 노드는 자식 노드가 없는 노드를 뜻한다.

📌 용어 살펴보기

Node (노드) : 트리를 구성하고 있는 각각의 요소
Edge (간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선
Root Node (루트 노드) : 트리 구조에서 최상위에 있는 노드
Terminal Node ( = leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드
Internal Node (내부노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함
level: 루트로부터 몇 번째 깊이인지
degree = 차수: 한 정점에서 뻗어나가는 간선 수
height: 트리의 최고 레벨

이진 힙(Binary Heap) 개념

이진 힙은 힙 중에서 가장 널리 쓰이는 형태 중 하나로 이진 트리 형태인 힙이다. 여기서 이진 트리는 각 노드의 자식 노드가 반드시 2개 이하인 트리를 말한다. 이진 힙은 완전 이진 트리라는 조건을 만족해야 한다.

힙(Heap)

힙이란 최댓값이나 최솟값을 찾아내는 연산을 빠르게 하기위해 고안된 완전이진트리를 기본으로한 자료구조이다.

  • 힙은 완전 이진 트리 기반의 자료 구조이며, 최소힙과 최대힙 두 가지가 있고 해당 힙에 따라 특정한 특징을 지킨 트리를 말한다.

  • 최대힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야한다. 또한, 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다.

  • 최소힙 : 최소힙에서 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 한다.
    또한, 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다.

완전 이진 트리

완전 이진 트리(complete binary tree) : 왼쪽에서부터 채워져 있는 이진트리를 의미한다. 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 경우 왼쪽부터 채워져 있다.


Graph 개념

그래프는 비선형적 자료구조로, 정점(vertex, node)과 간선(edge)으로 이루어진 자료구조를 말한다.

그래프(Graph) 특징

  • 그래프는 네트워크 모델이다
  • 2개 이상의 경로가 가능하다. 즉, 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.
  • 부모-자식 관계 개념이 없다.

Graph 예시

  • 포털 사이트의 검색 엔진, SNS에서 사람들과의 관계, 네비게이션에서 사용된다. 세 가지 모두 수많은 정점을 가지고 있고, 관계가 있는 정점은 간선으로 이어진다.

✍️ 간선: 연결된 두 개의 정점에서 데이터가 이동할 수 있음을 나타내고, 데이터가 서로 이동할 수 없는 경우 관계가 없다고 표현된다.

📌 용어 살펴보기

Node (노드) : 트리를 구성하고 있는 각각의 요소
Edge (간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선
인접 정점(adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점

그래프와 트리의 차이점?

  • 그래프는 정점과 간선으로 이루어진 자료구조를 말한다.
  • 트리는 그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져 있고 트리 구조로 배열된 일종의 계층적 데이터의 집합이다. 루트 노드, 내부 노드, 리프 노드 등으로 구성되며 V-1=E 등의 특징이 있다.
profile
JANG EUN JI | 장은지

0개의 댓글