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

수경·2022년 11월 22일
1

코드스테이츠

목록 보기
27/57

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) : 모든 레벨이 채워져있는 경우

profile
어쩌다보니 tmi뿐인 블로그😎

0개의 댓글