Pohon Stern–Brocot

Pohon Stern–Brocot, dan barisan Stern–Brocot dari orde i untuk i = 1, 2, 3, 4.

Dalam teori bilangan, pohon Stern–Brocot (bahasa Inggris: Stern–Brocot tree) adalah pohon biner lengkap yang tak terhingga. Pada pohon tersebut, simpulnya berkorespondensi satu-ke-satu dengan bilangan rasional positif, yang nilainya diurutkan dari kiri ke kanan seperti pada pohon telusur.

Pohon Stern–Brocot ditemukan secara terpisah oleh seorang ahli teori bilangan berkebangsaan Jerman bernama Moritz Stern, dan seorang pembuat jam di Prancis bernama Achille Brocot, yang menggunakan pohon Stern-Brocot untuk merancang sistem roda gigi dengan rasio roda gigi mendekati nilai yang diinginkan dengan menemukan rasio bilangan halus di dekat nilai tersebut.

Akar dari pohon Stern–Brocot korespondensi dengan angka 1. Hubungan induk-anak antara bilangan dalam pohon Stern–Brocot dapat didefinisikan dengan menggunakan pecahan berlanjut atau mediant, dan sebuah lintasan di pohon dari akar ke setiap bilangan lain ${\displaystyle q}$ memberikan barisan dari aproksimasi ke ${\displaystyle q}$, dengan penyebut yang lebih kecil dari ${\displaystyle q}$. Karena pohon tersebut mengandung setiap bilangan rasional positif tepatnya satu, algoritma breadth-first search dari pohon menyediakan metode dari daftar semua bilangan rasional positif yang terkait erat dengan barisan Farey. Subpohon di sebelah kiri dari pohon Stern–Brocot, yang mengandung bilangan rasional di kisaran (bahasa Inggris: range) ${\displaystyle (0,1)}$, disebut pohon Farey (bahasa Inggris: Farey tree).