ต้นไม้ในเขต
พิมพ์	ต้นไม้
ประดิษฐ์	พ.ศ. 2522
คิดค้นโดย	จอน หลุยส์ เบนท์ลีย์
ความซับซ้อนของเวลาในรูปแบบสัญกรณ์บิ๊กโอ การดำเนินการ เฉลี่ย กรณีที่เลวร้ายที่สุด ค้นหา ${\displaystyle O(\log ^{d}n+k)}$ ${\displaystyle O(\log ^{d}n+k)}$ ความซับซ้อนของพื้นที่ ช่องว่าง ${\displaystyle O(n\log ^{d-1}n)}$ ${\displaystyle O(n\log ^{d-1}n)}$

ในวิทยาการคอมพิวเตอร์ต้นไม้ช่วง (range tree)เป็นโครงสร้างข้อมูลแบบต้นไม้เรียงลำดับ เพื่อเก็บรายการของจุด ช่วยให้สามารถรายงาน จุดทั้งหมดภายในช่วงที่กำหนด ได้อย่างมีประสิทธิภาพ และโดยทั่วไปจะใช้ในสองมิติขึ้นไป ต้นไม้ช่วงได้รับการแนะนำโดยJon Louis Bentleyในปี 1979 ^{[ 1 ]}โครงสร้างข้อมูลที่คล้ายกันนี้ถูกค้นพบโดยอิสระโดย Lueker ^{[ 2 ]} Lee และ Wong ^{[ 3 ]}และ Willard ^{[ 4 ]} ต้นไม้ช่วงเป็นทางเลือกแทนต้นไม้k -d เมื่อเปรียบเทียบกับ ต้นไม้ k -d ต้นไม้ช่วงให้เวลาในการสืบค้นที่เร็วกว่า (ในสัญกรณ์ Big O ) แต่มีการจัดเก็บที่แย่กว่าโดยที่nคือจำนวนจุดที่จัดเก็บในต้นไม้dคือมิติของแต่ละจุด และkคือจำนวนจุดที่รายงานโดยการสืบค้นที่กำหนด ${\displaystyle O(\log ^{d}n+k)}$${\displaystyle O(n\log ^{d-1}n)}$

ในปี พ.ศ. 2533 Bernard Chazelleได้ปรับปรุงสิ่งนี้ให้มีความซับซ้อนด้านเวลาและพื้นที่ ในการ สอบถาม^{[ 5 ] [ 6 ]}${\displaystyle O(\log ^{d-1}n+k)}$${\displaystyle O\left(n\left({\frac {\log n}{\log \log n}}\right)^{d-1}\right)}$

ต้นไม้ช่วง (Range tree) บนเซตของจุด 1 มิติ คือต้นไม้ค้นหาแบบไบนารี ที่สมดุล บนจุดเหล่านั้น จุดที่จัดเก็บในต้นไม้จะถูกเก็บไว้ในใบของต้นไม้ โดยแต่ละโหนดภายในจะเก็บค่าที่ใหญ่ที่สุดของซับทรีด้านซ้าย ต้นไม้ช่วงบนเซตของจุดใน มิติ dคือต้นไม้ค้นหาแบบไบนารีหลายระดับที่กำหนดแบบเรียกซ้ำแต่ละระดับของโครงสร้างข้อมูลคือ ต้นไม้ค้นหาแบบไบนารีบนมิติใดมิติหนึ่งของdระดับแรกคือ ต้นไม้ค้นหาแบบไบนารีบนพิกัดแรกของdพิกัด แต่ละจุดยอดvของต้นไม้นี้จะมีโครงสร้างที่เกี่ยวข้องซึ่งเป็น ต้นไม้ช่วง ( d −1) มิติ บนพิกัด ( d −1) สุดท้ายของจุดที่จัดเก็บในซับทรีของ v

ต้นไม้ช่วงมิติเดียวบนเซตของ จุด nจุด คือต้นไม้ค้นหาแบบไบนารี ซึ่งสามารถสร้างได้ในเวลา ต้นไม้ช่วงในมิติที่สูงกว่าจะถูกสร้างขึ้นแบบเรียกซ้ำ โดยการสร้างต้นไม้ค้นหาแบบไบนารีที่สมดุลบนพิกัดแรกของจุด จากนั้น สำหรับแต่ละจุดยอดvในต้นไม้นี้ จะสร้างต้นไม้ช่วงมิติ ( d − 1) บนจุดที่อยู่ในต้นไม้ย่อยของvการสร้างต้นไม้ช่วงด้วยวิธีนี้จะใช้เวลา ${\displaystyle O(n\log n)}$${\displaystyle O(n\log ^{d}n)}$

