본문 바로가기

Programing General/자료구조2

이진 탐색 트리( map, set )와 우선순위 큐 ( Heap ) 이진 탐색 트리 이진 트리의 일종 자신보다 작은 값을 왼쪽 노드에 위치시키고, 자신보다 큰 값을 오른쪽 노드에 위치시킴 C++ 컨테이너인 map, set Java의 TreeSet, TreeMap은 이진 탐색 트리로 이루어져 있다. Map, Set 중복을 허용하지 않는 자료구조 대부분의 언어에서 Red-Black Tree를 사용함 (이진 탐색 트리의 한 종류) 특정한 기준에 의해서 정렬되어있음(JAVA의 경우 TreeMap, TreeSet만 정렬되어있고 HashMap, HashSet은 정렬 X) 자료구조 key value Map 중복될 수 없음 중복 가능 Set 중복될 수 없음 X(존재하지 않음) Heap 우선순위 큐를 위한 자료구조 heap은 우선순위 큐를 구현하기 위한 자료구조로서, 완전 이진트리 이다.. 2020. 1. 6.
[Container Adapter] stack과 queue의 메모리 할당 방식 stack과 queue는 자료구조를 처음 공부할 때 배우는 기초적인 선형 자료구조의 하나이다. 우리가 자료구조를 처음 공부할 때 배운 선형 자료구조의 종류는 다음과 같다. list vector deque queue stack 하지만 여기서 더 엄격한 기준으로 나눠보자면 list, vector, deque queue, statck 이렇게 두 분류로 다시 나눌 수 있다. list, vector, deque는 데이터를 어떻게 물리적으로 저장하는지에 대한 명세가 있는 자료구조이고, queue, stack은 데이터를 어떻게 사용하는지에 대한 명세가 있는 자료구조이다. 즉, 예를들어 stack은 선입후출의 방법으로 사용될 수 있게 설계된다면, deque으로 구현하던, vector로 구현하던, list로 구현하던 아.. 2019. 12. 26.

티스토리툴바