사전 스플레이 트리
자료구조

스플레이 트리

gabury1고친 사람 github-actions[bot]

스플레이 트리는 방금 찾은 값을 맨 위로 끌어올려 다음 찾기를 빠르게 합니다. 값을 크기 순서대로 담는 이진 탐색 트리의 한 종류입니다. 자주 찾는 값일수록 맨 위 가까이 머뭅니다. 여러 번 찾고 넣은 시간을 모아 보면 한 번에 드는 몫이 작게 유지됩니다.

쉽고 빠른 이해

스플레이 트리는 값을 찾을 때마다 찾은 값을 트리의 맨 위로 옮겨 둡니다. 같은 회원 정보를 짧은 시간에 여러 번 찾으면 두 번째부터는 맨 위에서 바로 찾습니다.

값을 크기 순서대로 담는 트리는 넣는 순서가 나쁘면 한 줄로 늘어서 찾기가 느려집니다. 흔한 해결책은 값마다 균형을 맞출 기록을 따로 적어 두는 것입니다. 스플레이 트리는 그런 기록 없이 찾을 때마다 모양을 고쳐 길을 줄여 나갑니다.

이렇게 돕니다.

  1. 보통의 방식대로 값을 찾아 내려간다
  2. 찾은 값을 바로 위의 값과 위아래를 바꾸는 동작으로 맨 위까지 끌어올린다
  3. 올라오는 동안 지나온 긴 길이 접혀 트리가 낮아진다

대가는 찾기만 해도 트리 모양이 바뀐다는 것입니다. 그래서 여러 스레드가 읽기만 할 때도 서로 막아야 합니다. 한 번의 찾기가 가끔 데이터 크기만큼 오래 걸리기도 합니다.

상세

이 절은 보통의 이진 탐색 트리가 왜 느려지는지에서 출발합니다. 그리고 1 부터 7 까지 키를 넣은 트리 하나로 스플레이가 트리를 어떻게 낮추는지 따라갑니다.

이진 탐색 트리와 높이

이진 탐색 트리는 값을 크기 순서대로 담아 두고 빨리 찾게 해 주는 트리입니다. 값을 담은 상자 하나하나를 노드라고 부릅니다. 노드마다 아래에 자식을 둘까지 둡니다. 맨 위 노드는 루트라고 부릅니다.

노드에 담겨 크기를 비교하는 값이 키입니다. 회원 번호로 회원을 찾는다면 회원 번호가 키입니다. 어느 노드에서 봐도 왼쪽 아래에는 그보다 작은 키만, 오른쪽 아래에는 큰 키만 둡니다.

찾을 때는 루트에서 출발해 한 층씩 내려갑니다. 찾는 키가 지금 노드의 키보다 작으면 왼쪽으로, 크면 오른쪽으로 갑니다. 그래서 찾는 시간은 몇 층을 내려가는지가 정합니다.

루트에서 어떤 노드까지 거치는 노드 수를 그 노드의 깊이라고 부릅니다. 루트의 깊이는 1 입니다. 가장 깊은 노드의 깊이가 트리의 높이입니다.

문제는 트리의 모양을 넣는 순서가 정한다는 것입니다. 작은 키부터 차례로 넣으면 한쪽으로만 매달려 한 줄로 늘어섭니다. 키가 n 개면 맨 끝의 키를 찾는 데 n 번 비교합니다. 값을 줄지어 이어 두고 처음부터 훑는 연결 리스트와 다를 것이 없습니다.

이것을 막는 흔한 방법은 넣고 지울 때마다 모양을 손봐 높이를 낮게 붙잡는 것입니다. 그런 트리를 균형 이진 탐색 트리라고 부릅니다. AVL 트리(Adelson-Velsky and Landis tree)는 노드마다 높이를 적어 두고 그 값으로 균형을 지킵니다. 레드-블랙 트리는 노드마다 빨강이나 검정 색을 적어 둡니다.

스플레이 트리는 노드에 그런 기록을 두지 않습니다. 대신 찾을 때마다 모양을 고칩니다.

찾은 노드를 루트로 올리는 스플레이

책상 위 서류 더미를 떠올려 봅시다. 서류를 하나 꺼내 본 뒤에는 더미 맨 위에 다시 얹어 둡니다. 그러면 요즘 자주 보는 서류는 늘 위쪽에 모입니다. 오래 안 본 서류만 아래로 내려갑니다.

