Dalam dunia struktur data, kita tidak asing dengan Self Balancing Binary Search Tree (BST), seperti AVL Tree atau Red-Black Tree karena kinerjanya yang baik dalam operasi search, insert dan delete. Namun, bagaimana jika kita hanya mengakses value tertentu dan value tersebut ada di bagian leaf? Untuk menangani kasus seperti ini, Splay Tree dapat menjadi solusi karena kemampuan self adjusting nya sesuai dengan value/key yang sering kita akses. 

Kenapa Splay Tree? 

Splay Tree merupakan BST yang memiliki kemampuan self adjusting yang artinya tree ini secara otomatis akan menyesuaikan strukturnya setiap kali dilakukan operasi search, insert, dan delete. Setiap kali sebuah node diakses, node tersebut akan dipindahkan ke root melalui proses yang disebut splaying. Konsep ini pertama kali diperkenalkan oleh Daniel Sleator dan Robert Tarjan pada tahun 1983, dengan tujuan untuk mendekati performa optimal BST secara dinamis, bahkan ketika frekuensi akses tidak diketahui di awal. Berbeda dengan tree yang lain, Splay Tree merupakan optimal BST bukan balance BST.  

 Splaying 

Setiap operasi pada Splay Tree seperti search, insert dan delete akan dilakukan proses splaying. Berikut adalah tiga rotasi dasar dalam proses splaying: 

  1. Zig 

Digunakan ketika node yang diakses adalah child langsung dari root. Cukup lakukan satu rotasi. 

2. Zig-Zig 

Digunakan ketika node dan parent-nya adalah left/right child dari grandparent-nya. Dua rotasi ke arah yang sama dilakukan. 

3. Zig-Zag 

Digunakan ketika node adalah left child dari parent yang merupakan right child dari grandparent, atau sebaliknya dua rotasi ke arah berlawanan dilakukan. 

Operasi Lainnya 

  • Join: menggabungkan dua subtree T₁ dan T₂ di mana semua elemen di T₁ < elemen di T₂. Caranya dengan men-splay elemen terbesar di T₁ lalu menjadikan T₂ sebagai anak kanannya. 
  • Split: membagi tree menjadi dua subbagian berdasarkan key/value tertentu. 
  • Delete: men-splay elemen yang ingin dihapus ke root, lalu menggabungkan dua subtree yang tersisa. 

Visualisasi selengkapnya dapat dicoba pada website berikut: https://www.cs.usfca.edu/~galles/visualization/SplayTree.html 

 

Referensi: 

  1. Design and Analysis of Algorithms, Chapter 10
  2. Data structures using C, Chapter 11
  3. Splay Tree Visualization, https://www.cs.usfca.edu/~galles/visualization/SplayTree.html 
  4. Splay Tree, https://web.stanford.edu/class/archive/cs/cs166/cs166.1146/lectures/08/Small08.pdf