[Alex] 데이터 장인의 블로그

이진탐색트리 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 이진트리. 이진 탐색 트리는 기존 이진트리보다 탐색이 빠르다. 이진 탐색 트리의 탐색 연산은 트리의 높이(height)가 h라면 O(h)의 시간 복잡도를 갖는다. 트리 구조에 따라서 logN ~ N까지의 시간복잡도를 가질 수 있다. (편향된 이진 탐색트리인 경우, N(높이)만큼의 시간복잡도를 가짐.) 해당 경우를 방지하기 위해 자가 균형트리가 존재. 자가 균형트리 트리가 한쪽으로 편향되지 않도록 삽입, 삭제를 개선한 이진 탐색트리. AVL 트리와 Red black 트리가 존재. 해시 해시에 매핑하여 데이터를 저장하는 방법. '데이터를 저장하는 위치 = 인덱스'를 간단한 연산으로 구하는 것. 원소의 검색뿐만 아니라, 추가&삭제도 효율적으로..

힙(Heap) '완전' 이진트리를 기초로 하는 자료구조. 마지막을 제외한 모든 노드에서 자식들이 꽉 채워진 이진트리. 최대값 혹은 최소값을 빠르게 찾기 위한 이진트리 우선 순위 큐를 위하여 만들어진 자료구조 (우선순위 큐: 우선순위의 개념을 큐에 도입한 자료 구조) 우선순위 큐는 배열, 연결리스트, 힙 으로 구현이 가능하다. 이 중에서 힙(heap)으로 구현하는 것이 가장 효율적이다. 시간복잡도 삽입 : logN 삭제 : logN 최대 힙(max heap) 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 key(부모 노드) >= key(자식 노드) 최소 힙(min heap) 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 key(부모 노드)

스택과 큐는 추상적 자료구조(ADT)이다. - 구조의 행동양식만 정해져 있는 것. 데이터 구조 중에서 가장 기초, 기본이 되는 개념. 스택과 큐는 '배열'의 형태로 쉽게 표현 가능하다. 스택(Stack) 배열이 수직으로 표현되어 있는 형식. 후입선출(LIFO)의 방식. 큐(Queue) 새로운 요소가 뒤에 추가되고, 가장 처음 요소가 삭제(사용)되는 자료형식. 선입선출(FIFO)의 방법. 가장 처음 입력된 데이터를 가장 처음 '사용'하는 자료구조. 인큐, 디큐 우선순위 큐 링 버퍼 / 우선순위 큐 링 버퍼의 활용. 환형 큐(Circular Queue) 우선순위 큐(Priority Queue) 링 버퍼는 오래된 데이터를 버리는 용도로 활용 가능. 원소 수가 n개인 배열에 데이터를 계속해서 입력. 가장 최근에..