Modul 9a Struktur Data: A-B Tree dan variasinya (B-Tree, 2-3 Tree, dsb)

Kembali ke Struktur Data (dengan Python)

import numpy as np
import graphviz as gv

(TODO) Implementasi A-B Tree dengan pointer

A-B Tree, terkadang disebut \((a,b)\)-tree di mana \(a, b \in \mathbb{Z}\) dengan \(2 \le a \le \frac{b+1}{2}\), adalah sejenis tree yang memenuhi sifat-sifat berikut:

Tiap node bisa menyimpan sejumlah key (atau data), maksimal sebanyak \((b-1)\)
Root (kalau tidak kosong) menyimpan minimal satu key
Semua node selain root menyimpan sejumlah key, minimal sebanyak \((a-1)\)
Tiap node bisa memiliki sejumlah child, maksimal sebanyak \(b\)
Root diharapkan memiliki minimal dua child
Tiap internal node (yaitu selain leaf dan root) memiliki sejumlah child, minimal sebanyak \(a\)
Semua leaf node ada di level yang sama

class ABtreeNode:
    def __init__(self, b, key_dtype=object, emptydata=None):
        self.keys = np.empty(b-1, dtype=key_dtype)
        self.children = np.empty(b, dtype=ABtreeNode) # menyimpan pointer
        self.emptydata = emptydata
        self.clear_keys()
        self.clear_children()

    def clear_keys(self):
        for i in range(len(self.keys)):
            self.keys[i] = self.emptydata
    
    def clear_children(self):
        for i in range(len(self.children)):
            self.children[i] = None

    def is_key_idx_empty(self, idx):
        if self.keys[idx] == self.emptydata:
            return True
        else:
            return False
    
    def is_children_idx_empty(self, idx):
        if self.children[idx] == None:
            return True
        else:
            return False

    def is_full_keys(self):
        # jika key terakhir tidak kosong, maka keys sudah penuh
        return ( not self.is_key_idx_empty(len(self.children)-1) )

    def is_leaf(self):
        # jika pointer pertama saja sudah kosong, berarti tidak punya child
        return self.is_children_idx_empty(0)

    def get_nonempty_keys_amount(self):
        all_keys_amount = len(self.keys)
        n = 0
        while (n < all_keys_amount) and (not self.is_key_idx_empty(n)):
            n += 1
        return n
    
    # method ini sebaiknya hanya digunakan pada leaf node
    def insert_key_get_carry(self, newkey, right_biased=False):
        carry = self.emptydata
        if self.is_full_keys():
            n = len(self.keys)

            # cari indeks yang layak untuk menyisipkan newkey
            newkey_idx = 0
            while ((newkey_idx < n) and
                   (self.keys[newkey_idx] < newkey)):
                newkey_idx += 1
            
            # seandainya newkey sudah disisipkan, tentukan indeks dari median
            med_idx = n/2
            if (not right_biased):
                med_idx = int(np.floor(med_idx))
            else:
                med_idx = int(np.ceil(med_idx))
            
            # lakukan penyisipan sekaligus menentukan elemen carry (buangan)
            if (med_idx < newkey_idx):
                carry = self.keys[med_idx] # ambil elemen buangan
                for i in range(med_idx, newkey_idx): # geser elemen array
                    self.keys[i] = self.keys[i+1]
                self.keys[newkey_idx] = newkey # sisipkan
            elif (med_idx == newkey_idx):
                carry = newkey
                # ternyata yang akan disisipkan ialah yang akan menjadi buangan
                # sehingga array keys tidak perlu dimodifikasi
            else: # med_idx > newkey_idx
                carry = self.keys[med_idx] # ambil elemen buangan
                for i in range(med_idx, newkey_idx, -1): # geser elemen array
                    self.keys[i] = self.keys[i-1]
                self.keys[newkey_idx] = newkey # sisipkan
            return carry
        # jika array keys tidak penuh
        n = self.get_nonempty_keys_amount()
        self.keys[n] = newkey
        # sekali bubble sort dari kanan ke kiri
        i = n
        while (i > 0) and (self.keys[i-1] > self.keys[i]):
            # tukar
            temp = self.keys[i-1]
            self.keys[i-1] = self.keys[i]
            self.keys[i] = temp
            # lanjut ke elemen sebelah kirinya
            i -= 1
        return carry # sebenarnya self.emptydata, tapi gapapa biar konsisten

