{"id":4255,"date":"2026-08-20T19:29:32","date_gmt":"2026-08-20T12:29:32","guid":{"rendered":"https:\/\/focusnic.com\/blog\/?p=4255"},"modified":"2026-08-20T19:29:34","modified_gmt":"2026-08-20T12:29:34","slug":"pengertian-binary-search-tree","status":"publish","type":"post","link":"https:\/\/focusnic.com\/blog\/pengertian-binary-search-tree\/","title":{"rendered":"Pengertian Binary Search Tree"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">Pada dunia <strong>struktur data<\/strong> dan <strong>algoritma<\/strong>, <strong>Binary Search Tree<\/strong> (BST) menempati posisi penting sebagai salah satu cara efisien menyimpan dan melakukan pencarian data. BST adalah pohon biner dengan properti khusus: setiap simpul (node) memiliki nilai yang lebih besar dari semua nilai di sub-pohon kiri dan lebih kecil dari semua nilai di sub-pohon kanan. Properti ini memungkinkan operasi <strong>pencarian<\/strong>, <strong>penyisipan<\/strong>, dan <strong>penghapusan<\/strong> dijalankan rata-rata dengan kompleksitas waktu O(log n).<\/p>\n\n\n\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_86 counter-hierarchy ez-toc-counter ez-toc-light-blue ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Table of Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/focusnic.com\/blog\/pengertian-binary-search-tree\/#Definisi_Binary_Search_Tree\" >Definisi Binary Search Tree<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/focusnic.com\/blog\/pengertian-binary-search-tree\/#Struktur_dan_Properti_Utama_BST\" >Struktur dan Properti Utama BST<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/focusnic.com\/blog\/pengertian-binary-search-tree\/#Operasi_Dasar_pada_BST_Pencarian_Penyisipan_dan_Penghapusan\" >Operasi Dasar pada BST: Pencarian, Penyisipan, dan Penghapusan<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/focusnic.com\/blog\/pengertian-binary-search-tree\/#1_Pencarian_Search\" >1. Pencarian (Search)<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/focusnic.com\/blog\/pengertian-binary-search-tree\/#2_Penyisipan_Insertion\" >2. Penyisipan (Insertion)<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/focusnic.com\/blog\/pengertian-binary-search-tree\/#3_Penghapusan_Deletion\" >3. Penghapusan (Deletion)<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/focusnic.com\/blog\/pengertian-binary-search-tree\/#Optimasi_dan_Penerapan_Lanjutan_Binary_Search_Tree\" >Optimasi dan Penerapan Lanjutan Binary Search Tree<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/focusnic.com\/blog\/pengertian-binary-search-tree\/#Kesimpulan\" >Kesimpulan<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Definisi_Binary_Search_Tree\"><\/span>Definisi Binary Search Tree<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Binary Search Tree<\/strong> adalah pohon biner berlabel, di mana:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Setiap simpul menyimpan sebuah nilai kunci.<\/li>\n\n\n\n<li>Sub-pohon kiri berisi simpul dengan kunci lebih kecil daripada kunci di simpul induk.<\/li>\n\n\n\n<li>Sub-pohon kanan berisi simpul dengan kunci lebih besar daripada kunci di simpul induk.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Definisi ini menciptakan struktur terurut yang memudahkan pencarian data secara efisien.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Dengan memanfaatkan sifat terurut, <strong>BST<\/strong> mampu mencapai kompleksitas rata-rata O(log n) untuk operasi pencarian. Dibandingkan dengan array terurut yang menggunakan <em>binary search<\/em> namun membutuhkan O(n) untuk penyisipan atau penghapusan, BST menawarkan keseimbangan antara efisiensi pencarian dan fleksibilitas dalam menambah atau menghapus data.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Struktur_dan_Properti_Utama_BST\"><\/span>Struktur dan Properti Utama BST<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Setiap simpul dalam <strong>BST<\/strong> memiliki atribut dasar:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Key<\/strong>: nilai kunci untuk perbandingan.<\/li>\n\n\n\n<li><strong>Left<\/strong>: referensi ke sub-pohon kiri (kunci lebih kecil).<\/li>\n\n\n\n<li><strong>Right<\/strong>: referensi ke sub-pohon kanan (kunci lebih besar).<\/li>\n\n\n\n<li><strong>Parent<\/strong> (opsional): referensi ke simpul induk, berguna untuk operasi penyeimbangan atau traversal.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Struktur sederhana ini menyusun hubungan antar-simpul sehingga traversal terurut (in-order) menghasilkan daftar nilai yang terurut menaik.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Agar memenuhi kriteria <strong>binary search tree<\/strong>, setiap simpul harus mematuhi dua syarat fundamental:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Semua kunci di sub-pohon kiri simpul X lebih kecil dari kunci X.<\/li>\n\n\n\n<li>Semua kunci di sub-pohon kanan simpul X lebih besar dari kunci X.<\/li>\n<\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">Jika salah satu syarat dilanggar, operasi pencarian dan penyisipan tidak lagi memberikan performa optimal. Oleh karena itu, validasi struktur setelah setiap operasi mutasi (insert\/delete) sangat penting.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Operasi_Dasar_pada_BST_Pencarian_Penyisipan_dan_Penghapusan\"><\/span>Operasi Dasar pada BST: Pencarian, Penyisipan, dan Penghapusan<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"1_Pencarian_Search\"><\/span>1. Pencarian (Search)<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Operasi <strong>search<\/strong> memanfaatkan sifat terurut BST:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Mulai di akar (root).<\/li>\n\n\n\n<li>Jika kunci target sama dengan kunci simpul saat ini, proses selesai.<\/li>\n\n\n\n<li>Jika kunci target lebih kecil, lanjutkan ke anak kiri; jika lebih besar, ke anak kanan.<\/li>\n\n\n\n<li>Ulangi hingga menemukan simpul atau mencapai simpul null (data tidak ditemukan).<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Rata-rata kompleksitas waktu: O(log n). Kasus terburuk (pohon miring) menjadi O(n).<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"2_Penyisipan_Insertion\"><\/span>2. Penyisipan (Insertion)<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Menambahkan simpul baru ke dalam <strong>BST<\/strong> mengikuti logika serupa pencarian:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Mulai dari root, bandingkan kunci baru dengan kunci simpul saat ini.<\/li>\n\n\n\n<li>Jika kunci baru lebih kecil, arahkan ke sub-pohon kiri; jika lebih besar, ke sub-pohon kanan.<\/li>\n\n\n\n<li>Ulangi hingga menemukan posisi null, kemudian sisipkan simpul baru di sana.<\/li>\n<\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">Proses ini menjaga syarat terurut. Kompleksitas rata-rata: O(log n). Namun jika data disisipkan berurutan menaik atau menurun, pohon akan berubah menjadi rantai (linked list) dengan kompleksitas O(n).<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"3_Penghapusan_Deletion\"><\/span>3. Penghapusan (Deletion)<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Operasi <strong>delete<\/strong> lebih kompleks, karena ada tiga skenario:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Simpul daun (leaf): cukup lepaskan referensi dari induk.<\/li>\n\n\n\n<li>Simpul dengan satu anak: gantikan simpul yang dihapus dengan anaknya.<\/li>\n\n\n\n<li>Simpul dengan dua anak: cari <strong>inorder successor<\/strong> (simpul terkecil di sub-pohon kanan) atau <strong>inorder predecessor<\/strong> (simpul terbesar di sub-pohon kiri), salin nilainya, lalu hapus simpul pengganti (yang merupakan simpul rantai satu anak atau daun).<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Langkah terakhir memastikan struktur tetap valid. Kompleksitas rata-rata: O(log n). Kasus terburuk: O(n).<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Optimasi_dan_Penerapan_Lanjutan_Binary_Search_Tree\"><\/span>Optimasi dan Penerapan Lanjutan Binary Search Tree<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Untuk menghindari kasus terburuk, sejumlah varian <strong>BST<\/strong> menambahkan mekanisme penyeimbangan otomatis:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>AVL Tree<\/strong>: menjaga perbedaan tinggi sub-pohon kiri dan kanan paling banyak 1. Melakukan rotasi tunggal atau ganda saat terjadi ketidakseimbangan.<\/li>\n\n\n\n<li><strong>Red-Black Tree<\/strong>: setiap simpul diberi warna merah atau hitam, dengan aturan khusus untuk memastikan jalur terpanjang tidak melebihi dua kali jalur terpendek.<\/li>\n\n\n\n<li><strong>Splay Tree<\/strong>: setelah akses (search\/insert\/delete), simpul yang diakses di-&#8220;splay&#8221; ke akar, meningkatkan performa akses berulang pada elemen yang sama.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Dengan penyeimbangan, kompleksitas operasi dipertahankan O(log n) di semua kasus, menjadikan BST lebih andal untuk aplikasi kritikal.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Binary Search Tree<\/strong> banyak digunakan di dunia nyata, antara lain:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Pangkalan data ringan (embedded database) untuk mengelola indeks sederhana.<\/li>\n\n\n\n<li>Pencarian menu GUI atau struktur file sistem operasi.<\/li>\n\n\n\n<li>Implementasi <em>symbol table<\/em> dalam compiler atau interpreter bahasa pemrograman.<\/li>\n\n\n\n<li>Algoritma kompresi dan struktur data grafis di gim komputer.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Fleksibilitas dan performa BST memungkinkan integrasi dalam berbagai solusi perangkat lunak, khususnya yang memerlukan struktur data dinamis dan operasi pencarian cepat.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Kesimpulan\"><\/span>Kesimpulan<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Binary Search Tree<\/strong> adalah fondasi penting dalam <strong>struktur data<\/strong> dan <strong>algoritma<\/strong>. Dengan memahami properti dasar, operasi pencarian, penyisipan, serta penghapusan, Anda dapat membangun aplikasi yang responsif dan hemat memori. Untuk kinerja optimal di semua kasus, pertimbangkan varian terpenyeimbang seperti <strong>AVL Tree<\/strong> atau <strong>Red-Black Tree<\/strong>. Semoga panduan ini membantu Anda menguasai konsep dasar hingga penerapan lanjutan <strong>Binary Search Tree<\/strong>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Pada dunia struktur data dan algoritma, Binary Search Tree (BST) menempati posisi penting sebagai salah satu cara efisien menyimpan dan melakukan pencarian data. BST adalah pohon biner dengan properti khusus: setiap simpul (node) memiliki nilai yang lebih besar dari semua nilai di sub-pohon kiri dan lebih kecil dari semua nilai di sub-pohon kanan. Properti ini [&hellip;]<\/p>\n","protected":false},"author":3,"featured_media":4312,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[114],"class_list":["post-4255","post","type-post","status-publish","format-standard","has-post-thumbnail","category-informasi","tag-programming"],"_links":{"self":[{"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/posts\/4255","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/comments?post=4255"}],"version-history":[{"count":1,"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/posts\/4255\/revisions"}],"predecessor-version":[{"id":4313,"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/posts\/4255\/revisions\/4313"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/media\/4312"}],"wp:attachment":[{"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/media?parent=4255"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/categories?post=4255"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/tags?post=4255"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}