Binary Search Tree
Binary Tree
Adalah sebuah pohon dalam sebuah struktur data yang bersifat hirarkis (berhubungan satu dengan yang lain). Tree bisa didefenisikan sebagai kumpulan simpul dengan setiap simpul mempunyai paling banyak dua anak. Secara khusus, anaknya dinamakan kiri dan kanan.
Binary tree memiliki syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binary treee boleh memiliki paling banyak dua child (anak simpul) yang disebut kiri dan kanan.
Binary Search Tree
Adalah struktur data yang mengambil konsep Binary Tree namun terdapat aturan bahwa setiap anaka node sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node. Binary search tree memungkinkan pencarian dengan cepat, penambahan, juga menghapus data yang ada di dalamnya, bisa juga digunakan sebagai implementasi sejumlah data dinamis, atau pencarian table data dengan menggunakan informasi kunci atau key.
Aturan Binary Search Tree :
-Setiap anak node sebelah kiri harus lebih kecil nilainya daripada root nodenya.
-Setiap anak node sebelah kanan harus lebih besar nilainya daripada root nodenya.
Kenapa harus membedakan kiri dan kanan sesuai nilainya? Tujuannya untuk memberikan efisiensi terhadap proses searching. Kalau struktur data tree sudah tersusun rapi sesuai aturannya, proses search akan lebih cepat.
Insert node pada BST:
Memasukan data pada Binary Search Tree ketentuan umumnya adalah inputan yang mempunyai nilai kecil diletakan pada sebelah kiri root / node, dan sebaliknya. (inputan pertama otomatis menjadi root).
Delete node pada BST:
Terdapat 3 kemungkinan yang ada saat ingin menghapus node :
1) Node to be deleted is leaf: Simply remove from the tree.
50 50
/ \ delete(20) / \
30 70 ---------> 30 70
/ \ / \ \ / \
20 40 60 80 40 60 80
2) Node to be deleted has only one child: Copy the child to the node and delete the child
50 50
/ \ delete(30) / \
30 70 ---------> 40 70
\ / \ / \
40 60 80 60 80
3) Node to be deleted has two children: Find inorder successor of the node. Copy contents of the inorder successor to the node and delete the inorder successor. Note that inorder predecessor can also be used.
50 60
/ \ delete(50) / \
40 70 ---------> 40 70
/ \ \
60 80 80
Sumber : https://www.geeksforgeeks.org/binary-search-tree-data-structure/
https://www.programiz.com/dsa/binary-search-tree
http://rismawati1911.blogspot.com/2015/05/binary-search-tree-pengantar-struktur.html
https://sourcecodegeneration.blogspot.com/2018/08/pengertian-binary-tree-binary-search.html
Adalah sebuah pohon dalam sebuah struktur data yang bersifat hirarkis (berhubungan satu dengan yang lain). Tree bisa didefenisikan sebagai kumpulan simpul dengan setiap simpul mempunyai paling banyak dua anak. Secara khusus, anaknya dinamakan kiri dan kanan.
Binary tree memiliki syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binary treee boleh memiliki paling banyak dua child (anak simpul) yang disebut kiri dan kanan.
Binary Search Tree
Adalah struktur data yang mengambil konsep Binary Tree namun terdapat aturan bahwa setiap anaka node sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node. Binary search tree memungkinkan pencarian dengan cepat, penambahan, juga menghapus data yang ada di dalamnya, bisa juga digunakan sebagai implementasi sejumlah data dinamis, atau pencarian table data dengan menggunakan informasi kunci atau key.
Aturan Binary Search Tree :
-Setiap anak node sebelah kiri harus lebih kecil nilainya daripada root nodenya.
-Setiap anak node sebelah kanan harus lebih besar nilainya daripada root nodenya.
Kenapa harus membedakan kiri dan kanan sesuai nilainya? Tujuannya untuk memberikan efisiensi terhadap proses searching. Kalau struktur data tree sudah tersusun rapi sesuai aturannya, proses search akan lebih cepat.
Insert node pada BST:
Memasukan data pada Binary Search Tree ketentuan umumnya adalah inputan yang mempunyai nilai kecil diletakan pada sebelah kiri root / node, dan sebaliknya. (inputan pertama otomatis menjadi root).
Delete node pada BST:
Terdapat 3 kemungkinan yang ada saat ingin menghapus node :
1) Node to be deleted is leaf: Simply remove from the tree.
50 50
/ \ delete(20) / \
30 70 ---------> 30 70
/ \ / \ \ / \
20 40 60 80 40 60 80
2) Node to be deleted has only one child: Copy the child to the node and delete the child
50 50
/ \ delete(30) / \
30 70 ---------> 40 70
\ / \ / \
40 60 80 60 80
3) Node to be deleted has two children: Find inorder successor of the node. Copy contents of the inorder successor to the node and delete the inorder successor. Note that inorder predecessor can also be used.
50 60
/ \ delete(50) / \
40 70 ---------> 40 70
/ \ \
60 80 80
Sumber : https://www.geeksforgeeks.org/binary-search-tree-data-structure/
https://www.programiz.com/dsa/binary-search-tree
http://rismawati1911.blogspot.com/2015/05/binary-search-tree-pengantar-struktur.html
https://sourcecodegeneration.blogspot.com/2018/08/pengertian-binary-tree-binary-search.html
Comments
Post a Comment