ต้นไม้ชแตร์น–บรอโก

จากวิกิพีเดีย สารานุกรมเสรี
ไปยังการนำทาง ไปยังการค้นหา
ต้นไม้ชแตร์น–บรอโก และลำดับชแตร์น–บรอโกของอันดับ i โดยที่ i = 1, 2, 3, 4

ในทฤษฎีจำนวน ต้นไม้ชแตร์น–บรอโก (อังกฤษ: Stern–Brocot tree) เป็นต้นไม้ทวิภาคสมบูรณ์อนันต์ซึ่งจุดยอดสมนัยแบบหนึ่งต่อหนึ่งกับจำนวนตรรกยะบวก ซึ่งเรียงจากซ้ายไปขวาดังในต้นไม้ค้นหา (search tree)

โมริทซ์ ชแตร์น (ค.ศ. 1858) และอาชีล บรอโก (ค.ศ. 1861) ค้นพบต้นไม้ชแตร์น–บรอโกแยกกัน ชแตร์นเป็นนักทฤษฎีจำนวนชาวเยอรมัน บรอโกเป็นช่างทำนาฬิกาชาวฝรั่งเศสผู้ใช้ต้นไม้ชแตร์น–บรอโกออกแบบระบบเฟืองโดยอัตราทดเฟืองใกล้เคียงค่าที่ต้องการโดยหาอัตราส่วนจำนวนเรียบ (smooth number) ใกล้ค่านั้น

รากของต้นไม้ชแตร์น–บรอโกสมนัยกับจำนวน 1 อาจนิยามความสัมพันธ์แบบพ่อแม่-ลูกระหว่างจำนวนในพจน์เศษส่วนต่อเนื่องหรือมีเดียนต์ (mediant) และวิถีในต้นไม้จากรากถึงจำนวน q อื่นใดให้ลำดับค่าใกล้เคียงของ q โดยตัวส่วนที่น้อยกว่า q เนื่องจากต้นไม้นี้มีจำนวนตรรกยะบวกทุกตัวครั้งเดียว การค้นหาในแนวกว้างของต้นไม้นี้จึงให้วิธีแสดงรายการจำนวนตรรกยะบวกทุกตัวซึ่งสัมพันธ์ใกล้ชิดกับลำดับแฟรีย์ (Farey sequence)