스플레이 트리는 이진 탐색 트리에서 이 일을 합니다. 키를 찾으면 그 노드를 루트까지 끌어올립니다. 이 끌어올리기를 스플레이(splay)라고 부릅니다. 트리의 이름도 여기서 왔습니다.

찾는 키가 트리에 없으면 마지막으로 닿은 노드를 끌어올립니다. 넣기와 지우기도 끝에 스플레이를 한 번씩 합니다. 그래서 스플레이 트리의 연산은 모두 「내려가서 찾고, 닿은 노드를 루트로 올린다」는 한 꼴입니다.

끌어올릴 때 쓰는 도구는 회전입니다. 아래에서 회전을 먼저 봅니다. 그 뒤에 회전을 어떻게 짝지어 쓰는지 봅니다.

회전

회전은 부모와 자식 두 노드의 위아래를 바꾸는 일입니다. 크기 순서 규칙은 지킨 채 자식을 한 층 올리고 부모를 한 층 내립니다.

아래 그림은 20 을 한 층 올리기 전의 모양입니다. A·B·C 는 노드 아래에 매달린 노드 묶음입니다. 한 노드와 그 아래에 딸린 노드를 모두 묶은 것을 서브트리라고 부릅니다.

flowchart TD
    Y["30"] --> X["20 · 30 의 왼쪽 자식"]
    Y --> C["C · 30 보다 큰 키"]
    X --> A["A · 20 보다 작은 키"]
    X --> B["B · 20 과 30 사이의 키"]

20 을 올리면 30 은 20 의 오른쪽 자식으로 내려갑니다. B 는 20 을 떠나 30 의 왼쪽 자식이 됩니다. B 의 키는 모두 20 보다 크고 30 보다 작기 때문입니다.

flowchart TD
    X["20"] --> A["A · 20 보다 작은 키"]
    X --> Y["30 · 20 의 오른쪽 자식"]
    Y --> B["B · 20 과 30 사이의 키"]
    Y --> C["C · 30 보다 큰 키"]

두 그림 모두 크기 순서로 늘어놓으면 A, 20, B, 30, C 입니다. 회전은 이 순서를 바꾸지 않고 모양만 바꿉니다. 바꿔 거는 연결이 셋뿐이라 회전 한 번에 드는 시간은 트리 크기와 상관없이 일정합니다.

위 노드 30 이 오른쪽 아래로 내려갔으므로 이것을 오른쪽 회전이라고 부릅니다. 좌우를 뒤집은 것이 왼쪽 회전입니다.

이 글은 회전을 내려가는 위 노드의 이름으로 부릅니다. 「30 에서 회전한다」는 30 이 한 층 내려간다는 뜻입니다. 그 대신 30 의 자식 20 이 한 층 올라옵니다. 위 그림이 바로 30 에서 회전한 것입니다.

스플레이의 세 경우

회전 한 번은 노드를 한 층 올립니다. 스플레이는 노드를 두 층씩 올리는 것이 기본이라 끌어올릴 노드 위의 두 노드를 함께 봅니다. 바로 위가 부모입니다. 부모의 부모는 조부모라고 부릅니다.

경우는 셋입니다. 두 물음이 이 셋을 가릅니다. 부모가 루트인가, 그리고 끌어올릴 노드와 부모가 같은 쪽으로 매달렸나입니다.

부모가 루트이면 지그, 같은 쪽이면 지그-지그, 반대쪽이면 지그-재그라고 부릅니다. 끌어올릴 노드가 루트가 될 때까지 이 판정을 되풀이합니다.

flowchart TD
    S{"끌어올릴 노드가 루트인가"} -->|"예"| E["스플레이 끝"]
    S -->|"아니오"| P{"부모가 루트인가"}
    P -->|"예"| Z1["지그 · 부모에서 회전 한 번"]
    P -->|"아니오"| Q{"노드와 부모가 같은 쪽에 매달렸나"}
    Q -->|"예"| Z2["지그-지그 · 조부모 먼저, 그다음 부모"]
    Q -->|"아니오"| Z3["지그-재그 · 부모 먼저, 그다음 조부모"]
    Z1 --> E
    Z2 --> S
    Z3 --> S

지그(zig)는 끌어올릴 노드가 루트 바로 아래에 있을 때입니다. 부모에서 회전을 한 번 하면 노드가 루트가 됩니다. 그러면 스플레이가 끝납니다. 「회전」 소절의 그림이 곧 지그입니다.

