개인기록부 개인기록부

개요 리프 노드의 수는 BST와 B-Tree를 구별하는 주요 차이점 중 하나로 BST는 두 개로 고정이되는 반면, B-Tree는 차 수에 따라 말단 노드의 개 수가 결정된다. 만약 데이터를 삽입하는 과정을 갖는다면 항상 리프 노드에서 발생하게 되는데 이는 삭제하는 과정 역시 동일하지만 삽입을 통해 자녀 노드의 수가 기준 값 보다 커졌을 경우 승진을 통한 재조정이 발생하지만 삭제의 경우 key의 개수가 최소 key의 수보다 적어졌다면 재조정이 이루어지게된다. B-Tree에 저장되는 데이터가 있다면 이 데이터 각각은 Key를 통해 동작하지만 여기선 데이터가 Key의 역할까지 수행하기 때문에 두 단어를 혼용해서 사용한다. 데이터 삭제 과정 다음과 같은 3차 B-Tree가 존재한다고 했을때, 데이터 삭제 과정에..

이진 탐색 트리 BST 이진 탐색 트리가 가지는 특징 모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들만 가지고, 모든 노드의 오른쪽 서브 트리는 해당 노드의 값보다 큰 값들만 가질 수 있고 자녀 노드는 최대 두 개까지 가질 수 있다. 트리 형태의 자료 구조의 특성상 깊이가 깊어질수록 소모되는 자원이 커질 수 밖에 없기 때문에 최대한 작은 depth를 통해 많은 자녀 노드를 확보할 필요가 있다. 이 생각을 바탕으로 기존 BST를 확장해 값의 범위를 세분화하게 되면 아래와 같이 범위를 갖는 트리 구조를 얻게 된다. 이 방식을 적용하면 이진 탐색 트리와 동일한 방식으로 동작 하면서도 하나의 노드가 자녀 노드의 개 수를 두 개 이상도 가질 수 있도록 만들 수 있는것이다. 범위를 갖게된 노드를 서브 ..