1. Tree

데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조이다.

하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조이다.

트리구조는 계층적으로 표현되고, 아래로만 뻗어나가기 때문에 사이클이 없다는 특징이 있다.

깊이(depth)
트리 구조에서 루트로부터 하위 계층의 특정 노드까지의 깊이를 표현할 수 있다. 루트 노드는 깊이가 0이고 루트의 자식노드부터는 1씩 깊이가 증가한다.

레벨(Level)
트리 구조에서 같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현할 수 있다. 깊이가 0인 루트의 레벨은 1이고 깊이가 1인 노드들은 레벨이 2다. 같은 레벨에 나란히 있는 노드를 형제 노드(Sibiling Node)라고 한다.

높이(Height)
트리 구조에서 리프 노드를 기준으로 루트까지의 높이를 표현할 수 있다.

서브 트리(Sub tree)
트리 구조의 root에서 뻗어나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리를 서브 트리라고 부른다.

용어

• 노드(Node) : 트리 구조를 이루는 모든 개별 데이터
• 루트(Root) : 트리 구조의 시작점이 되는 노드
• 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
• 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
• 리프(Leaf) : 트리 구조의 끝 지점이고, 자식 노드가 없는 노드

2. Graph

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

그래프의 구조로는

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

인접행렬

두 정점을 이어주는 간선이 있다면 이 두 정점은 인접하다고 말한다. 인접 행렬은 서로 다른 장점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타낸다.

• 2차원 배열 matrix 사용

• matrix[v][w] = 1 : 정점 v에서 정점 w로 가는 간선이 있음

• matrix[v][w] = 0 : 정점 v에서 정점 w로 가는 간선이 없음

• 예시) 정점 5는 정점 2와 정점 4와 연결되어 있다. 위의 행렬이 matrix라고 하면 matrix[5][2] = 1, matrix[5][4] = 1 이고 나머지는 0이다.

• 장점
  - 연결된 정점 찾기가 빠르다.
  - 구현이 쉽다.

• 단점
  - O(n^2)의 공간복잡도를 가진다.
  

인접 리스트
인접 리스트는 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현한다. 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정저믕ㄹ 담고 있다.

• 배열 또는 리스트를 사용

• 정점의 개수만큼 헤드 노드가 있고, 각 정점에 인접한 정점들을 리스트로 연결한다.

• 정점 v의 인접 정점이 w와 z라면 헤드 노드 v에 w와 z가 연결 리스트로 연결되어있다.

• 예시) 정점 5는 정점 2와 정점 4로 연결되어 있다. 5번 인덱스에 2와 4가 리스트로 연결되어 있다.

• 장점
  - 필요한 만큼 공간을 사용하기 때문에 공간 낭비가 적다.

• 단점
  - 인접 행렬보다 구현이 어렵다.

3. Binary Tree

우선 이진 트리(binary tree)는 자식 노드가 최대 두 개인 노드들로 구성된 트리이다. 왼쪽 자식 노드와 오른쪽 자식 노드로 자식 노드를 나눌 수 있다.

이진 트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)로 나뉜다.

정 이진 트리
각 노드가 0개 혹은 2개의 자식 노드를 갖는 트리이다.

포화 이진 트리
정 이진 트리이면서 완전 이진 트리인 경우이다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리이다.

완전 이진 트리
마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다.