스플레이 트리 (Splay Tree)

스플레이 트리

트리의 노드가 탐색 또는 갱신을 위해 접근된 후, 스플레이되는 이진 탐색 트리를 말합니다.

* 노드가 스플레이 된다 = 노드를 루트로 이동시킨다

- 사용되는 환경에 따라 재조정되는 방식

==> 트렌드를 반영하는 이진트리라 할 수 있습니다.

스플레이 트리의 장점

1. 구현이 단순합니다. 

( AVL 트리 같은 경우는, 균형을 유지하기 위해 복잡했는데 스플레이 트리는 이것이 필요 없습니다. )

2. 탐색, 삽입, 삭제에 O(log n)의 실행시간을 제공합니다.

3. 각 항목에 대한 접근빈도가 불균등한 사전에 사용하면 유리합니다.

( locality의 개념을 생각하시면 되겠습니다. )

스플레이 하는 시점

1. 탐색 

- 키가 발견되면, 그 노드를 스플레이

- 발견되지 않으면, 실패한 외부노드의 부모노드를 스플레이

2. 삽입

- 새로 삽입한 노드를 스플레이

3. 삭제

- 삭제된 내부노드의 부모노드를 스플레이

스플레이 방법

노드의 회전을 통하여 올라갑니다.

역시 전, 외워서 하는 것보다 그냥 머리 굴리는게 더 편해요..

코드로 보여드리도록 하겠습니다.

성능

최악실행시간은 O(h) 입니다. (h는 트리의 높이)

하지만, 상각의 관점에서 보면 삽입, 삭제, 탐색 모두 O(log n)의 시간을 갖습니다.

AVL 트리와 일치하지만, AVL 트리에 비해 구현이 쉽죠. 트리 개조의 불편함도 적구요.

그리고 locality의 측면에서 특정 항목에 대한 접근은 더욱 적은 시간을 갖겠죠?

즉, 스플레이 트리의 핵심은 각 항목에 접근되는 빈도에 "적응"을 할 수 있다는 점입니다.