노드와 부모가 같은 쪽으로 매달려 한 줄을 이루면 지그-지그(zig-zig)입니다. 이때는 조부모에서 먼저 회전하고 그다음 부모에서 회전합니다. 아래는 10 을 끌어올리기 전입니다.

flowchart TD
    G["30 · 조부모"] --> P["20 · 30 의 왼쪽 자식"]
    P --> X["10 · 20 의 왼쪽 자식"]

30 에서 먼저 돌리면 20 이 올라섭니다. 30 은 20 의 오른쪽으로 내려갑니다. 이어서 20 에서 돌리면 10 이 올라섭니다. 줄의 방향이 뒤집힌 모양이 됩니다.

flowchart TD
    X["10"] --> P["20 · 10 의 오른쪽 자식"]
    P --> G["30 · 20 의 오른쪽 자식"]

노드 셋만 보면 한 줄이 다른 한 줄로 바뀐 것뿐입니다. 조부모부터 돌리는 순서의 효과는 줄이 길 때 드러납니다. 뒤의 「한 줄로 선 트리의 스플레이」 소절이 그것을 보입니다.

노드와 부모가 서로 반대쪽에 매달려 꺾여 있으면 지그-재그(zig-zag)입니다. 이때는 부모에서 먼저 회전해 꺾인 곳을 폅니다. 이어서 조부모에서 회전합니다. 아래는 20 을 끌어올리기 전입니다.

flowchart TD
    G["30 · 조부모"] --> P["10 · 30 의 왼쪽 자식"]
    P --> X["20 · 10 의 오른쪽 자식"]

10 에서 먼저 돌리면 20 이 한 층 올라 30 의 왼쪽 자식이 됩니다. 10 은 20 의 왼쪽 자식으로 내려갑니다. 꺾였던 곳이 펴져 한 줄이 됩니다.

flowchart TD
    G["30 · 조부모"] --> X["20 · 30 의 왼쪽 자식"]
    X --> P["10 · 20 의 왼쪽 자식"]

이어서 30 에서 돌리면 20 이 맨 위로 올라섭니다. 10 과 30 은 양쪽 자식이 됩니다. 높이가 3 에서 2 로 줄었습니다.

flowchart TD
    X["20"] --> P["10 · 20 의 왼쪽 자식"]
    X --> G["30 · 20 의 오른쪽 자식"]

이 두 번의 회전은 AVL 트리가 꺾인 모양을 고칠 때 쓰는 이중 회전과 같은 동작입니다.

한 줄로 선 트리의 스플레이

빈 스플레이 트리에 1 부터 7 까지 차례로 넣어 봅니다. 새 키는 늘 지금까지의 가장 큰 키보다 커서 루트의 오른쪽 자식으로 들어갑니다. 그 뒤 지그 한 번으로 루트가 됩니다. 이전 트리는 새 루트의 왼쪽에 매달립니다.

그래서 넣기 일곱 번은 모두 비교 한 번과 회전 한 번으로 끝납니다. 결과는 7 을 루트로 모든 노드가 왼쪽 자식으로만 늘어선 한 줄입니다.

flowchart TD
    N7["7 · 루트"] --> N6["6"] --> N5["5"] --> N4["4"] --> N3["3"] --> N2["2"] --> N1["1 · 깊이 7"]

이제 1 을 찾습니다. 일곱 층을 내려가야 하니 이 한 번은 비쌉니다. 찾은 뒤 1 을 스플레이하면 지그-지그가 세 번 일어납니다.

첫 번째 지그-지그는 1 과 그 위의 2·3 을 돌립니다. 3 에서, 이어서 2 에서 회전하면 1 이 두 층 올라옵니다. 2 와 3 은 1 의 오른쪽에 한 줄로 매달립니다.

flowchart TD
    N7["7 · 루트"] --> N6["6"] --> N5["5"] --> N4["4"]
    N4 --> N1["1 · 4 의 왼쪽 자식"]
    N1 --> N2["2 · 1 의 오른쪽 자식"]
    N2 --> N3["3 · 2 의 오른쪽 자식"]

두 번째 지그-지그는 1 과 그 위의 4·5 를 돌립니다. 1 이 다시 두 층 올라 6 의 왼쪽 자식이 됩니다. 2 와 3 은 4 의 왼쪽으로 옮겨 붙습니다. 5 는 4 의 오른쪽 자식이 됩니다.

