[일반] splay tree 신기하네용

[익명(118.36)]

따라서 구현은 할 수 있겠는데

원리는 이해가 좀 ㅋㅋ ㅎㅎ;;

[지덕군(jidockun)]

스플레이 말고 트립 합시다!

[익명(118.36)]

트립은 무엇인가요

[익명(121.188)]

스플레이는 시간복잡도가 완전히 증명은 안된걸루 알아욤

[익명(118.36)]

log n 이라던데 아닌가요

[p플랫(urd05)]

완전히 증명 안 된 건 아니고 amortized O(logN)으로 한 번 시행했을 때 로그인 건 보장이 안 되는데 N번 시행하면 O(NlogN)이 보장되는 느낌

[p플랫(urd05)]

https://algoshitpo.github.io/2020/03/23/PotentialMethod/

[익명(121.188)]

ㅇㅎ 증명 가능하구나 증명 안되줄 ㄱㅅㄱㅅ

[p플랫(urd05)]

근데 300줄 짜고 런타임에러 디버깅해보고 WA 디버깅해보면 좋아할 수가 없는데...

[익명(121.188)]

사실 짤일은 그닥 없음요. 라이브러리에는 RB 트리가 쓰이고 대회환경에서는 짤 시간이 잘 안나서 보통 안풀림

[익명(222.233)]

대회 중에는 팀노트 배끼면 개꿀이라서 풀이 보이면 바로 짜지 않나요? - dc App

[익명(121.188)]

팀노트 얘기하는거면 일단 길이 자체가 길어서 실수할 가능성도 높고, 자료구조 때려박으면 풀리는 문제는 잘 안내려고 합니다

[익명(121.188)]

PS 는 퍼즐 풀이 같은 문제를 좋아하고, 암기식으로 풀 수 있는 문제는 지양해요. 원리와 활용 방법을 알아두는건 괜찮은데, 실제로 구현하는건 월파를 노리거나 최소 레드급은 되어야 해볼 일이 있을거에요

[Jerry(feb06)]

그냥 BBST같아보이는데 배울가치있음?

[익명(121.125)]

루트 맘대로 바꿀수있는거 때문에 십덕 자료구조에 잘응용됨

[익명(223.62)]

Splay Tree의 Splay 연산은 BST를 유지하면서 특정 노드를 루트로 올릴 수 있음. 이 Splay 연산을 2번 이용하면 [l, r] 구간을 하나의 서브트리로 모아줄 수 있고, 이 성질을 이용해 다양한 쿼리를 처리할 수 있음. - dc App