[CS스터디]220705 자료구조 - 2

Stack, Queue에 대해서 설명해주세요.

Stack

• LIFO(Last In First Out, 후입선출)
• push(), pop()
• 활용 예시
  • 웹 브라우저 방문 기록
  • 역순 문자열 만들기
  • 실행 취소
  • 후위 표기법
  • 수식의 괄호 검사 등

 

Queue

• FIFO(First In First Out, 선입선출)
• offer(), poll()
• 활용 예시
  • 우선순위가 같은 작업 예약(프린터의 인쇄 대기열)
  • 은행 업무
  • 콜센터 고객 대기시간
  • 프로세스 관리 등

 

 

 

Heap, Priority Queue에 대해서 설명해주세요.

Heap

• 완전 이진 트리(Complete Binary Tree)로 구성된 자료구조
• 모든 노드에 저장된 값들은 자식 노드들의 것보다 크거나 같다.
• 부모는 자식보다 항상 우선순위가 높다
• 그렇기 때문에 루트 노드가 항상 우선 순위가 가장 높은 노드임

 

Priority Queue

• Heap을 이용해서 우선 순위 큐를 구현함 !

 

 

 

Tree, Binary Tree, BST, AVL Tree에 대해서 설명해주세요.

Tree

• 나무(tree)를 뒤집어 놓은 것 같다고 해서 이름이 붙여진 자료 구조
• 노드와 엣지로 구성되어 있음

 

Binary Tree

• 이진 트리
• 자식 노드가 최대 두 개인 노드들로 구성된 트리

 

BST(Binary Search Tree)

• 이원 탐색 트리
• 이진 트리의 구조를 가지고 있으며, 임의의 키를 가진 원소를 삽입, 삭제, 검색하는데 효율적인 자료 구조
• 특징
  • 모든 원소는 상이한 키를 갖는다.
  • 왼쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다 작다.
  • 오른쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다 크다.
  • 왼쪽 서브트리와 오른쪽 서브트리도 모두 이원 탐색 트리이다.

 

AVL Tree

• 이진 탐색 트리는 데이터 삽입 순서에 따라서 한쪽으로 노드가 쏠릴 수가 있다. 그렇게 되면 데이터를 검색하는데에 O(N)의 시간 복잡도가 요구되어 성능이 매우 나빠지게 된다.
• AVL Tree는 BST의 이런 단점을 보완하고자 만들어졌다.
• 특징
  • 이진 탐색 트리의 속성을 가진다.
  • 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다.
  • 높이 차이가 1보다 커지면 회전(Rotation)을 통해 균형을 맞춰 높이 차이를 줄인다.
  • 삽입, 검색, 삭제의 시간 복잡도가 O(log N)이다. (N : 노드의 개수)