import numpy as np
import graphviz as gvModul 9a Struktur Data: A-B Tree dan variasinya (B-Tree, 2-3 Tree, dsb)
Kembali ke Struktur Data (dengan Python)
(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 konsistenclass 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):
passB-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")