programming/algorithm_datastructure

B+트리, B트리 비교

B+트리란?B트리에서 확장된 개념으로, 리프 노드에만 실제 데이터를 담는다B+트리는 리프 노드에만 데이터를 저장하고, 내부 노드에는 데이터가 아닌 키만을 저장한다 키는 데이터를 찾기 위한 인덱스 역할을 하며, 실제 데이터는 리프 노드에서만 접근 가능이로 인해 모든 데이터 접근이 리프 노드에서 이루어지며, 데이터가 정렬된 형태로 연결되어 있다B+트리는 리프 노드를 순차적으로 연결하는 포인터 집합을 가지고 있다.인덱스된 순차 파일 처리시,포인터를 이용하여, `키 : 값`을 일일이 비교하지 않고 다음 데이터에 접근해서 빠르게 처리할 수 있다.(이부분 무슨 말인지 이해가 안된다, 다시 알아보자)   데이터 삽입처음 1,2가 노드에 들어있을때3을 추가하면 노드의 최대 키을 초과하여( 3차이기 때문에 키는 2개가 ..

이진트리, 이진탐색트리

이진 트리 (Binary Tree): 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조단순히 각 노드가 자식노드를 2개 이하로 가질 수 있다는 조건만 만족하면 그것은 이진트리라 할 수 있다이진 탐색 트리 (Binary Search Tree, BST):이진 탐색 트리는 이진 트리의 한 종류이지만, 추가적인 정렬 조건을 만족해야 한다각 노드의 왼쪽 자식에는 해당 노드보다 작은 값이, 오른쪽 자식에는 더 큰 값이 위치해야 한다이런 조건을 만족함으로써 탐색 속도를 빠르게 할 수 있습니다. 왼쪽으로 가면 항상 더 작은 값을 찾고, 오른쪽으로 가면 더 큰 값을 찾을 수 있어 탐색 과정이 효율적입니다.

B-tree

binary search tree 에서 파생된것으로BST에서 자식노드의 갯수에 제한을 없앤것이 b-tree이다자식노드의 갯수가 3개 이상이려면부모노드의 key도 하나 이상이어야한다부모노드의 key들을 오름차순으로 정렬한다정렬된 순서에 따라 자녀 노드들의 key값의 범위가 결정된다 [20 40] / | \ [10 15] [30 35] [50 60 70] / | / | | \ [5 7] [12] [25] [32] [45] [55 65 75]자식노드의 갯수에 따라 n차 b-tree로 불리는데위의 예시는 자식노드가 3개이므로 3차 B-tree이다key에 의해서 자식노드들..

[hackerrank] sorting 문제

문제 해석: 한 array arr이 주어지면 arr[0]을 제외한 요소중에 2개 골라서 더하고 아무데나 놓기 그렇게 해서 오름차순이 되는 가장 최소의 반복횟수를 구하는 문제 [2,4,1,3,5]라는 배열이 주어졌을때 1,3을 고르고 그걸 더해서 arr[2]에 놓음 그럼 [2,4,4,5]로 정렬된 배열이 나옴 그럼 리턴은 1, 한번만에 정렬된 배열을 얻었기 떄문에