Membuat Fungsi Search untuk Binary Search Tree

Seperti yang sudah dibahas pada awal tutorial, binary search tree memiliki aturan kaki kiri < dari parent, dan kaki kanan > parent.

Mari kita buat fungsi untuk melakukan search dengan menambahkanya pada class Node.

def search(self, target):
    if self.data == target:
        print("Node found")
        return self
    
    if self.left and self.data > target:
        return self.left.search(target)

    if self.right and self.data < target:
        return self.right.search(target)

    print("No Node Found")

Pembahasan Code

Fungsi search akan menerima parameter target.

Jika data dari node sama dengan target, fungsi akan melakukan print dan mengembalikan node tersebut. Jika data tidak sama dengan target, maka akan dilakukan pencarian dengan menggunakan rule binary search tree.

Pertama kita periksa apakah node memiliki kaki kiri dan datanya lebih besar dari target (ingat rule BST kaki kiri harus lebih kecil dari parent). Jika kondisi dipenuhi lakukan pencarian dengan memanggil fungsi search.

Lakukan hal yang sama untuk kaki kanan, perbedaanya adalah data dari kaki kanan harus lebih kecil dari target. Jika kondisi dipenuhi, lakukan pencarian dengan memanggil fungsi search.

Terakhir kita lakukan print kelayar jika target tidak ditemukan.

Kita bisa tambahkan fungsi search pada class Tree hingga lebih memudahkan kita dalam memanggil fungsi search.

def search(self, target):
    return self.root.search(target)

Berikut isi lengkap dari program tree yang sudah ditambahkan fungsi search.

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
    
    def search(self, target):
        if self.data == target:
            print("Node found")
            return self
        
        if self.left and self.data > target:
            return self.left.search(target)

        if self.right and self.data < target:
            return self.right.search(target)

        print("No Node Found")

class Tree:
    def __init__(self, root, name=''):
        self.root = root
        self.name = name

    def search(self, target):
        return self.root.search(target)

node = Node(10)

node.left = Node(5)
node.right = Node(15)

node.left.left = Node(3)
node.left.right = Node(6)

node.right.left = Node(12)
node.right.right = Node(30)

myTree = Tree(node, 'Basic BST')

found = myTree.search(30)
if found:
    print(found.data)

$ python tree.py
Node found
3

Jika kita jalankan program diatas maka fungsi search berhasil menemukan node dengan value 3.