(2,4) 트리에서 레드-블랙 트리로레드-블랙 트리 :노드가 빨간색 또는 검은색으로 색칠된 이진 트리를 통해 (2,4) 트리를 표현(2,4) 트리와 비교 :동일한 로그 시간 성능단순한 구현: 레드-블랙 트리는 단일 노드 타입을 사용하여 더 간단하게 구현 가능레드-블랙 트리 정의루트 속성(Root Property): 루트는 검은색외부 속성(External Property): 모든 잎(리프)은 검은색내부 속성(Internal Property): 빨간색 노드의 자식은 모두 검은색깊이 속성(Depth Property): 리프 노드의 black depth는 모두 같다레드-블랙 트리의 높이정리: n개의 항목을 저장하는 레드-블랙 트리는 높이는 O(log n)증명:레드-블랙 트리의 높이는 (2,4) 트리의 높이의 최..

multi-way search treebinarySearch Tree의 relationial특성은 같지만 구조적 특성은 다르다binary ≠ multi-way각 내부노드는 최소 2개 child 가져야함(2,4) Trees(2-3-4tree)다음 속성을 만족하는 multi-way 트리모든 내부 노드가 child를 2,3,4개만 갖는 트리깊이 속성 (Depth Property): 모든 외부 노드는 같은 깊이에 있음Searching in a (2,4) tree with n items takes O(log n) time삽입(Insertion)키 k를 탐색하여 도달한 잎 노드의 부모 노드 v에 새로운 항목 (k, o)를 삽입합니다.삽입 전후에도 깊이 속성을 유지합니다. 즉, 모든 외부 노드는 같은 깊이에 있어야 ..

AVL 트리 (AVL Tree)균형 속성 (Height Balance Property)AVL 트리는 균형 이진 검색 트리입니다.높이 균형 속성을 만족합니다:트리 T의 모든 내부 노드 v에 대해, v의 자식 노드들의 높이 차이는 최대 1입니다.AVL 트리의 높이사실: n개의 키를 저장하는 AVL 트리의 높이는 O(log n)증명: AVL 트리의 높이 h에 따른 최소 내부 노드 수 n(h)를 제한합니다.기본 사례n(1) = 1n(2) = 2일반적인 경우n > 2인 경우, 높이가 h인 AVL 트리는 루트 노드와 높이가 h-1인 AVL 서브트리와 높이가 h-2인 AVL 서브트리로 구성됩니다.따라서, n(h) = 1 + n(h-1) + n(h-2)대소관계n(h-1) > n(h-2) 이므로, n(h) > 2n(h-..

Selection / Insertions Sort의 문제점1단계 : 입력 set에서 큐 구축2단계 : 우선순위 큐 구축Selection sort: Phase 1은 빠르지만 Phase 2는 매우 느리다.Insertion sort: Phase 1은 매우 느리지만 Phase 2는 빠르다.How can we balance the running times of the two phases?:효율적인 우선순위 큐의 구현은 heap이라는 데이터 구조를 사용Heap Data StructuresHeap(힙): 이진 트리 T는 관계적 속성과 구조적 속성을 만힙 순서 속성(Heap-order Property): 힙 T에서 루트가 아닌 모든 노드 v에 대해, v에 저장된 키는 v의 부모에 저장된 키보다 크거나 같다.완전 이진 ..

우선순위 큐정의우선순위가 지정된 요소들의 컬렉션을 저장하는 추상 데이터 타입임의의 요소 삽입을 지원하며,우선순위 순서에 따라 요소 제거 가능특징위치 기반 데이터 구조와는 다름이전 데이터 구조들은 요소를 특정 위치에 저장우선순위 큐는 우선순위에 따라 저장위치는 노출하지 않음첫번째 우선순위를 가진 요소는 언제든지 제거 가능용어키(Key)특정 요소에 지정된 속성요소를 식별하거나 가중치를 부여하는 데 사용고유하지 않아도 됨변경 가능엔트리(Entry)우선순위 큐에 저장되는 요소와해당 키의Total Order Relations 전체 순서 관계우선 순위 큐의 키들은 정렬이 정의된 임의의 객체가 될 수 있다키가 동일한 엔트리 두 개가 존재할 수 있다.Total Order Relations의 조건Reflexive pro..