class LinkedABtree:
    def __init__(self, a, b, key_dtype=object, emptydata=None):
        self.root = None
        self.a = a
        self.b = b
        self.key_dtype = key_dtype
        self.emptydata = emptydata
    
    def is_empty(self):
        if self.root == None:
            return True
        else:
            return False
    
    def search(self, x):
        if self.is_empty():
            print("Error search: tree kosong")
            return None
        temp = self.root
        i = 0
        n = temp.get_nonempty_keys_amount()
        while (temp != None):
            if (self.keys[i] == x):
                return x
            elif (i == 0 and x < self.keys[i]):
                temp = temp.children[0]
                i = 0
                if (temp != None):
                    n = temp.get_nonempty_keys_amount()
            elif (i == n-1) or (self.keys[i] < x and x < self.keys[i+1]):
                temp = temp.children[i+1]
                i = 0
                if (temp != None):
                    n = temp.get_nonempty_keys_amount()
            else:
                i += 1
        # tidak ditemukan
        return None

    def split_node(self, node, newkey, right_biased=False):
        old_n = node.get_nonempty_keys_amount()
        new_n = old_n + 1
        med_idx = (old_n)/2 # indeks untuk median
        if (not right_biased): # teknik left-biased
            med_idx = int(np.floor(med_idx))
        else: # teknik right-biased
            med_idx = int(np.ceil(med_idx))
        
        old_keys = node.keys
        old_children = node.children
        node.clear_keys()
        node.clear_children()

        left_child = ABtreeNode(b=self.b, key_dtype=self.key_dtype,
                                emptydata=self.emptydata)
        right_child = ABtreeNode(b=self.b, key_dtype=self.key_dtype,
                                 emptydata=self.emptydata)
        
        newkey_idx = 0
        while newkey_idx < len(old_keys):
            if (old_keys[i] < newkey_idx):
                newkey_idx += 1
        new_keys = list(old_keys)
        new_keys.insert(newkey_idx, newkey)
        # sisipkan newkey di indeks newkey_idx

        i = 0
        while (i < med_idx): # hingga sebelum posisi median
            left_child.keys[i] = new_keys[i]
            i += 1
        node.keys[0] = new_keys[i] # khusus median, di root
        i += 1
        while (i < new_n): # sisanya
            right_child.keys[i-med_idx-1] = new_keys[i]
            i += 1
        
        i = 0
        while (i < med_idx+1): # hingga pointer di sebelah kiri key median
            left_child.children[i] = old_children[i]
            i += 1
        while (i < old_n+1): # banyaknya pointer = (banyaknya key) + 1
            right_child.children[i-med_idx-1] = old_children[i]
            i += 1
        
        node.children[0] = left_child
        node.children[1] = right_child
        return node

    def insert(self, newkey, right_biased=False):
        if self.search(newkey) == None:
            self.root = self.insert_rec(newkey, right_biased=right_biased,
                                        current=self.root)
        else:
            print("Error insert: key sudah ada di tree, yaitu", newkey)
    def insert_rec(self, newkey, right_biased, current):
        if current == None:
            newnode = ABtreeNode(b=self.b, key_dtype=self.key_dtype,
                                 emptydata=self.emptydata)
            newnode.keys[0] = newkey
            return newnode
        
        # variabel untuk menyimpan key "buangan" dari child node
        # (dan key buangan itu nantinya akan dicoba dimasukkan ke keys)
        # sementara kita buat "kosong" dulu karena belum ada buangan
        carry = self.emptydata

        n = current.get_nonempty_keys_amount()
        if (not current.is_leaf()): # jika bukan leaf, akan lanjut ke child nya
            if (newkey < self.keys[0]):
                current.children[0] = self.insert_rec(
                    newkey, right_biased=right_biased,
                    current=current.children[0]
                    )
            else:
                for i in range(n):
                    if ((i == n-1) or
                        (self.keys[i] < newkey and newkey < self.keys[i+1])):
                        current.children[i+1] = self.insert_rec(
                            newkey, right_biased=right_biased, 
                            current=current.children[i+1]
                            )
                        break
        # selain itu, jika current adalah leaf node
        elif current.is_full_keys(): # jika current penuh, split
            left_child, right_child, carry = self.split_node(
                node=current, newkey=newkey, right_biased=right_biased
            )
            newkey_idx = current.try_insert_key(carry)
            carry = None
        else: # jika current (sebagai leaf node) tidak penuh
            current.try_insert_key(newkey)
        
        return current

    def delete(self, x):
        pass

B-Tree sebagai kasus khusus dari A-B Tree

B-Tree, berorder misalnya m, adalah sejenis A-B Tree atau \((a,b)\)-tree dengan

\[b=m\] \[a = \left\lceil \frac{b}{2} \right\rceil = \left\lceil \frac{m}{2} \right\rceil\]

Sehingga, untuk implementasi B-Tree, kita tinggal meng-inherit dari LinkedABtree dan memilih nilai a dan b yang sesuai berdasarkan nilai m yang diberikan.

class LinkedBtree(LinkedABtree):
    def __init__(self, m):
        self.b = m
        self.a = int(np.ceil(m/2))
    
    def get_m(self):
        return self.b

    def set_m(self, new_m):
        self.b = new_m
        self.a = int(np.ceil(new_m/2))

Variasi B-Tree

2-3 Tree

2-3 Tree adalah suatu B-Tree dengan \(m=3\).

(Lebih umumnya, 2-3 Tree atau \((2,3)\)-tree adalah suatu A-B Tree dengan \(a=2\) dan \(b=3\).)

class Linked23Tree(LinkedBtree):
    def __init__(self):
        super().__init__(m=3)
    
    # nonaktifkan fitur memasang nilai m dari LinkedBtree
    def set_m(self, new_m):
        print("Error 2-3 Tree: nilai m=3 tidak boleh diubah")

2-4 Tree

2-4 Tree, terkadang juga disebut 2-3-4 Tree, adalah suatu B-Tree dengan \(m=4\).

(Lebih umumnya, 2-4 Tree atau \((2,4)\)-tree adalah suatu A-B Tree dengan \(a=2\) dan \(b=4\).)

class Linked24Tree(LinkedBtree):
    def __init__(self):
        super().__init__(m=4)
    
    # nonaktifkan fitur memasang nilai m dari LinkedBtree
    def set_m(self, new_m):
        print("Error 2-4 Tree: nilai m=4 tidak boleh diubah")