pb_ds의 간단한 고찰 - 트리 구현체

PS를 좀 오래 한 사람이라면 pb_ds의 존재를 알고 있을 것이다. 그리고 보통 트리의 구현체로 r-b 트리인 rb_tree_tag를 쓸 것이다.

 

하지만 r-b 트리 외에도 스플레이 트리 구현체인 splay_tree_tag가 존재한다.

 

C++ 상에서 구현된 r-b 트리는 상수가 크다고 알려져 있는데 그럼 스플레이 트리를 대신 쓰면 성능이 좀 좋아질까?

 

그래서 해보았다.

 

백준 2104 - 스플레이 트리

 

http://boj.kr/1404da72672b4c429dfc8f2504ff4558

 

백준 2104 - r-b 트리

 

http://boj.kr/b9c4a1b73379447192b2c6153f223525

 

무려 스플레이 트리가 2배 더 빠르다!

 

그러면 다른 문제로 확인해보자.

 

백준 1572 - 스플레이 트리

 

http://boj.kr/cdf86f64af034ab1a262bbf0cbd26b43

 

백준 1572 - r-b 트리

 

http://boj.kr/5479023cb10a49e0809a5e0f8f012121

 

이건 스플레이 트리가 2배를 넘어 느리다..!

 

ps 수준에서는 스플레이 트리가 좀 더 유리할 거라 봤는데 아니었다. 궁금해서 더 찾아보니 각 tag에 대해 테스트를 한 결과가 있다.

 

https://gcc.gnu.org/onlinedocs/libstdc++/manual/policy_based_data_structures_test.html

 

 

삽입하고 찾는 연산에 대해 rb_tree_tag가 가장 빠르다고 한다. 그 와중에 기본 std::set은 압도적으로 느리다.

 

생각해보니 2104 문제는 erase 연산이 들어가는데 아쉽게도 원소를 제거할 때 측정한 자료는 없다.

 

추측컨데 원소의 삭제가 동반되는 경우, 스플레이 트리가 더 좋은 성능을 보여주는 것 같다. 그 외에는 r-b 트리를 쓰도록 하자.