{"id":628,"date":"2026-07-14T14:41:02","date_gmt":"2026-07-14T14:41:02","guid":{"rendered":"https:\/\/socs.binus.ac.id\/computer-science\/?p=628"},"modified":"2026-07-14T14:46:06","modified_gmt":"2026-07-14T14:46:06","slug":"mengenal-splay-tree","status":"publish","type":"post","link":"https:\/\/socs.binus.ac.id\/computer-science\/2026\/07\/14\/mengenal-splay-tree\/","title":{"rendered":"Mengenal Splay Tree"},"content":{"rendered":"

Dalam\u00a0dunia\u00a0struktur\u00a0data,\u00a0kita\u00a0tidak\u00a0asing\u00a0dengan\u00a0Self Balancing<\/em><\/span>\u00a0<\/em>Binary Search Tree<\/em> (BST),\u00a0seperti\u00a0AVL Tree<\/strong>\u00a0atau\u00a0Red-Black Tree <\/strong>karena kinerjanya yang baik dalam operasi <\/span>search, insert <\/span><\/i>dan\u00a0<\/span>delete<\/span><\/i>.\u00a0Namun,\u00a0bagaimana\u00a0jika\u00a0kita\u00a0hanya\u00a0mengakses\u00a0value<\/em> tertentu dan value <\/em>tersebut ada di bagian leaf<\/em>?\u00a0Untuk\u00a0menangani\u00a0kasus\u00a0seperti\u00a0ini, Splay<\/em> Tree<\/em>\u00a0dapat\u00a0menjadi\u00a0solusi\u00a0karena\u00a0kemampuan\u00a0<\/span>self adjusting <\/span><\/i>nya sesuai dengan value\/key <\/em>yang sering kita akses.<\/span>\u00a0<\/span><\/p>\n

Kenapa\u00a0Splay Tree?<\/span><\/b>\u00a0<\/span><\/p>\n

Splay Tree<\/strong>\u00a0merupakan\u00a0BST yang\u00a0memiliki\u00a0kemampuan\u00a0<\/span>self adjusting <\/span><\/i>yang artinya tree<\/em> ini secara otomatis akan menyesuaikan strukturnya setiap kali dilakukan operasi <\/span>search<\/span><\/i>,\u00a0<\/span>insert<\/span><\/i>, dan\u00a0<\/span>delete<\/span><\/i>. Setiap kali sebuah node diakses, node tersebut akan dipindahkan ke root<\/em> melalui proses yang disebut <\/span>splaying<\/span><\/i>. 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<\/em> yang lain, Splay Tree<\/em> merupakan <\/span>optimal<\/span><\/i>\u00a0BST\u00a0bukan\u00a0<\/span>balance<\/span><\/i>\u00a0BST.\u00a0<\/span>\u00a0<\/span><\/p>\n

\u00a0<\/span>Splaying<\/span><\/b>\u00a0<\/span><\/p>\n

Setiap\u00a0operasi\u00a0pada Splay Tree<\/em>\u00a0seperti\u00a0<\/span>search, insert <\/span><\/i>dan\u00a0<\/span>delete<\/span><\/i>\u00a0akan\u00a0dilakukan\u00a0proses splaying<\/em>. Berikut adalah tiga rotasi dasar dalam proses splaying<\/em>:<\/span>\u00a0<\/span><\/p>\n

    \n
  1. Zig<\/span>\u00a0<\/span><\/li>\n<\/ol>\n

    Digunakan\u00a0ketika\u00a0node yang\u00a0diakses\u00a0adalah\u00a0<\/span>child<\/span><\/i>\u00a0langsung\u00a0dari\u00a0root<\/em>.\u00a0Cukup\u00a0lakukan\u00a0satu\u00a0rotasi.<\/span>\u00a0<\/span><\/p>\n

    \"\"<\/span><\/p>\n

    2. Zig-Zig<\/span>\u00a0<\/span><\/p>\n

    Digunakan ketika node dan parent<\/em>-nya adalah left\/right child<\/em> dari grandparent<\/em>-nya. Dua rotasi ke arah yang sama dilakukan.<\/span>\u00a0<\/span><\/p>\n

    \"\"<\/span>3. Zig-Zag<\/span>\u00a0<\/span><\/p>\n

    Digunakan\u00a0ketika\u00a0node\u00a0adalah\u00a0left child\u00a0<\/em>dari\u00a0parent<\/em>\u00a0yang\u00a0merupakan\u00a0right child<\/em> dari\u00a0grandparent<\/em>, atau sebaliknya dua rotasi ke arah berlawanan dilakukan.<\/span>\u00a0<\/span><\/p>\n

    \"\"<\/p>\n

    Operasi\u00a0Lainnya<\/span><\/b>\u00a0<\/span><\/p>\n