자료 구조

Tree

Tree의 정의

• 그래프의 여러 구조 중 단방향 그래프의 한 구조
• 데이터가 바로 아래에 하나 이상의 데이터에 무방향으로 연결된 계층적 자료 구조
  • 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조
• 계층적으로 표현이 되고, 아래로만 뻗어나가므로 사이클이 없다!
• 실사용 예시 : 디렉토리 구조

Tree의 구조 및 특징

• 루트(root)라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결한다
  • 각 데이터를 노드(Node)라고 한다
  • 두 노드가 상하 계층으로 연결되면 부모 / 자식 관계를 가진다
  • 자식이 없는 노드를 리프 노드(Leaf Node)라고 한다

• 깊이(depth)
  • 루트로부터 하위 계층의 특정 노드까지의 깊이(depth)
  • 루트 노드의 깊이는 0
  • 아래로 내려갈수록 깊이는 1씩 증가한다

• 레벨(Level)
  • 같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현한다
  • depth가 0인 루트의 레벨은 1
  • 아래로 내려갈수록 레벨은 1씩 증가한다
  • 형제 노드(Sibling Node) : 같은 레벨에 나란히 있는 노드

• 높이(Height)
  • 리프 노드를 기준으로 루트까지의 높이
  • 리프 노드와 직간접적으로 연결된 노드의 높이를 표현하며, 부모 노드는 자식 노드의 가장 높은 높이값에 1을 더한 값을 높이로 가진다

• 서브 트리(Sub Tree)
  • 루트에서부터 뻗어 나오는 큰 트리의 내부에 트리 구조를 갖춘 작은 트리

용어 정리

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

---

Graph

Graph의 정의

• 여러 개의 점들이 선으로 이어져 있는 복잡한 네트워크망과 같은 모습을 가진다
• 실생활 예제 : 포털 사이트의 검색 엔진, SNS에서 사람들과의 관계, 네비게이션 등

Graph의 구조

• 직접적인 관계 : 두 점 사이를 이어주는 선이 존재
• 간접적인 관계 : 몇 개의 점 및 선에 걸쳐 이어진다
  • 정점(vertex) : 그래프에서 하나의 점
  • 간선(edge) : 그래프에서 하나의 선

Graph의 표현 방식

• 두 정점을 바로 이어주는 간선이 있다면 두 정점을 인접하다고 한다

인접 행렬

• 서로 다른 정점들이 인접한 상태인지 표현한 2차원 배열 형태의 행렬
  • 만약 두 정점이 이어져 있다면 1, 이어져 있지 않다면 0으로 표시한 표
  • 가중치 그래프라면 1이라는 값 대신에 관계에서 의미 있는 값으로 저장
    • 가중치 그래프 : 간선에 연결 정도를 표현한 그래프

• 인접 행렬은 언제 사용하나?
  • 인접 행렬은 두 정점 사이에 관계가 있는지 확인하기에 용이하다
  • 가장 빠른 경로(Shortest Path)를 찾고자 할 때 주로 사용된다

인접 리스트

• 각 정점이 어떤 정점과 인접하는지 리스트의 형태로 표현한다
  • 각 정점마다 하나의 리스트를 가지고 있고, 이 리스트에 자신과 인접한 다른 정점들을 담는다
• 그래프를 인접 리스트로 구현할 때에는, 정점 별로 살펴봐야 할 우선 순위를 고려해 구현할 수 있다
  • 리스트에 담겨진 정점들을 우선 순위 별로 정렬할 수 있다
  • 우선 순위가 없다면 연결된 정점들을 단순하게 나열한 리스트가 된다

• 인접 리스트는 언제 사용하나?
  • 메모리를 효율적으로 사용하고 싶을 때 사용한다
    • 인접 행렬은 연결 가능한 모든 경우의 수를 저장하므로 상대적으로 메모리를 많이 차지한다

용어 정리

• 정점(vertex)
  • 데이터가 저장되는 그래프의 기본 원소
  • 노드(node)라고도 한다
• 간선(edge)
  • 정점 간의 관계를 나타낸다(정점 사이를 이어주는 선)
• 인접 정점(adjacent vertex)
  • 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점
• 가중치 그래프(Weighted Graph)
  • 연결의 강도가 얼마나 되는지 적혀있는 그래프
• 비가중치 그래프(Unweighted Graph)
  • 연결의 강도가 적혀있지 않은 그래프
• 무(방)향 그래프(Undirected Graph)
  • 방향이 없는 그래프
  • 간선으로 이어져있는 두 정점은 서로 진출 및 진입이 가능하다
• 단방향 그래프(Directed Graph)
  • 방향이 있는 그래프
  • 간선에 방향이 존재하여 해당 방향으로만 이동이 가능하다
• 진입차수(in-degree) / 진출차수(out-degree)
  • 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타낸다
• 인접(adjacency)
  • 두 정점 간에 간선이 직접 이어져있다면 두 정점은 인접한 정점이다
• 자기 루프(self loop)
  • 한 정점에서 진출하는 간선이 바로 자신에게 진입하는 경우
    • 다른 정점을 거치지 않는다!
• 사이클(cycle)
  • 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 존재한다

---

이진 탐색 트리(Binary Search Tree)

• 이진 트리(Binary Tree)
  • 자식 노드가 최대 두 개인 노드들로 구성된 트리
  • 두 개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있다
  • 자료의 삽입 / 삭제 방법에 따라 정 이진 트리(Full Binary Tree), 완전 이진 트리(Complete Binary Tree), 포화 이진 트리(Perfect Binary Tree)로 나뉜다

이진 트리 종류	영어 표기	설명
정 이진 트리	Full binary tree	각 노드가 0개 혹은 2개의 자식 노드를 갖는다
완전 이진 트리	Complete binary tree	마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다
포화 이진 트리	Perfect binary tree	정 이진 트리이면서 완전 이진 트리인 경우를 말한다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리이다

• 이진 탐색 트리(Binary Search Tree)
  • 모든 왼쪽 자식의 값이 루트나 부모보다 작은 값을 가진다
  • 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가진다
    
  • 균형 잡힌 트리가 아닐 때, 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰릴 수 있다
    • 한쪽으로 노드가 몰린다면 트리를 탐색하는 데에 시간이 오래 걸릴 수 있다
      • 이러한 문제를 해결하기 위해 삽입 / 삭제마다 트리의 구조를 재조정하는 과정을 거치는 알고리즘을 추가할 수 있다
      • Ex. AVL 트리