Pohon pencarian biner

Pohon adalah struktur bertingkat: satu simpul akar di puncak, setiap simpul boleh punya anak, dan simpul tanpa anak disebut daun. Tinggi pohon adalah banyaknya simpul pada jalur terpanjang dari akar ke daun. Pohon pencarian biner (binary search tree, BST) membatasi setiap simpul paling banyak dua anak dan menambah satu aturan: semua kunci di subpohon kiri lebih kecil dari kunci simpul, dan semua kunci di subpohon kanan lebih besar.

Aturan itu membuat pencarian mirip pencarian biner pada daftar urut. Mulai dari akar, bandingkan kunci yang dicari: lebih kecil pergi ke kiri, lebih besar pergi ke kanan, sama berarti ketemu, dan None berarti tidak ada. Banyaknya perbandingan paling banyak setinggi pohon. Menyisipkan berjalan dengan cara yang sama sampai menemukan tempat kosong. Bedanya dengan daftar urut, menyisipkan ke BST tidak perlu menggeser data lain.

def cari(akar, kunci):
    s = akar
    while s is not None:
        if kunci == s.kunci:
            return True
        s = s.kiri if kunci < s.kunci else s.kanan
    return False

Penelusuran urut-tengah (in-order) mengunjungi subpohon kiri, lalu simpul, lalu subpohon kanan. Karena aturan BST, urutan kunjungan itu menghasilkan semua kunci dari terkecil ke terbesar. Pohon yang seimbang, misalnya hasil menyisipkan kunci dalam urutan acak, tingginya sekitar log₂ n, sehingga sejuta kunci cukup dicari dalam sekitar 20 perbandingan.