Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

2026-08-23T10:25:31Z

Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

← Revisi sebelumnya		Revisi per 23 Agustus 2026 10.25
Baris 1:		Baris 1:
			[[File:Binary_search_tree.svg\|thumb\|right\|280px\|Binary search tree]]

	Dalam [[ilmu komputer]], sebuah '''pohon pencarian biner''' (PPB) atau '''pohon biner terurut''' adalah sebuah [[pohon biner]] yang memiliki sifat-sifat berikut:		Dalam [[ilmu komputer]], sebuah '''pohon pencarian biner''' (PPB) atau '''pohon biner terurut''' adalah sebuah [[pohon biner]] yang memiliki sifat-sifat berikut:
	* Setiap [[Pohon (struktur data)#Simpul (node)\|simpul]] (''node'') memiliki sebuah nilai.		* Setiap [[Pohon (struktur data)#Simpul (node)\|simpul]] (''node'') memiliki sebuah nilai.
Baris 78:		Baris 80:
	* '''Penghapusan sebuah node dengan dua anak:''' Misalkan node yang akan dihapus adalah ''N''. Kita ganti nilai dari N dengan suksesor ''in-order'' (anak terkiri dari subpohon kanan) atau dengan predesesor ''in-order'' (anak terkanan dari subpohon kiri).		* '''Penghapusan sebuah node dengan dua anak:''' Misalkan node yang akan dihapus adalah ''N''. Kita ganti nilai dari N dengan suksesor ''in-order'' (anak terkiri dari subpohon kanan) atau dengan predesesor ''in-order'' (anak terkanan dari subpohon kiri).

			== Sumber dan atribusi ==

			Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Pohon+Pencarian+Biner&oldid=28370084 Wikipedia bahasa Indonesia], revisi 28370084 (2025-11-07T06:59:13Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Gambar pada artikel ini bersumber dari Wikimedia Commons dan mengikuti ketentuan lisensi masing-masing berkas. Mohon gunakan konten dan media secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

	~~== Sumber dan atribusi ==~~		<!-- WIKI_UNISSULA_PRESENTATION_V4 -->

	~~Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Pohon+Pencarian+Biner&oldid=28370084 Wikipedia bahasa Indonesia], revisi 28370084 (2025~~-11-~~07T06:59:13Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi~~-~~BerbagiSerupa (CC BY~~-~~SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.~~

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 28370084; atribusi sumber disertakan.

2026-08-23T09:51:14Z

Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 28370084; atribusi sumber disertakan.

Halaman baru

Dalam [[ilmu komputer]], sebuah '''pohon pencarian biner''' (PPB) atau '''pohon biner terurut''' adalah sebuah [[pohon biner]] yang memiliki sifat-sifat berikut:
* Setiap [[Pohon (struktur data)#Simpul (node)|simpul]] (''node'') memiliki sebuah nilai.
* Sebuah [[susunan total]] ditentukan dalam nilai ini.
* [[Pohon (struktur data)#Sub pohon (Subtrees)|Sub pohon]] (''subtree'') kiri dari sebuah simpul hanya memuat nilai lebih kecil dari nilai simpul.
* Sub pohon kanan dari sebuah simpul hanya memuat nilai lebih besar atau sama dengan nilai dari simpul.

Kelebihan utama dari pohon pencarian biner adalah keterkaitannya dengan [[algoritme pengurutan]] dan [[algoritme pencarian]] yang dapat lebih efisien, seperti ''[[in-order traversal]]''.

Pohon pencarian biner adalah sebuah struktur data dasar yang digunakan untuk membentuk struktur data yang lebih abstrak seperti [[struktur data set|set]], [[multiset]], dan [[array asosiatif]].

Jika PPB memperkenankan nilai-nilai duplikat, maka PPB merupakan sebuah multiset. Pohon jenis ini menggunakan ketaksamaan longgar (''non-strict inequalities''), sehingga semua yang berada di subpohon bagian kiri dari sebuah node adalah lebih kecil atau sama dengan nilai dari node, dan semua yang berada di subpohon bagian kanan dari node adalah lebih besar atau sama dengan nilai dari node.

Jika PPB tidak memperkenankan nilai-nilai duplikat, maka PPB merupakan sebuah set dengan nilai-nilai unik, sama seperti set pada matematika (himpunan). Pohon tanpa nilai-nilai duplikat menggunakan ketaksamaan kaku (''strict inequalities''), artinya subpohon kiri dari sebuah node hanya memuat node-node dengan nilai yang lebih kecil dari nilai node, dan subpohon kanan hanya memuat nilai-nilai yang lebih besar.

Beberapa definisi PPB menggunakan sebuah ketaksamaan longgar hanya pada satu sisi, sehingga nilai-nilai duplikat diperkenankan. Walaupun demikian, definisi-definisi PPB tersebut membatasi dengan baik bagaiman sebuah pohon dengan banyak nilai duplikat dapat diseimbangkan.

== Operasi-operasi ==
=== Pencarian ===
Pencarian sebuah nilai tertentu pada pohon biner adalah sebuah proses yang dapat dilakukan secara rekursif karena nilai-nilai yang disimpan adalah terurut. Pencarian dimulai dengan memeriksa akar (''root''). Jika nilai yang dicari sama dengan akar, maka nilai ditemukan. Jika nilai yang dicari kurang dari akar, maka pencarian dilakukan terhadap subpohon kiri, sehingga kita secara rekursif mencari subpohon kiri dengan cara yang sama. Jika nilai yang dicari lebih besar dari akar, maka pencarian dilakukan terhadap subpohon kanan sehingga kita secara rekursif mencari subpohon kanan dengan cara yang sama. Jika kita mencapai sebuah ujung (''leaf'') dan belum menemukan yang dicari, maka nilai tersebut tidak ada dalam pohon. Sebuah pembandingan dapat dibuat dengan [[pencarian biner]], yang beroperasi hampir mirip degan pengaksesan acak pada sebuah array.

Berikut adalah algoritma pencarian dalam [[bahasa pemrograman Python]]:

'''def''' search_binary_tree(node, key):
'''if''' node '''is''' None:
'''return''' None # not found
'''if''' key < node.key:
'''return''' search_binary_tree(node.left, key)
'''elif''' key > node.key:
'''return''' search_binary_tree(node.right, key)
'''else''':
'''return''' node.value

Operasi tersebut membutuhkan waktu [[notasi O besar|O]](log ''n'') pada kasus rata-rata, dan pada kasus terburuk membutuhkan waktu [[notasi O besar|O]](''n'') ketika pohon tak seimbang yang menyerupai sebuah list berkai.

=== Penyisipan ===
Penyisipan dimulai sebagaimana sebuah pencarian dilakukan. Jika akar tidak sama dengan nilai sisipan,
kita mencari subpohon kiri atau kanan seperti di atas. Pada suatu saat kita akan mencapai
sebuah node luar dan menambahkan nilai sisipan sebagai anak kiri atau anak kanan, bergantung pada nilai node.
Dengan kata lain, kita memeriksa akar dan secara rekursif menyisipkan node yang baru ke subpohon
kiri jika nilai yang baru lebih kecil atau sama dengan akar, atau menyisipkan ke subpohon
kanan jika nilai yang baru lebih besar dari root.

Berikut adalah penyisipan pohon pencarian biner yang biasa dilakukan dalam C:

'''void''' InsertNode(struct node **node_ptr, struct node *newNode) {
struct node *node = *node_ptr;
'''if''' (node == '''NULL''')
*node_ptr = newNode;
'''else if''' (newNode->value <= node->value)
InsertNode(&node->left, newNode);
'''else'''
InsertNode(&node->right, newNode);
}

Variasi prosedural di atas adalah destruktif. Cara di atas hanya menggunakan ruang yang tetap, sehingga pohon versi sebelumnya menjadi hilang. Alternatif cara adalah seperti contoh Python berikut, kita dapat merekonstruksi kembali semua ''pendahulu'' dari node yang disisipkan; Semua referensi ke akar pohon asal akan tetap valid, yang membuat phon menjadi sebuah [[struktur data persisten]].

'''def''' binary_tree_insert(node, key, value):
'''if''' node '''is''' None:
'''return''' TreeNode(None, key, value, None)

'''if''' key == node.key:
'''return''' TreeNode(node.left, key, value, None)
'''if''' key < node.key:
'''return''' TreeNode(binary_tree_insert(node.left, key, value), node.key, node.value, node.right)
'''else''':
'''return''' TreeNode(node.left, node.key, node.value, binary_tree_insert(node.right, key, value))

Cara pertama di atas menggunakan ruang O(log ''n'') pada kasus rata-rata dan O(''n'') dalam kasus terburut.

Pada kasus berikutnya, operasi membutuhkan waktu yang berbanding lurus dengan tinggi pohon pada kasus terburuk, yaitu [[notasi O besar|O]](log ''n'') pada kasus rata-rata, dan O(''n'') pada kasus terburuk.

Cara lain menjelaskan penyisipan adalah bahwa untuk menyisipkan sebuah node baru dalam pohon, nilainya terlebih dahulu dibandingkan dengan nilai dari akar. Jika nilainya lebih kurang dari nilai akar, nilai tersebut kemudian dibandingkan dengan nilai dari anak kiri akar. Jika nilainya lebih besar dari nilai akar, nilai tersebut dibandingkan dengan nilai dari anak kanan akar. Proses tersebut berlanjut, sampai node yang baru dibandingkan dengan node ujung, dan kemudian ditambahkan sebagai node anak kanan atau anak kiri bergantung nilainya.

=== Penghapusan ===
Ada kasus-kasus yang mesti diperhatikan:
* '''Penghapusan sebuah ujung:''' Penghapusan sebuah node tanpa anak adalah mudah, cukup menghilangkanya dari pohon.
* '''Penghapusan sebuah node dengan satu anak:''' Menghapusnya dan mengganti dengan anaknya.
* '''Penghapusan sebuah node dengan dua anak:''' Misalkan node yang akan dihapus adalah ''N''. Kita ganti nilai dari N dengan suksesor ''in-order'' (anak terkiri dari subpohon kanan) atau dengan predesesor ''in-order'' (anak terkanan dari subpohon kiri).

== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Pohon+Pencarian+Biner&oldid=28370084 Wikipedia bahasa Indonesia], revisi 28370084 (2025-11-07T06:59:13Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

Pohon Pencarian Biner - Riwayat revisi

Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 28370084; atribusi sumber disertakan.