움직이는 월e

B-Tree B-Tree는 AVL 트리나 레드 블랙트리와 같이 자가 균형 트리의 종류이다. B-Tree의 사용은 가상 메모리 시스템에서 페이징 기법과 연관이 있는데 페이징이란 디스크 공간을 일정 크기만큼 분할하여 일정 공간 크기를 한 번에 접근할 수 있는 페이지 번호를 매긴다. 디스크에 접근 시 페이지 번호를 참조하여 대략적인 블록 주소를 찾고 정확한 주소는 페이지 번호와 오프셋 정보를 이용하여 접근한다. 페이지의 크기는 8K ~ 16K로 보통 디스크가 한 블록 사이즈로 읽고 쓰므로 디스크 블록 사이즈와 일치한다. B-Tree는 검색 시 페이지 번호를 의미하는 리프 노드까지의 도달 시간을 줄이기 위해 검색 트리의 높이를 낮추는 것에 목적을 둔다. 트리의 높이를 낮추기 위해 B-Tree는 각 노드의 자식 ..

Heap 완전 이진 트리 형태의 자료 구조, 말단 노드 레벨을 제외한 내부 노드들이 꽉찬 트리이다. MinHeap, MaxHeap 부모 노드가 자식 노드보다 항상 작으면 MinHeap, 크다면 MaxHeap 우선순위 큐는 Heap으로 구현되어 있다. Heap을 배열로 구현한다면 parent의 인덱싱을 나누기 방식으로 바로 구할 수 있다. Heapify(node) 연산 node를 루트로 하는 서브 트리가 Heap을 만족할 때까지 트리를 수선하는 것. void Heapify(int root) { int leftId = GetLeft(root); int rightId = GetRight(root); if (leftId >= m_Size && rightId >= m_Size) return; T left = le..

AVL 트리와 마찬가지로 자가 균형 트리의 종류 모든 노드는 레드 혹은 블랙으로 표현되며 이 색깔의 성질에 의해 트리의 균형이 맞춰진다. 균형이 완벽하지는 않지만 여전히 트리의 높이가 O(logN)에 보장되며 이는 탐색, 삽입, 삭제를 O(logN)에 보장하게 된다. 레드 블랙 트리의 성질 모든 노드는 레드 혹은 블랙이다. 루트 노드는 항상 검정이다. 레드 노드의 자식노드는 항상 검정이다. 한 노드에서 리프 노드까지 가는 모든 경로상에 만나는 검정 노드의 수는 모든 경로가 같은 수를 가져야 한다. Null 자식 노드는 검정 노드이다. 레드 블랙트리의 정의에 따라 한 노드에서 자기 자신을 제외한 리프 노드까지 도달하는데 만나는 블랙 노드의 수를 black height라고 하고 bh(v)라고 표현할 수 있다..

AVL (Adelson-Velsky and Landis) Tree 이진 자가 균형 트리 - 균형 트리 이진 탐색 트리의 경우 삽입이나 삭제 이후 서브 트리간 불균형 문제가 발생할 수 있다. 이는 추후 탐색 시간을 저하시키기 때문에 균형을 맞추는 것이 필요하다. - 높이의 정의 한 노드의 높이는 노드를 루트로하는 서브 트리에서 말단 리프노드까지 도달하는 경로 중 가장 긴 경로를 의미한다. 재귀적 표현으로 높이를 구한다면 다음과 같다. height := max(height(left_child), height(right_child)) + 1 위 계산을 편리하게 하기위해 Null 노드의 높이를 -1로 설정한다. height = -1 if (root == NULL) - AVL Tree의 구조 AVL tree는 스..

Binary Search Tree 트리형 데이터 구조는 탐색에 최적화된 자료 구조이다. - 이진 탐색 트리 Binary Search Tree 각 노드는 키 값을 가지며 root와 left, right child 노드를 기준으로 다음을 만족해야 한다. 1. left.key root.key 3. left 서브 트리와 right 서브 트리는 BST를 만족해야 한다. - 이진 탐색 트리의 중위 순회 위 성질을 만족하기 때문에 left -> root -> right의 중위 순회에서 key 값을 순서대로 출력하면 정렬된 값을 얻을 수 있다. - 탐색 시간 높이가 h인 모든 레벨에 노드가 채워진 완전 이진트리의 전체 노드 개수는 $1 + 2 + ... + 2^h$ 이다. 전체 갯수 $2^{h+1} -1 = N$ 이므..