자료구조 : Tree / Graph

◎ Tree

• Tree

  • 그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태
  • 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조

• Tree의 노드와 노드사이 관계

  • 루트(Root) : 트리에 있는 단 하나의 꼭짓점 데이터
  • 간선(edge) : 데이터를 연결하는 것
  • 노드(Node) : 각 데이터를 일컫음
  • 부모 노드(Parent Node), 자식 노드(Child Node)
    : 위 그림에서 5 - 3 관계를 보자
    • 5 는 3 의 부모 노드(Parent Node) 이다.
    • 3 은 5 의 자식 노드(Child Node) 이다.
  • 리프 노드(Leaf Node) : 자식 노드가 없는 노드

• Tree의 용어

  • 깊이(depth) : 루트로부터 하위 계층의 특정 노드까지의 깊이(depth)
  • 레벨(Level) : 같은 깊이를 가지고 있는 노드를 묶어서 레벨(level)로 표현
  • 높이(Height) : 리프 노드를 기준(0)으로 루트까지의 높이(height), 자식 노드가 여러개일 경우, 숫자가 큰것을 기준
    ex) 10 : 높이 2
  • 서브 트리(Sub tree)
    • 트리 구조의 root에서 뻗어 나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리

• 적합한 상황 (실사용 예제)

  • 폴더 구조
    • C드라이브 부터 시작해서 폴더는 계속 하위 폴더를 가질 수 있다.
  • 월드컵 토너먼트 대진표, 가계도(족보), 조직도 등.

• Tree 구조 간략적인 구현

public class App { 
  private String value;
  private ArrayList<App> children;
  
  // Method ...
}

◎ Graph

• Graph(그래프)

  • 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조
    ex) 거미줄처럼 여러 개의 점들이 선으로 이어져 있는 복잡한 네트워크망

• 그래프 구조 및 용어

  • 정점 (vertex): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소
  • 간선 (edge): 정점 간의 관계를 나타냄 (정점을 이어주는 선)
  • 인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점
  • 가중치 그래프 (weighted Graph): 연결의 강도(추가적인 정보)가 얼마나 되는지 적혀져 있는 그래프
  • 비가중치 그래프 (unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프 (0, 1로만 구성)
  • 무(방)향 그래프 (undirected graph): 앞서 보았던 내비게이션 예제는 무(방)향 그래프입니다. 서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는 것도 가능합니다. 하지만 단방향(directed) 그래프로 구현된다면 서울에서 부산을 갈 수 있지만, 부산에서 서울로 가는 것은 불가능합니다(혹은 그 반대). 만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현할 수 있습니다.
  • 진입차수 (in-degree) / 진출차수 (out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냅니다.
  • 인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점이다.
  • 자기 루프 (self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현, 다른 정점을 거치지 않는다는 것이 특징
  • 사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현

• 인접 행렬
  

  • 두 정점을 바로 이어주는 간선이 있다면 이 두 정점은 인접하다고 한다
  • 두 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시한 일종의 표
  • 만약 가중치 그래프라면 1 대신 관계에서 의미 있는 값을 저장
  • 인접 행렬을 사용하는 상황
    • 두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이
    • 가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용

• 인접 리스트
  

  • 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현
  • 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있다.
  • 각 리스트마다의 순서는 보통 중요하지 않다. 정점별로 살펴봐야 할 우선 순위를 고려해 구현 (예외는 존재 가능)
  • 인접 리스트를 사용하는 상황
    • 메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용
      (접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지)

• Graph의 실사용 예제

  • SNS에서 사람들과의 관계, 내비게이션 (길 찾기) 등에서 사용

◎ Binary Search Tree

• 트리 구조 탐색

  • 수많은 선배 개발자님들은 효율적인 탐색을 위해 고민하고 발전했다.
  • 트리 구조는 가지고 있는 특징에 따라 여러 가지 이름으로 부른다.
  • 많은 트리의 모습 중, 가장 간단하고 많이 사용하는 것은 이진 트리(binary tree)와 이진 탐색 트리(binary search tree)가 있다.

• Binary Tree (이진 트리)

  • 자식 노드가 최대 두 개인 노드들로 구성된 트리
  • 두 개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나눈다.
  • 자료의 삽입, 삭제 방법에 따라 종류가 나뉜다.

• Binary Tree의 종류

  • Full binary tree(정 이진 트리) : 각 노드가 0개 혹은 2개의 자식 노드를 가짐
  • Complete binary tree(완전 이진 트리) : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 왼쪽 노드다 채워져야 한다.
  • Prefect binary tree(포화 이진 트리) : Full binary tree, Complete binary tree를 둘다 만족하는 경우
    • 리프 노드의 모든 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리이다.

• 이진 탐색 트리(Binary Search Tree)

  • 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가짐
  • 균형 잡힌 트리가 아닐 때, 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리게 될 수 있다.
  • 삽입과 삭제마다 트리의 구조를 재조정하는 과정을 거치는 알고리즘을 추가할 수 있다.