데이터 구조

ㅇADT (Abstract Data Type) 추상 자료형 개념적으로 어떤 동작이 있는지만 정의 구현에 대해서는 다루지 않음 vs. ㅇDS (Data Structure) 자료 구조 ADT 에서 정의된 동작을 실제로 구현한 것 개념 스택(stack) LIFO(Las

개념 우선순위 큐(Priority queue) 큐(Queue)와 유사함 우선순위가 높은 아이템이 먼저 처리되는 큐 큐(Queue) 우선순위 힙 & 큐 차이 사례

같은 타입의 데이터들을 저장하는 자료 구조연속된 메모리 공간(1차원)에 데이터들을 저장데이터들 각각은 이름이 없지만 인덱스로 접근 가능대부분의 high level 언어들은 배열에 객체들을 저장할 때는,객체 들은 메모리 상에 듬성 듬성 존재하고,객체의 레퍼런스(메모리 주

값(value)들을 저장하는 추상자료형(ADT)순서가 있음중복을 허용Set이나 Map이 더 적절한 상황이 아니라면,거의 대부분 List를 사용한다고 봐도 된다.객관식 문제의 정답을 List로 관리할 수 있음일반적으로 사용되는 프로그래밍 언어 순위를 순서대로 저장할 수

key-value 쌍(pair)들을 저장하는 ADT같은 key를 가지는 쌍(pair)은 최대 1개만 존재 (반면 value는 중복 가능)associative array 또는 dictionary 라고도 함전화번호에 대응되는 이름 투표 대상별 투표 횟수 카운팅배열과 해시

데이터를 저장하는 추상자료형(ADT)순서를 보장하지 않음데이터 중복을 허용하지 않음데이터 조회(search)가 List보다 빠름중복된 데이터를 제거해야 할 때데이터의 존재 여부를 확인해야 할 때해시 테이블(Hash table) 을 사용한 Set의 구현체그래서 크기 상관

노드(node)들의 집합각 노드는 '값(value)'과 다른 노드들을 가리키는 '레퍼런스'로 구성노드와 노드를 연결하는 선구현 관점에서는 레퍼런스를 의미link / branch 라고도 함트리의 최상단에 있는 노드트리의 시작점모든 노드는 0개 이상의 자녀 노드를 가진다자

개념트리를 순회하는 여러 방식들삽입/삭제/검색 방식모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들만 가진다and 모든 노드의 오른쪽 서브 트리는 해당 노드의 값보다 큰 값들만 가진다이진 탐색 트리 의 특징\-각각의 노드들을 맨 아래의 수평선에 사영시키면,

이진탐색트리(BST)의 한 종류스스로 균형을 잡는 트리balance factor를 통해 균형 유지이진 트리(binary)각 노드의 자녀 노드 수가 최대 2개 (left child/right child) 인 트리이진 탐색 트리 (Binary Search Tree)모든 노

개념속성삽입 시 동작 방식 + 그 이유// BF 개념은 레드블랙트리는 사용하지 않는 개념이다 // 이진탐색트리(BST)의 한 종류스스로 균형 잡는 트리이진탐색트리(BST)의 worst case의 단점을 개선모든 노드는 Red 또는 Black (nil 노드인 경우도 포함

DB 인덱스 구현에 사용되는 B tree 계열의 자료 구조자녀 노드의 최대 개수를 늘리기 위해서 부모 노드에 key를 하나 이상 저장한다부모 노드의 key들을 오름차순으로 정렬한다정렬된 순서에 따라 자녀 노드들의 key 값의 범위가 결정된다위의 방식을 적용하면 자녀 노