Splay Tree Menggunakan Python

Pendahuluan

Splay Tree adalah binary search tree dengan fitur tambahan yaitu recently accessed node untuk mempercepat akses.

Untuk tutorial binary search tree, dapat lihat disini https://skillplus.web.id/binary-search-tree-menggunakan-python/

Operasi pada splay tree umumnya memerlukan O(logN) time complexity, namun beberapa operasi dapat menjadi lambat karena splay tree tidak mewajibkan tree balance.

Keuntungan dengan tidak mewajibkan balance, lebih cepat dan mudah dalam implementasi. (Perhatian, bukan lebih cepat dalam melakukan operasi search, insert dan remove node).

Walaupun splay tree tetap akan melakukan balancing, namun tidak sesering tipe tree lainnya. Untuk melakukan balancing digunakan operasi rotations.

Recently accessed node disimpan dekat root node. Pengaturan topology ini dilakukan dengan operasi rotations.

Operasi rotation terdapat dua macam, yaitu left dan right rotation, beberpa point penting mengenai proses rotation:

• prose update reference pada node yang memerlukan waktu O(1).
• tidak akan merubah aturan parent-child relationships.
• in-order traversal tetap sama setelah proses rotasi.

Untuk proses search sama dengan binary search tree, artinya jika mencari item dengan value lebih kecil ke kaki kiri, jika lebih besar ke kaki kanan.

Proses search bisa memakan waktu O(N) jika splay tree tidak balance, dan hal ini mungkin terjadi.

Splaying (Rotation).

Splaying adalah proses rotasi dengan tujuan mengatur recently node menjadi root.

Perhatian, tujuan dari splaying bukan untuk membuat tree menjadi balance. Namun memastikan next search dapat dilakukan dengan cepat.

Terdapat 3 operasi splaying:

1. Zig-Zag situations
2. Zig-Zig situations
3. Zig situations

Zig-Zag situations

Node x (node yang dicari atau diinsert) adalah right-child dari left-child atau left-child dari right-child.

Situasi ini adalah left-right heavy (atau right-left heavy), artinya kita harus melakukan 2 rotasi (left dan right). Berikut contoh melakukan rotasi pada right-child dari left-child.

Zig-Zig Situations

node x adalah left-child dari left-child, atau right-child dari right-child, atau sering disebut doubly left atau right heavy case.

Berikut contoh proses rotasi pada left-child dari left-child.

Zig Situations

Pada zig situations, perlu dilakukan proses zig-zig dan zig-zag, sampai mencapai root node. Namun kondisi zig ini juga kadang cukup dilakukan satu kali rotasi (left atau right), root node sudah bisa dicapai.

Berikut contoh melakukan right rotation pada parent node.

Berikut table running time complexity dari splay tree

	Average-Case	Worst-Case
space complexity	O(N)	O(N)
insertion	O(logN)	O(N)
deletion	O(logN)	O(N)
search	O(logN)	O(N)

Implementasi Splay Tree Menggunakan Python

class Node:

    def __init__(self, data, parent):
        self.data = data
        self.parent = parent
        self.left_node = None
        self.right_node = None


class SplayTree:

    def __init__(self):
        self.root = None

    # it is exactly the same as BST
    def insert(self, data):
        if self.root is None:
            self.root = Node(data, None)
        else:
            self.insert_node(data, self.root)

    # BST insertion
    def insert_node(self, data, node):
        if data < node.data:
            if node.left_node:
                self.insert_node(data, node.left_node)
            else:
                node.left_node = Node(data, node)
        else:
            if node.right_node:
                self.insert_node(data, node.right_node)
            else:
                node.right_node = Node(data, node)

    # find a given arbitrary item in the BST
    def find(self, data):

        node = self.root

        while node is not None:
            if data < node.data:
                node = node.left_node
            elif data > node.data:
                node = node.right_node
            else:
                self.splay(node)
                return node.data

    def splay(self, node):

        # while we hit the root node - this is how we make the node
        # to be the root node (caches)
        while node.parent is not None:
            # the node is a left or right child of the root
            # CASE 3 - ZIG SITUATION
            if node.parent.parent is None:
                if node == node.parent.left_node:
                    self.rotate_right(node.parent)
                else:
                    self.rotate_left(node.parent)
            # doubly left heavy case ZIG-ZIG SITUATION
            elif node == node.parent.left_node and node.parent == node.parent.parent.left_node:
                self.rotate_right(node.parent.parent)
                self.rotate_right(node.parent)
            elif node == node.parent.right_node and node.parent == node.parent.parent.right_node:
                self.rotate_left(node.parent.parent)
                self.rotate_left(node.parent)
            # ZIG-ZAG SITUATIONS
            elif node == node.parent.left_node and node.parent == node.parent.parent.right_node:
                self.rotate_right(node.parent)
                self.rotate_left(node.parent)
            else:
                self.rotate_left(node.parent)
                self.rotate_right(node.parent)

    def rotate_right(self, node):

        temp_left_node = node.left_node
        t = temp_left_node.right_node

        temp_left_node.right_node = node
        node.left_node = t

        if t is not None:
            t.parent = node

        temp_parent = node.parent
        node.parent = temp_left_node
        temp_left_node.parent = temp_parent

        if temp_left_node.parent is not None and temp_left_node.parent.left_node == node:
            temp_left_node.parent.left_node = temp_left_node

        if temp_left_node.parent is not None and temp_left_node.parent.right_node == node:
            temp_left_node.parent.right_node = temp_left_node

        if node == self.root:
            self.root = temp_left_node

    def rotate_left(self, node):

        temp_right_node = node.right_node
        t = temp_right_node.left_node

        temp_right_node.left_node = node
        node.right_node = t

        if t is not None:
            t.parent = node

        temp_parent = node.parent
        node.parent = temp_right_node
        temp_right_node.parent = temp_parent

        if temp_right_node.parent is not None and temp_right_node.parent.left_node == node:
            temp_right_node.parent.left_node = temp_right_node

        if temp_right_node.parent is not None and temp_right_node.parent.right_node == node:
            temp_right_node.parent.right_node = temp_right_node

        if node == self.root:
            self.root = temp_right_node


if __name__ == '__main__':

    splay_tree = SplayTree()
    splay_tree.insert(10)
    splay_tree.insert(8)
    splay_tree.insert(3)
    splay_tree.insert(7)

    splay_tree.find(7)
    splay_tree.find(3)
    splay_tree.find(8)
    splay_tree.find(3)
    print(splay_tree.root.data)

Aplikasi Splay Tree

Berikut beberapa conto aplikasi Splay Tree:

• Cache, yaitu component yang bertujuan untuk meyimpan data dan cepat diakses.
• Garbage collector, process otomatis yang berfungsi untuk menghapus penggunaan memory yang sudah tidak digunakan.
• IP Routing, network router menangani frekuensi packet data yang tinggi. Oleh karena perlu cepat dalam memutuskan packet tersebut akan dikirim ke network yang dituju berdasarkan IP Address. IP Address yang pernah digunakan, umumnya akan lebih sering digunakan dikemudian hari.