목록자료구조 (22)

오늘도 더 나은 코드를 작성하였습니까?

B Tree 정의와 데이터 삽입

* 나무위키의 내용 및 * 아래 링크의 유튜브 영상을 보고 본 글은 제 학습의 결과를 정리한 내용입니다. https://youtu.be/bqkcoSm_rCs?si=TVQzH3urhF3rorru 정의 B 트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. 방대한 양의 저장된 자료를 검색해야 하는 경우 검색어와 자료를 일일이 비교하는 방식은 비효율적이다. B-트리는 자료를 정렬된 상태로 보관하고, 삽입 및 삭제를 O(logn) 지수시간으로 할 수 있다 특징 자식 노드의 개수를 늘려 저장하기 위해서 최소 1개 이상의 key는 부모노드에 존재한다. 부모노드의 key는 오름..
자료구조 2023. 10. 2. 22:14
펜윅트리 (Binary Index Tree) feat. kotlin

Fenwick 트리 또는 BIT(Binary Indexed Tree)는 요소를 "효율적으로 update"하고, 숫자 테이블에서 "prefix sum"을 계산할 수 있는 데이터 구조입니다. 구조는 1989년에 Boris Ryabko가 제안했으며, 1992년에 추가 수정본이 발표되었습니다. 이후 그의 1994년 기사에서 이 구조를 설명한 Peter Fenwick의 이름을 따서 Fenwick 트리라는 이름으로 알려지게 되었습니다. *이진법 비트연산 성질을 이용한다. 컴퓨터에서 정수를 저장하기위 사용되는 타입은 Int입니다. int 자료형은 4byte(32bit)이다. 정수 15는 00000000 00000000 00000000 00001111 정수 -15는 *2의 보수( ~15 + 1) 11111111 111..
자료구조 2023. 7. 3. 17:04
세그먼트 트리(Segment Tree) feat. kotlin

CS에서 statistic tree라고도 하는 세그먼트 트리는 간격 또는 세그먼트에 대한 정보를 저장하는 데 사용되는 트리 데이터 구조입니다. 주어진 포인트를 포함하는 저장된 세그먼트에 대해서 쿼리할 수 있습니다. n개의 원소에 대하여 구성된 세그먼트 트리는트리를 생성하는 비용은 O(n)이다. 원소를 update 하는데 O(log n)의 시간 복잡도가 필요하고, 쿼리 또한 O(log n)의 시간 복잡도가 요구된다. 1. 초기화 1차원 배열을 통해 구현한다. * 0번째 idx는 사용하지 않는다. 원본 배열의 Size의 2배 크기의 배열을 Tree로 사용한다. * 크기를 2배로 잡는 이유는 원본 배열로 세그먼트 트리의 리프 노드를 구성하게 되면, 세그먼트 트리가 2진트리이기 때문에 (리프 노드 개수/ 2)면..
자료구조 2023. 7. 2. 17:50
Kotlin Priority Queue(우선순위 큐)

우선순위 큐는 정해진 우선순위가 가장 높은 데이터를 먼저 삭제하는 자료구조이다. 구현 단순 array / list 하여 구현 - 삽입 O(1) - 삭제 O(N) 힙을 사용하여 구현 - 삽입 O(logN) - 삭제 O(logN) * 모든 데이터를 힙으로 구현된 우선순위 큐에 담았다가 꺼내면 정렬된다(힙 정렬 - O(NlogN)) 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다. A가 B의 부모노드(parent node) 이면, A의 키값과 B의 키값 사이에는 대소관계가 성립한다. * 완전 이진 트리 - 높이가 h..
자료구조 2023. 6. 27. 16:48
이전 Prev 1 2 3 4 5 6 Next 다음