TIL-20221118

khundi·2022년 11월 18일

트리(Tree)

트리는 그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있어 트리 구조라고 부른다.

트리구조의 실사용 예

파일탐색기

이진 트리(Binary tree)

이진 트리는 자식노드가 최대 두 개인 노드들로 구성된 트리를 말한다.
자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진트리(Perfect binary tree)로 나뉜다.

이진 트리 특징

정 이진 트리: 각 노드가 0개 혹은 2개의 자식 노드를 갖습니다.
완전 이진 트리: 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 합니다.
포화 이진 트리: 정 이진 트리이면서 완전 이진 트리인 경우입니다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리입니다.

트리 순회

특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회라고 한다. 모든 노드를 순회하는 방법엔 크게 세 가지가 있다.

전위 순회 (preorder traverse)

전위 순회는 루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 뒤, 왼쪽 노드 탐색이 끝나면 오른쪽 노드를 탐색한다.
중위 순회 (inorder traverse)

중위 순회는 루트를 가운데에 두고 순회한다. 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 시준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 모두 탐색한다. 중위 순회는 이진 탐색 트리의 오름차순으로 값을 가져올 때 쓰인다.
후위 순회 (postorder traverse)

후위순회는 루트를 가장 마지막에 순회한다. 후위 순회는 트리를 삭제할 때 사용한다. 자식 노드가 먼저 삭제되어야 상위 노드를 삭제할 수 있기 때문.

그래프(Graph)

그래프는 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조이다.

그래프의 구조

두 점 사이를 이어주는 선이 있다면 직접적인 관계이다.
몇 개의 점과 선에 걸쳐 이어지면 간접적인 관계이다.
하나의 점을 그래프에서는 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge)이라고 한다.

그래프의 표현 방식

인접 행렬

인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타낸다.
A라는 정점과 B라는 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시한 일종의 표이다.

A = 0, B = 1, C = 2

A의 진출차수는 1개 입니다: A —> C
[0][2] === 1

B의 진출차수는 2개 입니다: B —> A, B —> C
[1][0] === 1
[1][2] === 1

C의 진출차수는 1개입니다: C —> A
[2][0] === 1