เวลาในการสร้างนี้สามารถปรับปรุงได้สำหรับต้นไม้ช่วง 2 มิติเป็น[ ^{7 ] ให้} S เป็นเซตของจุด 2 มิติn จุด ถ้า Sมีจุดเพียงจุดเดียว ให้ส่งคืนใบที่มีจุดนั้น มิฉะนั้น ให้สร้างโครงสร้างที่เกี่ยวข้องของSซึ่งเป็นต้นไม้ช่วง 1 มิติบนพิกัดyของจุดในSให้x _mเป็นค่ามัธยฐานของพิกัดxของจุด ให้S _Lเป็นเซตของจุดที่มี พิกัด xน้อยกว่าหรือเท่ากับx _mและให้S _Rเป็นเซตของจุดที่มี พิกัด xมากกว่าx _mสร้างv _L ซึ่งเป็น ต้นไม้ช่วง 2 มิติบนS _Lและv _Rซึ่งเป็นต้นไม้ช่วง 2 มิติบนS _{R แบบ} เรียกซ้ำ สร้างจุดยอดv ที่มี v _Lเป็นลูกซ้าย และ v _Rเป็นลูกขวาหากเราเรียงลำดับจุดตาม พิกัด yในช่วงเริ่มต้นของอัลกอริทึม และคงลำดับนี้ไว้เมื่อแบ่งจุดตาม พิกัด xเราจะสามารถสร้างโครงสร้างที่เกี่ยวข้องของแต่ละซับทรีได้ในเวลาเชิงเส้น ซึ่งจะลดเวลาในการสร้างเรนจ์ทรี 2 มิติเหลือและยังลดเวลาในการสร้าง เรนจ์ทรี dมิติเหลืออีกด้วย ${\displaystyle O(n\log n)}$${\displaystyle O(n\log n)}$${\displaystyle O(n\log ^{d-1}n)}$

การค้นหาช่วงบนต้นไม้ช่วงจะรายงานชุดของจุดที่อยู่ภายในช่วงที่กำหนด ในการรายงานจุดที่อยู่ในช่วง [ x ₁ , x ₂ ] เราเริ่มต้นด้วยการค้นหาx ₁และx ₂ที่จุดยอดบางจุดในต้นไม้ เส้นทางการค้นหาไปยังx ₁และx ₂จะแยกออกจากกัน ให้v _splitเป็นจุดยอดสุดท้ายที่เส้นทางการค้นหาทั้งสองนี้มีร่วมกัน สำหรับทุกจุดยอดvในเส้นทางการค้นหาจากv _splitไปยังx ₁ถ้าค่าที่เก็บไว้ในvมากกว่าx ₁ให้รายงานทุกจุดในซับทรีด้านขวาของvถ้าvเป็นใบ ให้รายงานค่าที่เก็บไว้ในvถ้าค่านั้นอยู่ภายในช่วงการค้นหา ในทำนองเดียวกัน ให้รายงานจุดทั้งหมดที่เก็บไว้ในซับทรีด้านซ้ายของจุดยอดที่มีค่าน้อยกว่าx ₂ตามเส้นทางการค้นหาจากv _splitไปยังx ₂และรายงานใบของเส้นทางนี้ถ้ามันอยู่ภายในช่วงการค้นหา

เนื่องจากต้นไม้ช่วง (range tree) เป็นต้นไม้ไบนารีแบบสมดุล เส้นทางการค้นหาไปยังx ₁และx ₂จึงมีความยาวเท่ากับ การรายงานจุดทั้งหมดที่เก็บไว้ในต้นไม้ย่อยของจุดยอดสามารถทำได้ในเวลาเชิงเส้นโดยใช้ อัลกอริทึม การท่องต้นไม้ ใดๆ ก็ได้ ดังนั้น เวลาที่ใช้ในการค้นหาช่วงจึงเป็นโดยที่kคือจำนวนจุดในช่วงการค้นหา ${\displaystyle O(\log n)}$${\displaystyle O(\log n+k)}$

การค้นหาช่วงใน มิติ dมีลักษณะคล้ายกัน แทนที่จะรายงานจุดทั้งหมดที่เก็บไว้ในซับทรีของเส้นทางการค้นหา ให้ทำการค้นหาช่วงมิติ ( d −1) บนโครงสร้างที่เกี่ยวข้องของแต่ละซับทรี ในที่สุด การค้นหาช่วงมิติ 1 จะดำเนินการและจะรายงานจุดที่ถูกต้อง เนื่องจาก การค้นหามิติ dประกอบด้วย การค้นหาช่วงมิติ ( d −1) ดังนั้นเวลาที่ต้องใช้ในการ ค้นหาช่วงมิติ dคือโดยที่kคือจำนวนจุดในช่วงการค้นหา ซึ่งสามารถลดลงได้โดยใช้รูปแบบหนึ่งของ การ เรียงลำดับเศษส่วน^{[ 2 ] [ 4 ] [ 7 ]}${\displaystyle O(\log n)}$${\displaystyle O(\log ^{d}n+k)}$${\displaystyle O(\log ^{d-1}n+k)}$

• ต้นไม้k -d
• ต้นไม้เซกเมนต์
• การค้นหาช่วง

• โครงสร้างต้นไม้ช่วงและส่วนในCGALซึ่งเป็นไลบรารีอัลกอริธึมทางเรขาคณิตเชิงคำนวณ
• การบรรยายครั้งที่ 8: ต้นไม้ในเขตการกระจายพันธุ์โดย มาร์ค ฟาน เครเวลด์ เก็บถาวรไว้ที่นี่
• การสร้างแผนผังแสดงขอบเขตโดยใช้PAMซึ่งเป็นไลบรารีแผนที่เสริมแบบขนาน
• การแสดงภาพแผนผังช่วงแบบ 2 มิติโดย โจว ไคซวน