반응형 [C++로 배우는 알고리즘과 자료구조 심화] Day 4: 이면 탐색 트리 (Treap) 이면 탐색 트리 (Treap)이면 탐색 트리(Treap)는 이진 탐색 트리(BST)와 힙(Heap)의 특성을 동시에 가지는 자료구조입니다. 각 노드는 키(key)와 우선순위(priority)를 가지며, 다음 두 가지 성질을 만족합니다:이진 탐색 트리 성질: 키의 값에 대해 이진 탐색 트리 성질을 만족합니다.힙 성질: 우선순위에 대해 최대 힙 또는 최소 힙 성질을 만족합니다.트라이의 주요 특징삽입, 삭제, 검색:평균 시간 복잡도: (O(\log n))최악의 경우 시간 복잡도: (O(n))회전 연산:이중회전을 통해 트리의 균형을 유지합니다.트라이의 기본 연산삽입 (Insert): 새로운 노드를 삽입합니다.삭제 (Delete): 특정 키를 가진 노드를 삭제합니다.검색 (Search): 특정 키를 가진 노드를 .. 2024. 8. 1. 이전 1 다음 반응형
