Data Structures10 B-tree B-트리는 이진 탐색 트리를 확장하여 여러 개의 값을 하나의 노드에 연속적으로 저장할 수 있는 자료구조이다. 자가 균형 트리와 유사하게 노드를 분리 및 병합을 통해 균형을 유지하는 구조를 기반으로 한다. 균형을 유지하기 때문에 최악의 경우에도 O(logN)의 시간복잡도를 갖는다. B-트리는 하나의 노드에 여러 개의 값을 배열로 관리하기 때문에 다른 트리에 비해 적은 데이터 참조 횟수로 탐색 연산이 가능하다. 대량의 데이터는 메모리에 적재해서 사용할 수가 없기 때문에 데이터베이스와 같은 영역에서는 하드 디스크 같은 보조기억장치의 데이터를 필요시에 읽어서 사용하는데, 하나의 값이라도 블록단위로 읽어오기 때문에 이진트리 형태의 자료구조는 매우 비효율적이다. 2021. 8. 23. 레드-블랙 트리( Red-black tree ) 레드-블랙 트리( 이하 RBT )는 특수한 형태의 이진 탐색 트리로, 삽입 및 삭제 시 균형을 유지하는 '자가 균형 이진 탐색 트리' 이다. 일반적인 이진 탐색 트리는 최악의 경우에 O(N)의 시간 복잡도를 갖지만, 균형을 유지하는 RBT는 최악의 경우에도 O(logN)의 시간 복잡도를 갖는다. 1. 특징 - RBT의 노드는 기존과 조금 다른데, 부모에 대한 참조와 노드의 색깔에 대한 변수가 추가된다. 그리고 리프 노드는 값을 가지지 않는 NULL 노드로서 사용된다. - RBT의 연산은 기본적으로 이진 탐색 트리의 것을 사용하되, 균형을 유지하기 위한 로테이션과 색 변경 등의 연산이 추가된다. 2. 필요조건 - 모든 노드는 레드 또는 블랙이다. - 루트 노드는 블랙이다. - nil(null) 노드는 블랙.. 2021. 8. 10. 힙 트리( Heap tree ) 힙 트리는 완전 이진 트리 구조를 가지며 최소 또는 최대 값을 상수시간에 탐색 가능한 자료 구조로 배열로 구현이 쉽다. 1. 특징 - 완전 이진 트리 형태이다. - 모든 노드는 부모노드의 값보다 크거나 작다. ( = 서브트리도 힙 트리의 특징을 갖는다 ) - 루트 노드에 항상 최소 또는 최대 값이 위치한다. 2. 종류 - 최소 힙( Minimum heap ) - 최대 힙( Maximum heap ) 3. 구현 2021. 7. 29. 이진 탐색 트리( Binary search tree ) 1. 속성 - 중복되지 않는 값을 가진 이진 트리 구조 - 노드의 왼쪽 서브트리에는 노드보다 작은 값을 가진 노드의 집합이다. - 노드의 오른쪽 서브트리에는 노드보다 큰 값을 가진 노드의 집합이다. - 각 서브트리는 위와 같은 속성을 갖는다. - 탐색 및 삽입,삭제 시에 트리가 균형을 이룰 때 O(logN)의 시간복잡도를 갖는다. ( 단, '높이 = 노드 수'일 경우 O(N) ) 2. 구현 2021. 7. 27. 이전 1 2 3 다음