flowchart TD
    N7["7 · 루트"] --> N6["6"]
    N6 --> N1["1 · 6 의 왼쪽 자식"]
    N1 --> N4["4 · 1 의 오른쪽 자식"]
    N4 --> N2["2 · 4 의 왼쪽 자식"]
    N4 --> N5["5 · 4 의 오른쪽 자식"]
    N2 --> N3["3 · 2 의 오른쪽 자식"]

마지막 지그-지그는 1 과 그 위의 6·7 을 돌립니다. 1 이 루트가 됩니다.

flowchart TD
    N1["1 · 루트"] --> N6["6 · 1 의 오른쪽 자식"]
    N6 --> N4["4 · 6 의 왼쪽 자식"]
    N6 --> N7["7 · 6 의 오른쪽 자식"]
    N4 --> N2["2 · 4 의 왼쪽 자식"]
    N4 --> N5["5 · 4 의 오른쪽 자식"]
    N2 --> N3["3 · 2 의 오른쪽 자식"]

높이가 7 에서 5 로 줄었습니다. 한 줄이던 트리가 반쯤 접혀 가지를 쳤습니다. 다음에 2 를 찾으면 네 층만 내려가면 됩니다.

견주기 위해 같은 한 줄 트리에서 지그-지그 없이 부모에서 회전하기만 되풀이해 1 을 올려 봅니다. 결과는 아래와 같습니다. 7 아래로는 여전히 왼쪽 자식으로만 늘어서 있습니다.

flowchart TD
    M1["1 · 루트"] --> M7["7 · 1 의 오른쪽 자식"] --> M6["6"] --> M5["5"] --> M4["4"] --> M3["3"] --> M2["2 · 깊이 7"]

한 층씩 올리는 방법은 한 줄을 다른 한 줄로 옮겨 놓았을 뿐입니다. 이제 2 를 찾으면 또 일곱 층을 내려갑니다. 이어서 3, 4 를 차례로 찾아도 매번 줄을 거의 끝까지 내려가야 합니다.

지그-지그는 조부모부터 돌려서 줄을 접습니다. 줄이 길수록 접히는 효과가 커서, 지나온 길 위의 노드들이 대략 절반 깊이로 올라옵니다. 비싼 찾기 한 번이 트리를 낮춰 두어 뒤의 찾기를 싸게 만드는 것입니다.

넣기와 지우기

넣기는 보통의 이진 탐색 트리처럼 빈 곳을 찾아 새 노드를 매답니다. 그다음 새 노드를 스플레이해 루트로 올립니다. 앞 소절의 한 줄 트리가 이렇게 만들어졌습니다.

지우기는 지울 키를 먼저 스플레이해 루트로 올립니다. 루트를 떼어 내면 왼쪽과 오른쪽 두 서브트리가 남습니다. 둘을 다시 이으면 지우기가 끝납니다.

잇는 방법은 이렇습니다. 왼쪽 서브트리에서 가장 큰 키를 스플레이해 그 서브트리의 루트로 올립니다. 가장 큰 키보다 큰 키는 없으니 올라온 뒤 오른쪽이 비어 있습니다. 그 빈 오른쪽에 오른쪽 서브트리를 매답니다.

flowchart TD
    subgraph 떼어낸뒤["루트를 떼어 낸 뒤 · 두 서브트리"]
        L["왼쪽 서브트리 · 지운 키보다 작은 키"]
        R["오른쪽 서브트리 · 지운 키보다 큰 키"]
    end
    subgraph 이은뒤["왼쪽의 가장 큰 키를 올려 이은 뒤"]
        M["왼쪽의 가장 큰 키 · 새 루트"] --> ML["왼쪽 서브트리의 나머지"]
        M --> MR["오른쪽 서브트리"]
    end
    떼어낸뒤 --> 이은뒤

왼쪽 서브트리의 키는 모두 오른쪽 서브트리의 키보다 작습니다. 그래서 이렇게 이어도 크기 순서 규칙이 지켜집니다.

여러 번을 모아 세는 비용

스플레이 트리는 연산 한 번의 시간을 약속하지 않습니다. 한 줄 트리에서 1 을 찾을 때처럼 한 번이 키 수 n 에 비례해 걸릴 수 있습니다. 이것을 빅오 표기법으로 O(n) 이라고 적습니다.

