스플레이 트리 회전 계산기

찾은 노드를 회전으로 뿌리까지 끌어올립니다. 노드 x, 부모 p, 조부모 g라 할 때 p가 뿌리면 zig(한 번 회전), x와 p의 방향이 같으면 zig-zig, 다르면 zig-zag로 나눠 두 번씩 회전합니다. 균형을 재거나 노드마다 균형 정보를 들고 다니는 일은 하지 않습니다.

조부모를 «먼저» 돌려야 하며, 노드를 두 번 올리는 것으로 바꾸면 분할상환 보장이 깨집니다. 조부모 먼저 돌리면 노드 아래 매달려 있던 부분트리가 경로의 양쪽으로 갈라져 붙어 깊이가 접히지만, 노드만 두 번 위로 빼면 나머지는 그대로 한 줄에 남습니다. 노드 16개가 한 줄로 늘어선 트리에서 가장 깊은 노드를 끌어올리면 제대로 한 쪽은 높이가 16에서 10으로 줄고, 노드를 두 번 올리는 쪽은 회전 수가 같은데도 16 그대로입니다.

그쪽은 균형을 «유지»하고 스플레이 트리는 균형을 보장하지 않습니다. 한 줄로 늘어선 트리가 얼마든지 나올 수 있어 한 번의 접근이 O(n)이 될 수 있습니다. 대신 m번의 접근이 모두 합쳐서 O(m log n)이 되는데, 이것이 분할상환 보장이며 최악의 한 번이 아니라 전체를 견주는 이야기입니다. 균형 정보를 저장하지 않아도 된다는 것과 최근에 쓴 것이 위로 올라온다는 것이 얻는 쪽입니다.

중위 순회가 언제나 같은 정렬 순서인지로 봅니다. 회전은 이진탐색트리의 성질을 건드리지 않으므로 어떤 회전을 몇 번 하든 중위 순회 결과가 달라지면 안 됩니다. 이 계산기는 매 단계마다 그것을 확인해 결과에 표시합니다.

실제 접근이 고르게 흩어지지 않고 몰리는 경우가 많기 때문입니다. 방금 쓴 것을 곧 다시 쓸 가능성이 높으면 그것을 뿌리에 두는 편이 유리하고, 스플레이 트리는 그 습성을 자료구조 자체에 담습니다. 접근 분포가 치우칠수록 이득이 커지고, 완전히 고르게 흩어지면 균형 트리와 비슷해집니다.

이 계산기는 트리를 그대로 둡니다. 실제 스플레이 트리는 탐색이 멈춘 마지막 노드를 대신 끌어올리는데, 다음에 그 근처를 다시 찾을 가능성이 높기 때문입니다. 여기서는 회전 과정을 보이는 것이 목적이라 그 규칙을 넣지 않았습니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 키는 이 기기에만 남습니다.