Graph

zx

상하위개념이 없는 노드와 노드 간의 연결하는 간선으로 구성된 자료구조
= 객체간의 관계를 표현할 수 있는 자료구조
ex) 지하철노선도, 지도어플의 최단경로, 팔로워 등

  • 버텍스 : 노드, 정점

  • 아크: 엣지, 노드와 노드의 연결
    => 버텍스 간에 여러개의 아크 존재가능

  • Cycle 가능 : 단순경로의 시작정점과 종료정점 동일
    • Self-loop(자체간선) 가능
    • Cyclic (순환그래프)
    • Acyclic (비순환그래프)
  • 방향성
    • Directed(방향그래프) : 간선을 통해 양방향 갈 수 있음
    • Undirected(무방향그래프) ex) 일방통행
  • 루트 노드의 개념이 없음 / 부모-자식 관계라는 개념이 없음
  • 그래프는 네트워크 모델

그래프 구현

1) Adjacency Matrix (인접행렬) : 배열로 구현
ff

2) Adjacency List (인접리스트, 일반적) : 리스트로 구현
sdfg

Tree

제목 없음

그림출처 : https://chercher.tech/kotlin/tree-kotlin

트리는 그래프 중에서 특수한 케이스 - 여러 데이터가 계층구조

  • 두개의 노드 사이에 반드시 1개의 경로만 가짐 (최소 연결 트리라고도 불림)
  • 비순환 + 방향 그래프
  • 부모-자식 관계가 존재해 레벨이 존재 (최상위 노드 = Root)
  • 노드가 N개이면 간선은 N-1개 / 각 레벨 k에 존재하는 노드는 2^k개
  • 트리의 순회 존재
    • 전위순회 : 부모 -> 좌 -> 우
    • 중위순회 : 좌 -> 부모 -> 우
    • 후위순회 : 좌 -> 우 -> 부모

용어

  • root node : 뿌리노드, 트리의 가장 상층

  • leaf node : 잎노드, 자식노드가 없는 모든 노드

  • parent node

  • childe node

  • ancestor node : A가 B의 조상노드 = 노드A의 자식을 따라 내려갔을 때, 노드 B에 도달할 수 있음
  • descendant node : B가 A의 자손노드
  • sibling node : 형제노드, 같은 부모노드 가짐

BST (Binary Search Tree, 이진탐색트리)

기초적인 트리구조 최대 2개의 자식노드만 가짐
댓글, 카테고리 구분 등에서 사용
aa

  • 노드의 왼쪽 서브트리에는 노드의 값보다 작은값
  • 오른쪽 서브트리에는 노드의 값과 같거나 큰 값 들어가게 됨

업데이트:

참고