빽 투더 기본기 [알고&자구 2편]. 자료구조 기초

기초 자료구조에 대해서 정리해 놓는다.
그닥 내용은 없지만, 그냥 한번 훑어보는 정도.

자료구조 개요

출처 : https://m.post.naver.com/viewer/postView.nhn?volumeNo=16398872&memberNo=15488377

어떤 자료구조를 안다함은, 다음을 안다는 것이다.

• 정의
• 특징 / 특이사항
• 접근 시간
• 사용 상황 구분

위 자료구조들은 기초적인 것으로, 굳이 여기에 다 적진 않는다.

 

트리

좀 더 자세히 알아보고 싶은 것은 비선형구조의 트리다.
선형 구조와 다르게, 비선형 구조는 구조 특성상 여러 형태로 응용되기 때문에, 좀 더 알 필요가 있다.

 

정의

트리의 정의는 다음과 같다고 한다.

1. 트리는 하나의 루트 노드를 갖는다.
2. 루트 노드는 0개 이상의 자식 노드를 갖고 있다.
3. 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.
4. 트리는 DAG(Directed Acyclic Graphs, 방향성이 있는 비순환 그래프)의 한 종류이다.

출처 : https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html

뭐.. 별 내용 없다. 마지막 4번. 트리와 그래프의 차이는, 트리는 방향 그래프의 일종이고 싸이클이 없다는 것이다.
일반적으로, 그래프는 네트워크모델, 트리는 계층모델이다.

 

종류

트리의 종류는 기준이 뭐냐에 따라 겁나 다양한데… 뭐 각 기준별로 하나씩 살펴보면

• 그냥 트리 vs 이진 트리

  • 이진 탐색 트리

  • Full, Complete, Perfect (완전 이진, 전 이진, 포화 이진)

    • Full : 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리.
    • Complete : 트리의 모든 높이에서 노드가 꽉 차 있는 이진 트리. 마지막 레벨은 꽉 차 있지 않아도 되자만 노드가 왼쪽에서 오른쪽으로 채워져야 한다.
    • Perfect : Full + Complete 상태인 트리.
  • 
    

     

출처 : https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html

• 균형 트리 vs 비균형 트리

  • 레드 블랙 트리
  • AVL 트리

• 힙

  • 최소 힙, 최대 힙

• 트라이

  • 접두사를 빠르게 찾아보기 위해 사용되는 트리구조

와 정말 기초다.

 

참고했거나 참고하면 좋은 링크

Heejeong Kwon님 블로그. 트리란
aria-grande님 블로그. 기술 면접에서 주눅들지 않으려면