대신 여러 번을 모은 합을 약속합니다. 빈 트리에서 시작해 찾기·넣기·지우기를 모두 m 번 하면 전체가 O(m log n) 안에 끝납니다. n 은 그동안 트리에 든 키가 가장 많을 때의 수입니다.

log n 은 n 을 몇 번 반으로 나눠야 1 이 되는지를 세는 값입니다. 키가 백만 개면 20 쯤입니다. 키가 두 배로 늘어도 이 값은 1 만 늡니다.

전체를 횟수 m 으로 나누면 한 번에 O(log n) 꼴입니다. 이렇게 여러 번을 모아 나눈 한 번의 몫을 분할 상환 비용이라고 부릅니다. 한 줄 트리를 만든 넣기 일곱 번이 모두 쌌던 덕에, 그 뒤 1 을 찾은 비싼 한 번을 합쳐도 한 번의 몫은 작습니다.

이 약속은 트리 모양에 점수를 매겨 증명합니다. 노드마다 자기 서브트리에 든 노드 수의 로그를 구해 모두 더한 값이 점수입니다. 한 줄로 늘어선 트리는 이 점수가 높습니다. 고르게 퍼진 트리는 낮습니다.

싼 연산에는 실제로 걸린 시간보다 조금 더 많은 비용을 매깁니다. 그 차액은 점수로 쌓입니다. 한 줄 트리를 만든 넣기 일곱 번이 그랬습니다. 넣을 때마다 줄이 길어져 점수가 올라갔습니다.

비싼 스플레이는 긴 줄을 접어 점수를 크게 떨어뜨립니다. 떨어진 점수만큼이 그 비싼 시간을 메웁니다.

이렇게 자료구조의 상태에 점수를 매겨 비용을 나눠 세는 방법을 잠재 함수 방법이라고 부릅니다. 점수가 쌓여 있다가 비싼 연산 때 풀려 나가는 꼴입니다.

자주 찾는 키와 루트까지의 거리

짧은 시간 동안 일부 데이터만 되풀이해 쓰는 경향을 참조 지역성이라고 부릅니다. 로그인해 있는 회원 두세 명의 회원 번호로 회원 정보를 번갈아 조회하는 일이 그 예입니다. 스플레이 트리는 이런 접근에서 이득을 봅니다.

방금 찾은 키는 루트에 있으니 곧 다시 찾으면 거의 바로 끝납니다. 최근에 찾은 몇 개의 키를 번갈아 찾을 때도 그 키들은 루트 가까이 모여 있습니다. 한 키를 찾는 분할 상환 비용은 그 키를 지난번에 찾은 뒤 다른 키를 몇 가지나 찾았는지에 따라 정해집니다. 이 성질을 작업 집합 정리라고 부릅니다.

더 센 견주기도 있습니다. 상대는 접근 순서를 미리 다 알고, 그 순서에 맞춰 회전까지 가장 잘 고르는 이진 탐색 트리입니다.

스플레이 트리는 접근 순서를 미리 모릅니다. 그런데도 어떤 접근 순서에서든 그런 트리보다 늘 일정한 배수 안에서만 느리다는 추측이 있습니다. 이 추측을 동적 최적성 추측이라고 부릅니다. 아직 증명되지 않았습니다.

찾기가 트리를 바꾸는 대가

보통의 이진 탐색 트리에서 찾기는 트리를 읽기만 합니다. 스플레이 트리에서는 찾기도 회전으로 연결을 바꿔 씁니다. 읽기가 곧 쓰기가 됩니다.

그래서 여러 스레드가 한 트리를 함께 쓰면 찾기끼리도 서로 막아야 합니다. 둘이 동시에 회전하면 연결이 꼬이기 때문입니다. 읽기끼리는 함께 들어오게 하는 읽기-쓰기 락을 써도 찾기가 전부 쓰기라 동시에 들어오지 못합니다.

두 번째 대가는 한 번의 긴 지연입니다. 분할 상환 O(log n) 은 합에 대한 약속이라 그중 한 번은 O(n) 이 걸릴 수 있습니다. 응답 하나하나가 빨라야 하는 서버에서는 이 한 번이 드물게 튀어 오르는 긴 응답 시간으로 드러납니다. 이렇게 드물게 튀는 긴 응답을 꼬리 지연이라고 부릅니다.

