[section 2] 자료구조(3) - Tree, Graph, BST

Tree

하나 이상의 데이터에 무방향으로 연결된 자료구조, 나무가 뒤집어진 모양이라 트리라 칭함

특징

• 계층적 자료구조
• 비선형 구조
• 단방향 구조
• 사이클이 없음

용어

• 깊이 depth : 루트로부터 해당 노드까지의 깊이
  ❗️root의 깊이 : 0
  

• 레벨 level : 같은 깊이의 노드들
  ❗️같은 레벨노드 ➡️ 형제노드
  

• 높이 height : leaf 노드로부터 해당 노드까지의 높이
  ❗️leaf의 높이: 0
  ❗️부모 노드의 높이: 자식 노드들의 깊이 중 가장 큰 값 + 1
  

• 서브트리 sub tree : 큰 트리 안의 트리구조를 이루는 작은 트리
  ❗️여러 개의 서브트리를 가짐
  

Java Collection - TreeSet, TreeMap

• 값 자동 정렬
• sort() 하지 않아도 자동 정렬

---

Graph

여러 점들의 연결 관계를 표현한 자료구조

특징

• 정점과 간선으로 구성
• 방향이 있음
• 사이클 있음

표현 방식

• 인접행렬 (배열)
  

• 인접 리스트
  

용어

• 정점 vertex
• 간선 edge
• 인접 : 정점이 연결되어 있으면 인접한다고 표현
• 가중치 그래프 / 비가중치 그래프 : 간선에 value가 있는 경우
• 무방향 그래프 / 방향 그래프
• 진입 차수 / 진출 차수 : 들어오고 나가는 간선의 개수
• 자기 루프 : 진출 간선이 바로 자기 자신에게 진입하는 경우
• 사이클

---

BST(Binary Search Tree)

자식노드가 최대 두 개인 트리(이진트리)를 검색이 편리하도록 만든 자료구조

특징

부모의 작은 노드는 왼쪽, 큰 노드는 오른쪽에 위치
➡️ 탐색시,
✔️ 해당 노드의 값이 현재 노드의 값보다 작다면 왼쪽 자식노드 탐색
✔️ 해당 노드의 값이 현재 노드의 값보다 크다면 오른쪽 자식노드 탐색

종류

• 정 이진트리(full binary tree) : 각 노드가 0개 or 2개의 자식 노드를 가지는 경우

• 완전 이진트리(complete binary tree) : 마지막 레벨이 모두 채워지지 않았지만, 왼쪽부터 채워져 있는 경우

• 포화 이진트리(perfect binary tree) : 모든 레벨이 채워져있는 경우