트랩을 사용하는 경우

Question

누구나 treap을 사용하여 데이터를 저장하는 가장 좋은 방법은 무엇입니까?

트랩이 힙과 트리 구조보다 어떤 상황에서 더 좋을지 알고 싶습니다.

가능한 경우 실제 상황에서 몇 가지 예를 제공해주세요.

여기에서 트 랩핑을 사용하는 경우와 인터넷 검색으로 검색하려고했지만 아무 것도 찾지 못했습니다.

감사합니다.

Answer 1

실제 사례를 제공해 드릴 수는 없습니다. 하지만 프로그래밍 대회에서 몇 가지 문제를 해결하기 위해 treaps를 사용합니까 :

• http://poj.org/problem?id=2761
• http://poj.org/problem?id=3481

이 실제로 실제 문제가 아니지만, 이해가.

Answer 2

트리 기반 맵 구현으로 사용할 수 있습니다. 응용 프로그램에 따라 faster 일 수 있습니다. 2 년 전 Treap 및 Skip 목록을 Java로 재미있게 구현하고 TreeMap과 비교하는 기본적인 벤치마킹을 수행했으며 Treap이 가장 빠릅니다. 결과는 here입니다.

가장 큰 장점 중 하나는 Red-Black 나무에 비해 구현이 매우 쉽다는 것입니다. 그러나, 내가 기억하는 한, Red-Black 나무와 비교할 때, 연산에 보장 된 비용이 없습니다 (검색은 O (log n), 확률은 high). 특정 시간 제한이 요구되는 안전성이 중요한 응용 프로그램에 사용하십시오.

Answer 3

트랩은 밸런스 이진 검색 트리의 멋진 변형입니다. 이진 트리의 균형을 맞추기 위해 많은 알고리즘이 존재하지만, 대부분은 처리해야 할 특별한 경우가 수없이 많습니다. 반면에 Treaps를 코딩하는 것은 매우 쉽습니다. 임의성을 사용하여 대수적 인 높이가 될 것으로 예상되는 BBT가 있습니다. 좋은 문제가 treaps가 사용하여 해결하기 위해 - http://www.spoj.com/problems/QMAX3VN/ (쉬운 수준) http://www.spoj.com/problems/GSS6/ (보통 수준)

Answer 4

해시 값을 우선 순위로 사용하는 경우, treaps는 내용의 독특한 표현을 제공합니다.

AVL 트리 또는 rb 트리로 구현 된 항목의 순서 세트를 고려하십시오. 서로 다른 순서로 항목을 삽입하면 일반적으로 서로 다른 모양의 나무가됩니다 (모두 균형이 잡혀 있음). 주어진 내용에 대해 treap은 역사에 관계없이 항상 같은 모양입니다.

1. 보안상의 이유로 :

   나는 독특한 표현이 도움이 될 수있는 이유는 두 가지 이유를 보았다. treap은 역사에 대한 정보를 포함 할 수 없습니다.

2. 효율적인 서브 트리 공유. 내가 발견 한 집합 연산을위한 가장 빠른 알고리즘은 트랩을 사용합니다.