트립

• 입력이 특정 순서로 주어질 때 그 성능이 떨어진다는 이진 검색 트리의 단점을 해결하기 위해 고안된 일종의 랜덤화된 이진 검색 트리
• 이진 검색 트리와 같은 성징을 가지고 있지만 트리의 형태가 원소들의 추가 순서에 따라 결정되지 않고 난수에 의해 임의대로 결정
• 트리 높이의 기대치는 항상 일정
• 새 노드가 추가될 때마다 해당 노드에 우선순위를 부여

트립의 조건

1. 이진 검색 트리의 조건 : 모드 노드에 대해 왼쪽 서브트리에 있는 노드들의 원소는 해당 노드의 원소보다 작고, 오른족 서브트리에 있는 노드들의 원소는 해당 노드의 원소보다 큽니다.
2. 힙의 조건 : 모든 노드의 우선순위는 각자의 자식 노드보다 크거나 같습니다.

트립의 높이

랜덤화에 의미가 있으려면 O(N)보다 작아야 함