Binary Search Tree dengan Golang

Binary Search Tree

Hi BroDev disini saya akan mengulas sedikit tentang binary search tree implementasi menggunakan Golang.

Binary search tree menggunakan konsep akar pohon, akar yg bercabang kebawah dinamakan sebagai(child) akar yg memiliki cabang dinamakan (parent) dari child dibawahnya. atau istilah umum biasa menggunakan node(parent) dan node(child). Nilai child disebelah kanan selalu memiliki nilai yang lebih besar dibandingkan parent dan left childnya. Pencarian akan sangat optimal jika kondisi tree dalam keadaan berimbang.

Pros
1. Ukuran flexible
2. Terurut
3. Operasi (n)
Cons
1. Tidak memiliki opearsi dengan O(1)

Binary search tree memiliki 3 operasi:

Cari membutuhkan operasi O(log n) karenasudah terurut berbeda dengan array membutuhkan operasi O(n)
Insert membutuhkan operasi O(log n) berbeda dengan array membutuhakn operasi O(1) jika diinputkan ke akhir index tpi O(n) jika array digeset ke index tertentu.
Delete membutuhakn operasi O(log n)

Seperti yang kita liat dari gambar diatas, bst me miliki performa yang sangat bagus denga O(log n) denagan kondisi berimbang, jika kondisi tidak berimbang maka membutuhkan operasi O(n)

Operasi

Seperti gambar diatas binary search tree dengan kondisi tidak berimbang membutuhkan operasi seperti pada linkedlist.

Sebelum kita membuat sebuah tree kita membutuhkan 2 structs. pertama adalah Node yg merepresentasikan sebuah element. Setiap node memiliki 2 ch ild kiri dan kanan. struct kedua untuk menyimpan root node.

type Node struct{
    Left, Right *Node
    Value int
}
type BinaryTree struct{
    Root *Node
}

Insert

Insert adalah sebuah operasi menambahkan node baru kedalam tree. untuk proses insert perlu melakukan pengecekan nila. jika nilai kurang dari node saat ini maka taruh ke kiri child jika sebaliknya taruh ke kanan child. ulangi langkah tersebut sampai menemukan nilai null.

berikut contoh kode implementasinya:

func (b *BinaryTree) insert(value int) {
    n := &Node{
        Value: value,
    }
    if b.Root = nil {
        b.Root = n
        return
    }

    curr := b.Root

    for curr != nil {
        if curr.Value == value{
            fmt.Println("Same Value")
            break
        }

        if n.Value <curr.Value {
            if curr.Left == nil {
                curr.Left = n
                break
            }
            curr = curr.Left
        }else {
            if curr.Right == nil {
                curr.Right = n
                break
            }
            curr = curr.Right
        }
    }
}

Pencarian

pencarian adalah sebuah operasi menemukan nilai spesifik didalam tree. operasinya hampir sama seperti operasi insert. kita harus mengecek nilai yang ingin kita cari, jika nilai memiliki angka kurang dari node saat ini maka geser ke posisi child left, dan sebaliknya.

berikut untuk kode implementasinya:

func (b *BinaryTree) cari(value int) {
    if b.Root.Right == nil && b.Root.Left == nil {
        fmt.Println("Value found ", b.Root.Value == value, b.Root)
    }
    curr := b.Root
    found := false

    for curr != nil {
        if curr.Value == value{
            found = true
            break
        }
        if value < curr.Value {
            curr = curr.Left
        }else {
            curr = curr.Right
        }
    }
    if curr != nil && curr.Value == value {
        fmt.Println(value, "-", found, "Left", curr.Left, "Right", curr.Right)
    }else {
        fmt.Println(value, "-", found)
    }
}

Delete

Delete adalah sebuah operasi menghapus 1 node didalam sebuah tree.

dari animasi diatas, seperti yang kita liat jika kita ingin menghapus angka 62, we harus melakukan pengecekan ke left child sampai menemukan nilai null. setelah itu kita perlu melakukan swap nilai. untuk memahami secara jelas, saya merekomendaskan km untuk melihat ini. visual-bst. berikut adalah contoh kode implementasinya


func (b *BinaryTree) remove(value int) {
    curr := b.Root
    if curr == nil {
        return
    }
    if curr.Right == nil && curr.Left == nil {
        if curr.Value == value {
            b.Root =  nil
        }
    }
    for curr != nil {
        if value < curr.Value{
            if curr.Left != nil && curr.Left.Value == value {
                break
            }
            curr = curr.Left
        }else {
            if curr.Right != nil && curr.Right.Value == value {
                break
            }
            curr = curr.Right
        }
    }
    if curr == nil {
        fmt.Println("Value not found")
        return
    }
    if curr.Left.Value == value {
        parent := curr
        curr = curr.Left
        rightNode := curr.Right
        if rightNode == nil {
            parent.Left = curr.Left
            curr.Left = nil
            return
        }
        if rightNode.Left == nil {
            parent.Left = rightNode
            rightNode.Left = curr.Left
            curr.Right, curr.Left =nil, nil
        }else {
            for rightNode.Left != nil {
                rightNode = rightNode.Left
            }
            parent.Left = rightNode
            rightNode.Left, rightNode.Right = curr.Left, curr.Right
            curr.Left, curr.Right = nil, nil
        }
    }else if curr.Right.Value == value{
        parent :=curr
        curr = curr.Right
        rightNode := curr.Right
        if rightNode == nil{
            parent.Right = curr.Left
            curr.Left = nil
            return
        }
        if rightNode.Left == nil {
            parent.Right = rightNode
            rightNode.Left = curr.Left
            curr.Right, curr.Left = nil, nil
        }else {
            for rightNode.Left != nil {
                rightNode = rightNode.Left
            }
            parent.Right = rightNode
            rightNode.Left, rightNode.Right = curr.Left, curr.Right
        }
    }
}

Kesimpulan

Dalam artikel ini , kita telah membahas binary search tree data structure. yang memiliki 3 operasi dasar (cari, insert, dan delete) dan dari dalam kasus best case memiliki operasi O (log n) yang tentunya salah satu data structure yang memiliki performa yang bagus. Terimakasih sudah membaca artikel ini.