22.05.16 개발 일기

오늘의 계획

• 제로베이스 자료구조(Tree) 챕터 다 듣기 => (90%완료)
• LeetCode 두 문제 풀기 => 완료

트리 (Tree)

• 그래프의 일종으로 두 노드 사이의 하나의 간선만 연결되어 있는, 최소 연결과 계층 형태의 비선형 자료 구조
• 트리 특징
  • 주요 특징: '최소 연결 트리'로 불림, 계층 모델, 방향 비순환 그래프(DAG: Directed Acyclic Graph)한 종류
  • 트리 종류 : 이진트리, 이진 탐색 트리, AVL 트리, 힙(Heap)
• 트리 순회 ( 총 4가지 )
  • 트리 구조에서 각각의 노드를 정확히 한 번씩 체계적인 방법으로 방문하는 과정
  • 필요 용어
    -->N(node) : 해당 노드를 방문
    -->L(Left) : 왼쪽 서브 트리로 이동
    -->R(Right) : 오른쪽 서브 트리로 이동
  • 순회 방식
    -->전위 순회(Pre-order): N - L - R
    -->중위 순회(In-order):L - N - R
    -->후위 순회(Post-order): L - R - N
    -->층별 순회(Level-order): 낮은 Level부터 순차적으로 순회 bfs챕터중 하나

이진트리 (Binary Tree)

• 각각의 노드가 최대 두개의 자식 노드를 가지는 트리 자료 구조
• 활용 방식
  • 검색 과 정렬 : 이진 탐색 트리와 이진 힙 구현에 활용
  • 허프만 코딩 : 연관 분기 구조 위한 데이터 표현에 활요 (데이터 압축, 데이터 표현)
• 이진 트리 종류
  • 포화 이진 트리(Perfect binary tree)
    -> 모든 레벨의 노드가 가득 채워져 있는 트리
• 특징 :
  -> Leaf 노드를 제외한 모든 자식은 2개의 노드를 보유
  -> 노드의 개수: n = 2^n - 1
  • 완전 이진 트리(Complete binary tree)
    • 마지막 레벨 전까지 노드가 가득 채워져 있고, 마지막 레벨은 왼쪽부터 순차적으로 채워져 있는 트리
    • 특징
      -> 배열을 사용해 효율적인 표현이 가능
      -> 노드의 개수: n < 2^n -1
  • 정 이진 트리(Full binary tree)
    • 모든 노드가 0개 또는 2개의 자식 노드만 갖는 트리
    • 특징 :
      -> proper 또는 plane 이진 트리라고도 불림
      -> 노드의 개수 n <= 2^n - 1
  • 편향 이진 트리(Skewed binary tree)
    • 왼쪽 혹은 오른쪽으로 편향되게 치우쳐 있는 트리
    • 특징
      -> 각각의 높이에 하나의 노드만 존재
      -> 노드의 개수 : h(높이)
  • 균형 이진 트리(Balanced binary tree)
    • 삽입/삭제가 이루워 질때 , 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차를 1이하로 맞추는 이진 탐색 트리
    • 특징
      -> 서브 트리 높이 차이가 항상 1이하로 유지
      -> 균형 트리 종류 : AVL트리, Red-Black 트리, B트리, B+ 트리, B*트리

오늘의 LeetCode 문제가 트리와 DFS 카테고리가 있어서 Tree 부분 강의를 듣기로 계획하였다.
강의를 90%정도 수강하고 LeetCode 문제를 풀기 시작하였는데, 원하는 구조는 만들수 있었지만 아직 이해도가 부족해서 응용이 되지 않고 오랜 시간동안 문제를 풀지 못해서 두 문제 모두 정답 코드를 보고 문제를 풀었는데, 재귀 함수에 대해서 조금 더 가까워지는 코드였다.

그래도 요즘은 코드를 보면 구조에 대해서 아직 어렵지만 예전보다는 이해가 되고 조금씩 나아가고 있다고 느끼고 있는 하루였다..[]~(￣▽￣)~*