세 번째는 접근이 고르게 흩어질 때입니다. 찾을 때마다 회전으로 연결을 바꿔 쓰는 일이 붙습니다. 다음 찾기가 방금 올린 키 근처를 다시 찾지 않으면 이 일은 얻는 것 없이 비용으로만 남습니다.

연산별 비용

아래 표는 두 가지 약속을 나란히 놓은 것입니다. 「한 번의 최악」 열은 연산 한 번이 가장 오래 걸릴 때입니다. 「여러 번의 분할 상환」 열은 여러 번을 모아 나눈 한 번의 몫입니다.

연산 한 번의 최악 여러 번의 분할 상환
찾기 O(n) O(log n)
넣기 O(n) O(log n)
지우기 O(n) O(log n)
크기 순서대로 모두 꺼내기 O(n) O(n)

크기 순서대로 모두 꺼내는 일은 모양과 상관없이 O(n) 입니다. 어느 노드에서든 왼쪽 서브트리, 자기, 오른쪽 서브트리 순으로 훑으면 크기 순서가 나옵니다. 이 방법을 중위 순회라고 부릅니다.

공간은 노드 수만큼인 O(n) 을 씁니다. 노드마다 키와 두 자식을 가리키는 참조만 둡니다. AVL 트리의 높이나 레드-블랙 트리의 색처럼 균형을 위해 더 두는 칸이 없습니다.

AVL 트리·레드-블랙 트리와 가르는 기준

세 트리 모두 찾기·넣기·지우기를 O(log n) 에 끝냅니다. 차이는 그 약속이 한 번 한 번에 대한 것인가, 여러 번의 합에 대한 것인가입니다. 아래 표가 셋을 가르는 축을 모읍니다.

스플레이 트리 AVL 트리 · 레드-블랙 트리
O(log n) 을 약속하는 단위 여러 번을 모은 분할 상환 연산 한 번 한 번의 최악
노드에 더 두는 정보 없음 높이나 색
찾기가 트리를 바꾸나 바꾼다 안 바꾼다
자주 찾는 키의 깊이 루트 가까이 올라온다 찾는 횟수와 상관없다

같은 키를 되풀이해 찾는 일이 잦고 한 번의 긴 지연을 견딜 수 있으면 스플레이 트리를 고릅니다. 여러 스레드가 동시에 읽거나 응답 하나하나에 상한이 있어야 하면 AVL 트리나 레드-블랙 트리를 고릅니다.

어느 쪽이든 노드마다 키에 값을 짝지어 담으면 키 순서가 지켜지는 맵이 됩니다. 「이 번호 다음의 회원」이나 「가장 작은 키」처럼 순서로 묻는 일에 이런 맵을 씁니다.

관련 항목

스플레이 트리가 속하는 상위 분류

자료구조 · 트리 · 이진 트리 · 이진 탐색 트리 · 자가 조정 자료구조 · 균형 이진 탐색 트리

스플레이 트리를 이루는 구성 요소

노드 · 루트 노드 · 리프 노드 · 부모 노드 · 자식 노드 · 서브트리 · 노드 깊이 · 트리 높이

스플레이 트리가 모양을 바꾸는 연산

스플레이 · 트리 회전 · 왼쪽 회전 · 오른쪽 회전 · 이중 회전 · 트리 분할 · 트리 병합

스플레이 트리와 같은 일을 두고 겨루는 자료구조

AVL 트리 · 레드-블랙 트리 · 트립 · AA 트리 · 스킵 리스트 · B-tree · 해시테이블 · 연결 리스트

스플레이 트리의 비용을 따지는 분석 방법

분할 상환 비용 · 분할 상환 분석 · 잠재 함수 방법 · 빅오 표기법 · 최악 시간 복잡도 · 로그 시간

스플레이 트리가 누리는 접근 성질

참조 지역성 · 작업 집합 정리 · 정적 최적성 · 동적 최적성 추측 · 자기 조직화 리스트

스플레이 트리 위에 세우는 추상 자료형

맵 · 집합 · 정렬된 맵 · 정렬된 집합 · 우선순위 큐 · 링크-컷 트리

스플레이 트리를 여러 스레드가 쓸 때 부딪히는 문제

스레드 · 동시성 · 락 · 읽기-쓰기 락 · 락 경합 · 꼬리 지연

다른 이름: splay tree