CS STUDY/자료구조 (6) 썸네일형 리스트형 B Tree&B+ Tree 다원 탐색 트리(Multiway Search Tree) 정의 및 특징 트리의 노드가 최대 m-1개의 요소와 m개 이하의 서브 트리를 가질 수 있는 탐색 트리 트리의 높이를 줄이고 싶을 때 사용 각 노드는 최대 m개의 서브트리 m개의 서브 트리를 가지는 노드는 m-1개의 요소를 가진다. 각 노드 안의 요소들은 오름차순으로 정렬 B Tree 정의 M원 검색트리에서 균형 문제도 해결한 자료구조 => 데이터의 삽입, 삭제 시 균형을 맞추는 알고리즘을 수행 최대 M개의 자식을 가질 수 있는 B트리를 M차 B트리라고 부름 규칙 모든 리프 노드들 같은 레벨에 있다. 모든 내부 노드는 최소 ⌈M/2⌉개의 자식을 가진다. 모든 노드들은 최대 M개의 자식을 가질 수 있다. 리프가 아닌 모든 노드들은 최소 2개 이상의 자식.. 트라이(Trie) 트라이(Trie) 개념 문자열의 집합을 표현하는 트리 자료구조 문자열의 검색을 빠르게 해주는 자료구조 사용 목적 두 문자열을 비교하는 경우엔 단순한 비교를 통해 진행하기 때문에 문자열의 길이만큼 시간 소요 => 문자열의 길이 O(M) * 문자열의 총 개수 O(logN) => O(Mlog(N)) 특징 루트에서부터 내려가는 경로에서 만나는 글자들을 모으면 문자열의 접두사를 얻을 수 있다. 리프 노드의 개수는 문자열의 총 개수와 동일하다. 장단점 장점 문자열 추가와 탐색이 모두 O(M)만에 가능 단점 각 노드가 자식에 대한 포인터를 저장하므로 메모리가 많이 필요 사용 예시 검색어 자동완성, 사전에서 단어 찾기, 문자열 검사 참고 https://nooblette.tistory.com/entry/%ED%8A%B8.. 해시 해시(Hash) 개념 및 특징 입력 데이터를 고정된 길이의 데이터로 변환한 값 => 데이터의 key 값을 변환 키(Key)와 데이터(Value)의 매핑 구조 해시 함수(Hash Function)를 통해 키의 데이터를 배열에 저장할 수 있는 주소(인덱스)를 계산 데이터의 탐색 속도가 빨라짐 해시 함수(Hash Function)란? 임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 함수 같은 입력값에 대해서 같은 출력값이 생성된다. 입력값의 범위보다 출력값의 범위가 좁은 경우가 많기 때문에 입력값이 다르더라도 동일한 값이 출력될 가능성이 있다. => 충돌(Collision) 충돌이 발생하는 경우, 배열이 생성되며 선형검색이 이루어진다. 해시 테이블(Hash table)이란? 해시함수를 사용.. 힙&이진탐색트리 트리(Tree) 루프를 갖지 않고 연결된 무방향 그래프 구조 트리내에 또 다른 트리가 있는 재귀적 자료구조 노드 간에 부모 자식 관계를 갖고 있는 계층형 자료구조이며 모든 자식 노드는 하나의 부모 노드만 갖는다. 사용 예: 디렉터리 구조, 조직도 힙(Heap) 개념 및 특징 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 **완전 이진트리란? 단 두개의 자식 노드만 갖는 이진 트리 중 노드가 왼쪽부터 차례로 채워져 있는 트리 A가 B의 부모노드이면, A의 키 값과 B의 키 값 사이에는 대소관계가 성립한다. => 형제 사이에는 대소관계x 부모노드의 키 값이 자식노드의 키 값보다 크거나 같은 완전 이진 트리를 '최대 힙(max heap)', 작거나 같은 완전 이진 트리를 '최소 힙(mi.. 스택과 큐 스택(Stack) LIFO(Last In First Out) 구조 입력과 출력이 한 곳에서만 발생하고, top으로 정한 곳을 통해서만 접근 가능 top을 통해 삽입하는 연산을 'push', 삭제하는 연산을 'pop' 시간복잡도 접근: O(N) => top에서부터 순차적으로 접근 삽입 및 삭제: O(1) => 한 곳(top)에서만 발생 활용 후위 표기법 계산 수식의 괄호 검사 실행 취소(undo) 웹 브라우저 방문기록(뒤로 가기) 큐(Queue) FIFO(First In First Out) 구조 한쪽 끝(rear)에서 삽입이, 다른 쪽 끝(front)에서 삭제가 이루어짐 rear를 통해 삽입하는 연산을 'enqueue', front에서 삭제하는 연산을 'dequeue' 시간복잡도 접근: O(N) => 순차.. 배열과 리스트 배열(Array) 고정된 크기를 갖는 같은 자료형의 원소들이 연속적인 즉, 논리적 저장 순서와 물리적 저장 순서가 일치한 형태로 구성된 자료구조 ⇒ 연속적인 메모리 할당 ⇒ 인덱스 사용 가능 시간복잡도 삭제: 빈자리가 남게되어 메모리가 낭비 ⇒ 마지막 값 삭제할 때만 O(1)이고 그 외에는 O(N) 삽입: 연속적인 형태 유지를 위해 shift 연산이 필요 ⇒ O(N) (맨 뒤에 추가할 것이고 배열에 공간이 남아 있으면 예외적으로 O(1)) 검색, 수정: 인덱스를 통한 검색과 수정이 용이 ⇒ O(1) 리스트(Linked List) 불연속적인 메모리 공간에 저장하므로 크기 제한에서 자유로움 노드 간에 연결을 통해 리스트로 구현된 객체 시간복잡도 삭제: 삭제하려는 데이터의 위치가 맨 앞이면 O(1), 그 외에.. 이전 1 다음
