Implementasi Algoritma Binary Search Tree Pada Python

Binary Search Tree adalah tree yang terurut (ordered Binary Tree). Nama lain dari Binary Search Tree adalah Sorted Binary Tree. Data dibentuk seperti pohon. Peletakan data menggunakan konsep sebagai berikut.

  • Apabila data lebih kecil dari root nya maka data diletakkan disebelah kirinya.
  • Apabila data lebih besar dari root nya maka data diletakkan disebelah kirinya.

Algoritma ini bisa digunakan sebagai metode pengurutan dan pencarian

Data dan Pohon

Misalkan kita memiliki data tidak terurut data = [4, 6, 2, 1, 5, 7, 3]. Maka angka 4 akan menjadi root utamanya. Angka ke 2 yaitu 6 akan di cek apakah lebih besar atau lebih kecil dari 4? Karena lebih besar maka diletakkan di bawah sebelah kanan angka 4. Angka ke 3 yaitu 2 karena lebih kecil maka akan diletakkan di bawah sebelah kiri dari angka 4. Begitu seterusnya maka diagram pohon yang terbentuk seperti pada gambar dibawah ini.

Diagram Pohon yang terbentuk.


Kode Program

Pada kode program akan terdiri dari 2 class yaitu class Tree dan class Node. Class Node mempunyai struktur root, left, right, sedangkan class Tree berisi class Node.

from random import randint

# membuat objek Tree
class Tree(object):
    def __init__(self):
        self.root = None

    # fungsi menambahkan node pada objek tree
    def addValue(self,val):
        n = Node(val)
        if(self.root == None):
            self.root = n
        else:
            self.root.addNode(n)
    
    def traverse(self):
        self.root.visit()

    def search(self, val):
        found = self.root.search(val)
        return found

class Node(object):
    def __init__(self, val):
        self.value = val
        self.left = None
        self.right = None

    def addNode(self,n):
        if(n.value < self.value):
            if(self.left == None):
                self.left = n
            else:
                self.left.addNode(n)
        elif (n.value > self.value):
            if(self.right == None):
                self.right = n
            else:
                self.right.addNode(n)
    
    def visit(self):
        if(self.left != None):
            self.left.visit()
        print(self.value, end = " ")
        if(self.right != None):
            self.right.visit()

    def search(self, val):
        if(self.value == val):
            return self
        elif (val < self.value and self.left != None):
            return self.left.search(val)
        elif (val > self.value and self.right != None):
            return self.right.search(val)

tree = Tree()
print("Data: ")
for k in range(1,10):
    data = randint(1, 100)
    print(data, end=" ")
    tree.addValue(data)

print("\nRoot:\n" +  str(tree.root.value))

print("Tranverse: ")
tree.traverse()

searching = int(input("\nCari Data : "))
result = tree.search(searching)
if(result == None):
    print("Not Found")
else:
    print("Found")

Keluaran Program

Berikut ini keluaran dari program

Data:
92 95 44 29 52 4 20 16 77
Root:
92
Tranverse:
4 16 20 29 44 52 77 92 95
Cari Data : 52
Found

Be the first to comment

Leave a Reply

Your email address will not be published.


*