Skip to main content

Binary Search Tree


Binary Search Tree

Binary Search Tree adalah salah satu bentuk data structure yang mendukung searching secara lebih cepat, sorting lebih cepat, dan mempermudah insertion dan deletion.

Binary Search Tree juga dikenal sebagai versi sorting dari Binary Tree

200px-Binary_search_tree.svg

Untuk node x = 8

  • Elemen di sebelah kiri dari node x harus bernilai lebih kecil dari x
  • Elemen di sebelah kanan dari node x harus bernilai lebih besar dari x
( dengan asumsi dimana setiap elemen / node bernilai berbeda satu dengan yang lain )

Basic Operation

  • find(x) : find the key x
  • insert(x) : insert new key x
  • remove(x) : remove key x 

Search

  • karena kelebihan BST dimana searching sangat mudah dengan menggunakan BST
  • misalkan kita ingin mencari x
    • kita akan mulai dari root
    • jika di root ditemukan nilai x ( root = x ), maka search akan dihentikan
    • jika nilai x lebih kecil dari root, maka pencarian akan dilakukan secara rekursif di sub tree kiri dari root. 
    • Jika nilai x lebih besar dari roor, maka pencarian akan dilakukan secara rekursif di sub tree kanan dari root. 

Insertion

  • Insertion dilakukan secara rekursif
  • Misalkan new key adalah x
    • dimulai dari root
    • Jika nilai x lebih kecil dari new key, maka nilai x akan dimasukkan ke daerah sub tree sebelah kiri.
    • Jika nilai x lebih besar dari new key, maka nilai x akan dimasukkan ke daerah sub tree sebelah kanan.
    • Dilakukan secara rekursif sampai terdapat node kosong untuk meletakkan (dimana x akan selalu menjadi new leaf )

Berikut adalah contoh insertion dimana merupakan pencarian tempat untuk node key baru.
PENGENALAN BINARY SEARCH TREE | @ABDILAHRF            Insertion Example BST

                                             Insertion BST


Deletion 

Terdapat tiga kondisi yang perlu dipertimbangkan : 
  1. Jika key adalah leaf, maka node tersebut akan dihapus
  2. Jika key adalah node yang mempunyai satu child, maka node tersebut dihapus dan child akan dihubungkan dengan parent-nya
  3. Jika key adalah node yang mempunyai dua children, maka temukan 

Berikut adalah contoh deletion yang merupakan penghapusan node key.

Binary Search Tree deletion of a node | BST operations









Comments

Post a Comment

Popular posts from this blog

Summary of Data Structures ( 1st Semester )

Single Linked List Circular Single Linked List Circular adalah Single Linked List yang pointer selanjutnya menunjuk ke dirinya sendiri. Jika terdiri dari beberapa node, maka pointer next pada node terakhir akan menunjuk ke pointer terdepan.            Single :  artinya field pointer-nya hanya satu buah saja dan satu arah. Circular :  artinya pointer next-nya akan menunjuk ke dirinya sendiri sehingga akan membuat sebuah sirkuit atau sirkular Ilustrasi -           Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya yang juga memiliki field yang berisi data -           Pada akhir linked list, node terakhir akan menunjuk ke node terdepan sehingga linked list tersebut berputar. Node terakhir akan menunjuk lagi ke head. Rangkaian Single Linked List tersebut diawali dengan sebuah head un...
Post a Comment
Read more

AVL Tree

AVL Tree adalah Binary Tree yang sudah dapat melakukan self-balancing terhadap node di dalam tree-nya Dalam AVL Tree, terdapat 3 komponen utama yaitu: Key / Data yang bersifat unik Level ( perhitungan dari root sampai node / leaf terjauh ) Balance Factor ( perbedaan level dari anak kiri dan anak kanan ) Dalam Gambar, yang diberi warna biru muda memiliki: Key = 75 Level = 3 ( dihitung dari key 100, key 50, dan key 75 ) Balance Factor = 0, yang dilihat dari level anak kiri 75 yaitu, 65 dan anak kanan 75 yaitu, 85, maka 1-1 = 0 Balance Factor dapat dilihat sebagai berikut :  Leaves selalu memiliki balance factor 0 dan level 1 karena leaves adalah node terujung dan tidak memiliki anak  Dari leaves ke induknya, maka balance factor dan level dihitung dengan ketentuan:  Level Induk = [Level tertinggi anak] + 1 Balance Factor = [Level anak kiri] - [Level anak kanan] Sebuah node tidak boleh memiliki Balance Factor lebih dari 1. Jika terdapat node y...
Post a Comment
Read more

Heap & Tries

Heap Heap adalah struktur data yang berbentuk pohon yang merupakan jenis dari binary tree. Heap juga mempunyai karakter dimana masing-masing node mempunyai maksimum dua children sebagaimana terdapat di dalam binary tree. Heap juga merupakan complete binary tree yang memenuhi sifat - sifat heap. Heap Property Min Heap dimana setiap key dalam node bernilai lebih kecil dari children-nya Max Heap dimana setiap key dalam node bernilai lebih besar dari children-nya Min Heap Setiap key dalam node bernilai lebih kecil dari key children-nya. Key yang bernilai paling kecil berada di root. Key yang bernilai paling besar berada di salah satu dari node leaves. Heap bisa diimplementasikan menggunakan linked list, namun lebih mudah diimplementasikan dengan menggunakan array Applications of Heaps Heap Sort Selection Algorithm Graph Algorithm Selection Algorithm menemukan key minimum atau maksimum, mencari median, dan menentukan elemen k ter...
Post a Comment
Read more