Binary Search Tree

Apa itu Tree?

Tree merupakan salah satu bentuk struktur data non-linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen.

Tree bisa didefinisikan sebagai kumpulan node dengan elemen khusus yang disebut Root dan referensi ke node lain yang disebut dengan Child. Suatu node dari tree bersama dengan seluruh node di bawahnya membentuk sebuah subtree. Subtree dari sebuah tree juga merupakan sebuah tree.

Terminologi

• Root - merupakan node paling atas (node pertama) dari sebuah tree
• Edge - merupakan referensi yang menghubungkan antar dua node
• Child - merupakan ekstensi (node yang berada di bawahnya) dari sebuah node
• Parent - merupakan node yang berada di atas dari sebuah node. Seluruh node pasti mempunyai parent kecuali root node.
• Siblings - merupakan kumpulan dua atau lebih node yang mempunyai parent yang sama.
• Leaf - merupakan node yang tidak mempunyai child
• Internal node - merupakan semua node yang tidak termasuk leaf dan node

Binary Tree

Binarty Tree merupakan tree yang tiap-tiap nodenya mempunyai paling banyak dua child (left child dan right child)

Binary Search Tree

• Subtree kiri dari sebuah node hanya berisi node dengan key lebih kecil dari key node
• Subtree kanan sebuah node hanya berisi node dengan key lebih besar dari key node
• Subtree kiri dan kanan masing-masing juga harus berupa BST

Implementasi dan Dokumentasi