[일반] treap 궁금한게 있는데

[익명(118.235)]

treap이 랜덤으로 우선순위를 부여해서 bst를 bbst에 가깝게 만드는 거잖아

그럼 데이터 입력이 랜덤하게 들어오는 것이 보장되면

그냥 bst를 만들어도 treap과 유사하다고 볼 수 있나?

[대학원오지마세요(publfl)]

Treap의 깊이와 데이터의 랜덤성은 별개임. priority를 얼마나 랜덤하게 설정하느냐가 깊이를 결정해서, 데이터가 랜덤으로 들어와도 priority를 1,2,3,4… 이런식으로 주면 그건 O(N)이됨