트립 (자료 구조)

키와 우선순위의 두 기준

각 노드는 검색할 키와 구조를 결정하는 우선순위를 가진다. 서로 다른 키를 사용한다면 왼쪽 부분 트리에는 더 작은 키가, 오른쪽에는 더 큰 키가 놓인다. 최대 힙 방식을 선택하면 부모의 우선순위가 자식보다 높아야 한다. 키의 크기와 우선순위의 크기는 서로 다른 기준이다.

같은 키에도 달라지는 모양

키가 2, 5, 9이고 최대 힙을 사용한다고 하자. 5의 우선순위가 가장 높으면 5가 루트이고 2와 9는 양쪽에 놓일 수 있다. 2의 우선순위가 가장 높으면 2가 루트가 된다. 우선순위가 중복되지 않으면 주어진 키와 우선순위의 조합이 트리 모양을 결정한다.

분할과 병합

트립은 기준 키 이하의 부분과 초과하는 부분으로 분할할 수 있다. 키 범위가 순서대로 분리된 두 트리는 우선순위를 비교하며 병합할 수 있다. 이러한 연산을 조합하면 삽입과 삭제를 구성할 수 있다. 임의의 두 트리를 키 범위 확인 없이 단순 병합해서는 탐색 트리 조건이 유지되지 않는다.

기대 성능의 조건

무작위 우선순위는 한쪽으로 치우친 트리의 가능성을 줄이는 데 사용한다. 기대 O(log n)은 모든 실행에서 같은 높이가 보장된다는 뜻이 아니다. 우선순위가 키 순서와 같은 방향으로 편향되면 긴 사슬이 생길 수 있다. 중복 키와 같은 우선순위의 처리 규칙도 구현에서 명확히 정해야 한다.