트립(Treap) 삽입·회전 계산기
키는 이진탐색트리 순서로, 우선순위는 힙 순서로 지키는 트립을 한 걸음씩 그려 봅니다. 우선순위를 무작위로 뽑으면 정렬된 데이터를 넣어도 트리가 한쪽으로 쏠리지 않는다는 것을 보통의 이진탐색트리와 나란히 비교해 보여 줍니다.
공백이나 쉼표로 나눠 넣습니다. 넣는 순서대로 삽입하며 60개까지 다룹니다.
같은 씨앗이면 같은 트리가 나옵니다. 바꿔 가며 모양이 어떻게 달라지는지 보세요.
노드 12개 트립의 높이
5
우선순위 없이 같은 순서로 넣은 보통의 이진탐색트리는 높이가 12입니다. 완전히 균형 잡힌 트리라면 4이고, 무작위 우선순위의 기대 높이 어림은 3·ln n = 7.5입니다.
3 (우선순위 799) ├─ 2 (우선순위 542) │ └─ 1 (우선순위 271) └─ 8 (우선순위 662) ├─ 5 (우선순위 535) │ ├─ 4 (우선순위 457) │ └─ 6 (우선순위 487) │ └─ 7 (우선순위 354) └─ 9 (우선순위 506) └─ 11 (우선순위 490) ├─ 10 (우선순위 86) └─ 12 (우선순위 14)
삽입 한 걸음씩
| 키 | 우선순위 | 회전 | 깊이 | 높이 |
|---|---|---|---|---|
| 1 | 271 | 없음 | 0 | 1 |
| 2 | 542 | 1 기준 좌회전 | 0 | 2 |
| 3 | 799 | 2 기준 좌회전 | 0 | 3 |
| 4 | 457 | 없음 | 1 | 3 |
| 5 | 535 | 4 기준 좌회전 | 1 | 3 |
| 6 | 487 | 없음 | 2 | 3 |
| 7 | 354 | 없음 | 3 | 4 |
| 8 | 662 | 7 기준 좌회전, 6 기준 좌회전, 5 기준 좌회전 | 1 | 5 |
| 9 | 506 | 없음 | 2 | 5 |
| 10 | 86 | 없음 | 3 | 5 |
| 11 | 490 | 10 기준 좌회전 | 3 | 5 |
| 12 | 14 | 없음 | 4 | 5 |
새 노드를 잎에 붙인 뒤 부모보다 우선순위가 크면 회전으로 한 칸씩 끌어올립니다. 회전은 탐색트리 순서를 바꾸지 않으므로 올리는 동안 키 순서는 그대로입니다.
같은 키에 우선순위만 바꾸면
| 씨앗 | 뿌리 | 높이 | 회전 |
|---|---|---|---|
| 1 | 10 | 6 | 10 |
| 2 | 5 | 6 | 9 |
| 3 | 5 | 5 | 8 |
| 4 | 8 | 7 | 9 |
| 5 | 9 | 6 | 9 |
| 6 | 9 | 6 | 9 |
키 집합은 같은데 우선순위만 달라 뿌리도 높이도 달라집니다. 어느 것도 크게 한쪽으로 쏠리지는 않는다는 것이 무작위 우선순위의 보장입니다.
사용 방법
- 1우선순위를 무작위로 뽑을지 직접 넣을지 고릅니다.
- 2넣을 키를 공백이나 쉼표로 나눠 적습니다. 적은 순서대로 삽입합니다.
- 3완성된 트리와 높이를, 우선순위 없이 같은 순서로 넣은 이진탐색트리의 높이와 비교합니다.
- 4삽입 표에서 회전이 언제 몇 번 일어나는지 확인합니다.
- 5난수 씨앗을 바꾸거나 우선순위를 직접 넣어 트리 모양이 어떻게 달라지는지 봅니다.
자주 묻는 질문
키는 이진탐색트리 순서로, 우선순위는 힙 순서로 동시에 지키는 트리입니다. 이름도 tree와 heap을 합친 것입니다. 모든 노드에서 왼쪽 부분트리의 키 < 자기 키 < 오른쪽 부분트리의 키이면서, 자기 우선순위가 두 자식보다 크거나 같습니다.
보통의 이진탐색트리처럼 잎에 붙인 뒤, 부모보다 우선순위가 크면 회전으로 한 칸씩 끌어올립니다. 회전은 중위 순회 결과를 바꾸지 않으므로 올리는 동안 키 순서는 그대로 유지됩니다. 부모보다 작아지는 순간 멈춥니다.
트리 모양이 (키, 우선순위) 쌍으로만 정해져 삽입 순서와 무관해지기 때문입니다. 우선순위를 무작위로 뽑았다면 그 트리는 「키들을 무작위 순서로 넣은 이진탐색트리」와 같은 분포를 따르고 기대 높이가 약 3·ln n입니다. 정렬된 데이터를 넣어도 한쪽으로 쏠리지 않습니다.
무작위성의 보장이 사라집니다. 우선순위를 키 순서대로 주면 트립도 그대로 한 줄로 늘어서 탐색이 O(n)이 됩니다. 무작위성은 자료의 성질이 아니라 우리가 집어넣는 것이라는 점이 요점이며, 그래서 입력이 악의적이어도 기대 성능이 지켜집니다.
같은 구조입니다. (키, 우선순위) 쌍의 집합에서 우선순위가 가장 큰 것을 뿌리로 두고 키로 좌우를 갈라 되풀이하면 나오는 트리가 데카르트 트리이며, 트립은 그 우선순위를 무작위로 뽑은 것입니다. 그래서 삽입 순서를 바꿔도 같은 트리가 나옵니다.
균형을 잡는 기준이 다릅니다. AVL은 높이차, 레드블랙은 색, 스플레이는 접근 순서, 트립은 무작위 우선순위입니다. 트립은 최악의 경우를 막지 못하고 기댓값만 보장하지만 코드가 훨씬 짧고 두 트립을 합치거나 쪼개는 연산이 자연스럽게 나옵니다.
힙 조건을 「부모 ≥ 자식」으로 두면 트리는 만들어지지만 모양이 삽입 순서에 영향을 받아 무작위성의 보장이 약해집니다. 실제 구현에서는 겹칠 확률이 무시할 만큼 넓은 범위에서 우선순위를 뽑습니다.
전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.
알아두면 좋은 점
- 삽입만 다룹니다. 삭제(우선순위를 −∞로 낮춰 잎까지 내린 뒤 떼어내기)와 분할·병합은 이 도구에 없습니다.
- 키가 60개까지만 들어갑니다. 그림으로 보는 것이 목적이라 그 이상은 화면에서 읽기 어렵습니다.
- 이미 있는 키는 건너뜁니다. 중복 키를 허용하는 구현과는 다릅니다.
- 기대 높이 3·ln n은 어림입니다. 실제 값은 씨앗마다 달라지므로 표에서 여러 씨앗을 비교해 보세요.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 2일 · 결과는 참고용 추정치입니다.