Binary Search Tree

Materi Data Structure 17 Maret 2020

Hal yang akan dibahas pada pertemuan kali ini yaitu :
1. Binary Search Tree
2. Binary Search Tree Operations

1. Binary Search Tree

    Binary Search Tree adalah salah satu struktur data yang mendukung pencarian lebih cepat, penyortiran cepat, dan penyisipan dan penghapusan yang mudah.

    Binary Search Tree juga sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang disimpan di dalam memory.

Aturan main Binary Search Tree adalah :
- Setiap child node sebelah kiri harus lebih kecil nilainya daripada root nodenya
- Setiap child node sebelah kanan harus lebih besar nilainya daripada root nodenya.

berikut  gambaran contoh dari Binary Search Tree

Kenapa harus membedakan kiri dan kanan sesuai besaran nilainya? Tujuannya untuk memberikan efisiensi terhadap proses searching. Kalau struktur data tree sudah tersusun rapi sesuai aturan mainnya, proses search akan lebih cepat.

2. Binary Search Tree Operations

Terdapat 3 operasi dalam Binary Search Tree yaitu :

1. Search

Dengan properti bahwa semua nilai lebih kecil dari root node terletak disebelah kiri dan semua nilai yang lebih besar dari root node terletak disebelah kanan membantu untuk pencarian dalam waktu yang cepat (dengan anggapan h adalah ketinggian tree)

Misalkan kita berada pada satu simpul dan nilai yang ingin dicari lebih kecil dari nilai simpul itu. Dalam hal ini, kita akan mencari di subtree kiri.

contoh:

Jadi fungsi kita akan mengambil elemen yang akan dicari (x) dan pohon (T)yaitu : SEARCH(x,T)

dan kita akan melakukan pencarian jika root of the tree tidak NULL, if (T.root!=NULL)

langkah-langkahnya yaitu :

1. pertama kita cek terlebih dahulu apakah data yang akan dicari berada di root atau tidak. jika sudah di root, maka kita akan mengembalikannya

2. jika bukan, maka kita akan mencari di subtree kiri jika nilai yang akan dicari lebih kecil dari pada root. atau kita akan mecrai di subtree sebelah kanan jika nilai yang akan dicari lebih besar dari pada root.

gambaran codingannya :

SEARCH(x, T)
    if(T.root != null)
        if(T.root.data == x)
            return r
        else if(T.root.data > x)
            return SEARCH(x, T.root.left)
        else
            return SEARCH(x, T.root.right)

2. Insertion

contoh insertion

Langkah-langkah untuk insertion sbb :

Pertama-tama kita akan mencari elemen itu dan jika elemen itu tidak ditemukan, maka kita akan memasukkannya. 

Lalu kita akan menggunakan pointer sementara dan pergi ke tempat node akan dimasukkan.

Kita perlu membuat simpul terakhir dalam iterasi diatas sebagai induk dari simpul baru. jadi kita perlu menggunakan variabel baru

kita telah menggunakan variabel y. ketika tree tidak memiliki simpul, simpul baru akan manjadi root dari tree dan parentnya akan NULL. jadi awalnya nilai y adalah NULL. Jika tidak y akan menunjuk pada simpul terakhir.

setelah ini kita akan menjadikan y sebagai induk dari simpul baru

Terakhir, kita perlu membuat simpul baru anak y. jika y adalah NULL, simpul baru akan menjadi akar dari pohon, jika tidak kita akan memeriksa apakah lebih besar atau lebih kecil dari data y, dan karenanya kita akan membuatnya menjadi kiri atau the right child

gambaran codingannya :

INSERT(T, n)
    temp = T.root
    y = NULL
    while temp != NULL
        y = temp
        if n.data < temp.data
            temp = temp.left
        else
            temp = temp.right
    n.parent = y
    if y==NULL
        T.root = n
    else if n.data < y.data
        y.left = n
    else
        y.right = n

3. Deletion

dalam tahap deletion kita perlu memerhatikan 3 hal yaitu :

1. jika key berada di leaf, maka kita hanya perlu menghapus node tersebut

2. jika key ada di simpul yang memiliki 1 child, hapus simpul tersebut dan sambungkan childnya ke parentnya.

3. jika key ada di simpul yang memiliki 2 child, mkaa temukan child paling kanan dari sub tree kirinya(simpul P), ganti keynya dengan key p dan hapus p secara rekursif

NAMA : Timothy Gilbert
NIM : 2301851036
Kelas Besar : CB01
Kelas Kecil : LK01

sumber :

https://www.codesdope.com/course/data-structures-binary-search-trees/