이진 탐색 트리빠른 검색을 위해 사용하는 비선형 자료구조(트리 형태이므로)논리적으로 데이터가 정렬되어 있고 정렬된 상태를 유지하면서 데이터의 삽입/삭제를 O(logN)에 할 수 있다.아래 그림과 같이 왼쪽: 현재 노드 데이터보다 작은 값을 가지는 노드오른쪽: 현재 노드 데이터보다 큰 값을 가지는 노드 시간복잡도데이터 삽입/삭제O(logN)X라는 데이터 접근O(logN)X보다 Ceiling/Floor에 접근O(logN) 사용사례Java TreeMap, TreeSet내부적으로 이진 탐색 트리 중 하나인 Red-Black Tree 구조를 사용해서 데이터를 저장 및 관리한다. Java HashMap Chaining같은 key값에 여러 개의 value값을 가지는 경우 8개 이상을 가지는 데이터에서는 BST 형태로..
Data Structure
야구를 보러가거나 놀이기구를 기다릴때, 기다린 순서대로 먼저 탄다. 큐를 줄을 서는 것으로 생각하면 된다. 큐데이터가 논리적(물리적 x)로 저장되어 있는 자료구조chunk라는 단위로 내부적으로 저장FIFO(First In First Out)자료구조이다. 연산Enqueue: 큐에 데이터를 넣는다.Dequeue: 큐에 데이터를 꺼낸다. 시간복잡도i번째 데이터 접근O(N)x라는 데이터 탐색O(N)맨 앞 데이터 접근(peek)O(1)데이터 추가(Enqueue)O(1)데이터 추가(Dequeue)O(1) 사례CPU 스케쥴링운영체제에서 여러 프로세스가 CPU를 할당받으려고 할때, 큐에 추가된다. 네트워크 패킷라우터에서 데이터 패킷이 들어오는 순서대로 큐에 저장되고, 들어온 순서에 맞춰서 전송한다. 배치 처리(Ba..
롤 유저들은 나서스라는 챔프에 대해 알 것이다. 나서스는 q스킬이 스택을 쌓고 있다고 흔히들 표현하는데, 그 스택이라고 생각하면 기억하기 용이할 것이라고 생각한다.(데미지에 대한 데이터를 쌓는다) 스택데이터가 논리적(물리적 x)으로 저장되어 있는 자료구조LIFO(Last In First Out) 마지막에 들어온 데이터가 첫번째로 나가는 자료구조 두가지 연산push : 데이터를 넣는 연산pop : 데이터를 꺼내는 연산 시간복잡도맨위에 있는 데이터를 접근(peek)O(1)i번째 데이터 접근O(N)x라는 데이터가 있는지 탐색O(N)push 연산O(1)pop 연산O(1) ErrorStack 메모리를 초과Stack Overflow ErrorStack 데이터가 없을 때, pop을 수행할 경우, Empty Stac..
