딥스(Deap)는 루트(root) 노드에 어떠한 원소나 키 값도 저장하지 않는 특수한 형태의 데이터 구조입니다. 이 구조는 다음과 같은 규칙에 따라 구성됩니다.
딥스의 기본 규칙
- 루트 노드에는 원소가 존재하지 않으며, 항상 비어 있습니다.
- 딥스의 왼쪽 서브트리(left subtree)는 최소 힙(min heap) 역할을 수행합니다.
- 딥스의 오른쪽 서브트리(right subtree)는 최대 힙(max heap) 역할을 수행합니다.
이러한 구조적 특징 덕분에 딥스는 아래의 명제를 수학적으로 보장할 수 있습니다.
핵심 성질
어떤 노드의 왼쪽 서브트리와 오른쪽 서브트리가 모두 비어 있지 않고, 서로 대응되는 두 노드를 각각 'a'와 'b'라고 할 때 다음 부등식이 항상 성립합니다.
a.KeyValue <= b.KeyValue
즉, 같은 위치에서 서로 대응하는 왼쪽 트리의 노드 값은 오른쪽 트리의 노드 값보다 항상 작거나 같습니다. 이 성질 덕분에 딥스는 하나의 구조 안에서 최솟값과 최댓값을 동시에 효율적으로 관리할 수 있는 자료구조로 활용됩니다.