Computer Science/Data Structures (3) 썸네일형 리스트형 이진 탐색 트리 1. 개요 트리(Tree) 는 추상 자료형으로 루트 값과 부모-자식 관계의 서브트리로 구성되어 있는 자기 참조(Self-Referential) 자료구조이다. 그리고 이진트리와 이진 탐색 트리는 트리 중에서도 가장 널리 사용되는 트리 자료구조이지, 트리 자체를 대변하는 것은 아니다. 이진 탐색 트리는 정렬된 트리로 다음의 조건을 만족해야 한다. 노드의 왼쪽 서브 트리에는 현재 노드의 값보다 작은 값을 가진 노드가 온다. 노드의 오른쪽 서브 트리에는 현재 노드의 값보다 큰 값을 가진 노드가 온다. 왼쪽과 오른쪽 서브 트리 모두 이진 탐색 트리여야 한다. 2. 이진 탐색 트리의 특징 이진 탐색 트리는 시간복잡도 측면에서 강점을 가지고 있다. 연산 시간복잡도(평균) 시간복잡도(최악) 삽입 $O(\log n)$ .. 스택과 큐 이미지 출처: twitter - Greg Kyte, CPA 1. 개요 스택과 큐는 데이터 접근 방식을 설명하는 대표적인 자료구조이다. 즉, 자료구조가 코드로 정의된 것이 아니라 행동 양식이 정의되어 어떤 자료구조가 스택 또는 큐로 구분되기 위한 규칙에 해당한다. 이러한 것들을 다른 말로 추상적 자료구조(ADT, Abstract, Data Type)라고 부른다. 데이터를 입력하고 출력하는 그 순서에 따라서 스택과 큐가 구분되고, 이러한 특징을 적재적소에 활용하여 많은 실제 시스템 또는 서비스 등에 적용하고 있다. 이번 글에서는 스택과 큐에 대한 개념과 실제 구현까지 다루어보려고 한다. 2. 스택(Stack) 이미지 출처: Wikipedia - Stack 스택을 설명하는 한 단어를 선택하라고 한다면 바로 L.. 해시테이블 1. 해시 테이블 해시테이블은 해시맵이라고도 불리며, Key와 Value라는 두 가지 값을 함께 맵핑하여 데이터를 저장하는 자료구조이다. 이미 각 언어들은 내부적으로 해시테이블의 기능을 제공하고 있고 대표적으로 Python에는 딕셔너리가, Java에는 Map 컬렉션을 통해서 해당 기능을 제공하고 있다. 해시 테이블은 Key를 임의의 해시 함수에 입력하여 출력된 해시 값을 데이터가 저장되는 배열의 인덱스로 활용한다. 따라서, 특정 value에 접근하려 할 때 key를 통해서 해당 value에 바로 접근하는 것이 가능하기 때문에 $O(1)$의 시간복잡도를 가진다. 보통 배열로 미리 hash table의 크기만큼 공간을 만들어두고 사용하지만, 해시 테이블에서는 충돌이라는 이벤트가 자주 발생한다. 이 충돌을 가.. 이전 1 다음
