ในวิทยาการคอมพิวเตอร์ต้นไม้ช่วงเวลา (interval tree)เป็นโครงสร้างข้อมูลแบบต้นไม้สำหรับเก็บช่วงเวลาโดยเฉพาะอย่างยิ่ง ช่วยให้สามารถค้นหาช่วงเวลาทั้งหมดที่ทับซ้อนกับช่วงเวลาหรือจุดที่กำหนดได้อย่างมีประสิทธิภาพ มักใช้สำหรับการค้นหาแบบหน้าต่าง^{[ 1 ]}เช่น การค้นหาถนนทั้งหมดบนแผนที่คอมพิวเตอร์ภายในวิวพอร์ตรูปสี่เหลี่ยมผืนผ้า หรือการค้นหาองค์ประกอบที่มองเห็นได้ทั้งหมดภายในฉากสามมิติ โครงสร้างข้อมูลที่คล้ายกันคือต้นไม้ส่วน (segment tree )

วิธีแก้ปัญหาที่ง่ายที่สุดคือการเยี่ยมชมแต่ละช่วงเวลาและทดสอบว่าช่วงเวลานั้นตัดกับจุดหรือช่วงเวลาที่กำหนดหรือไม่ ซึ่งต้องใช้เวลา โดยที่คือจำนวนช่วงเวลาในชุดข้อมูล เนื่องจากแบบสอบถามอาจส่งคืนช่วงเวลาทั้งหมด ตัวอย่างเช่น หากแบบสอบถามเป็นช่วงเวลาขนาดใหญ่ที่ตัดกับช่วงเวลาทั้งหมดในชุดข้อมูล วิธีนี้จึงเหมาะสมที่สุดในเชิง อะซิมโทติก อย่างไรก็ตาม อาจพิจารณา อัลกอริทึมที่คำนึงถึงผลลัพธ์ซึ่งเวลาทำงานแสดงในรูปของ(จำนวนช่วงเวลาที่สร้างโดยแบบสอบถาม) ได้เช่นกัน ต้นไม้ช่วงเวลามีเวลาในการค้นหาและเวลาในการสร้างเริ่มต้นในขณะที่จำกัดการใช้หน่วยความจำไว้ที่หลังจากสร้างแล้ว ต้นไม้ช่วงเวลาอาจเป็นแบบไดนามิก ทำให้สามารถแทรกและลบช่วงเวลาได้อย่างมีประสิทธิภาพในเวลา หากจุดปลายของช่วงเวลาอยู่ในช่วงจำนวนเต็มขนาดเล็ก ( เช่นในช่วง) จะมีโครงสร้างข้อมูลที่เร็วกว่าและเหมาะสมที่สุด^{[ 2 ] [ 3 ]}ที่มีเวลาในการประมวลผลล่วงหน้าและเวลาในการค้นหาสำหรับการรายงานช่วงเวลาที่มีจุดค้นหาที่กำหนด (ดู^{[ 2 ]}สำหรับตัวอย่างที่ง่ายมาก) ${\displaystyle O(n)}$${\displaystyle n}$${\displaystyle m}$${\displaystyle O(\log n+m)}$${\displaystyle O(n\log n)}$${\displaystyle O(n)}$${\displaystyle O(\log n)}$${\displaystyle [1,\ldots ,O(n)]}$${\displaystyle O(n)}$${\displaystyle O(1+m)}$${\displaystyle m}$

ในกรณีง่ายๆ ช่วงเวลาจะไม่ทับซ้อนกัน และสามารถแทรกเข้าไปในต้นไม้ค้นหาแบบไบนารี อย่างง่าย และสอบถามได้ในเวลาไม่นาน อย่างไรก็ตาม หากช่วงเวลาทับซ้อนกันโดยพลการ จะไม่มีวิธีใดที่จะเปรียบเทียบช่วงเวลาสองช่วงเพื่อแทรกเข้าไปในต้นไม้ได้ เนื่องจากลำดับที่เรียงตามจุดเริ่มต้นหรือจุดสิ้นสุดอาจแตกต่างกัน วิธีการแบบง่ายๆ อาจเป็นการสร้างต้นไม้คู่ขนานสองต้น ต้นหนึ่งเรียงลำดับตามจุดเริ่มต้น และอีกต้นหนึ่งเรียงลำดับตามจุดสิ้นสุดของแต่ละช่วงเวลา วิธีนี้ช่วยให้สามารถทิ้งครึ่งหนึ่งของแต่ละต้นไม้ได้ในเวลาไม่นาน แต่ผลลัพธ์จะต้องถูกรวมเข้าด้วยกัน ซึ่งต้องใช้เวลา และทำให้ได้ผลลัพธ์การสอบถามในเวลาไม่นาน ซึ่งไม่ดีไปกว่าการค้นหาแบบใช้กำลังทั้งหมด ${\displaystyle O(\log n)}$${\displaystyle O(\log n)}$${\displaystyle O(n)}$${\displaystyle O(n+\log n)=O(n)}$

โครงสร้างต้นไม้ช่วงเวลาช่วยแก้ปัญหานี้ได้ บทความนี้อธิบายถึงการออกแบบต้นไม้ช่วงเวลาสองแบบทางเลือก ซึ่งเรียกว่าต้นไม้ช่วงเวลาแบบศูนย์กลางและต้นไม้ ช่วงเวลาเสริม

การสืบค้นข้อมูลต้องใช้เวลา โดยที่คือจำนวนช่วงเวลาทั้งหมด และคือจำนวนผลลัพธ์ที่รายงาน การสร้างข้อมูลต้องใช้เวลา และการจัดเก็บข้อมูลต้องใช้พื้นที่ ${\displaystyle O(\log n+m)}$${\displaystyle n}$${\displaystyle m}$${\displaystyle O(n\log n)}$${\displaystyle O(n)}$

เมื่อกำหนดชุดช่วงบนเส้นจำนวนแล้ว จำเป็นต้องสร้างโครงสร้างข้อมูลเพื่อให้สามารถดึงช่วงทั้งหมดที่ทับซ้อนกับช่วงหรือจุดอื่นได้อย่างมีประสิทธิภาพ ${\displaystyle n}$

ขั้นแรก นำช่วงทั้งหมดของช่วงห่างมาหารครึ่งที่(ในทางปฏิบัติ ควรเลือก เพื่อให้โครงสร้างต้นไม้มีความสมดุล) จะได้ช่วงห่างสามชุด ได้แก่ ช่วงห่างที่อยู่ทางซ้ายของ เรียกว่า, ช่วงห่างที่อยู่ทางขวาของเรียกว่า , และช่วงห่างที่ทับซ้อนกับ เรียกว่า, ${\displaystyle x_{\textrm {center}}}$${\displaystyle x_{\textrm {center}}}$${\displaystyle x_{\textrm {center}}}$${\displaystyle S_{\textrm {left}}}$${\displaystyle x_{\textrm {center}}}$${\displaystyle S_{\textrm {right}}}$${\displaystyle x_{\textrm {center}}}$${\displaystyle S_{\textrm {center}}}$

ช่วงเวลาใน และ จะถูกแบ่งซ้ำๆ ในลักษณะเดียวกันจนกว่าจะไม่มีช่วงเวลาเหลืออยู่ ${\displaystyle S_{\textrm {left}}}$${\displaystyle S_{\textrm {right}}}$

ช่วงเวลาที่ทับซ้อนกับจุดศูนย์กลางจะถูกจัดเก็บไว้ในโครงสร้างข้อมูลแยกต่างหากที่เชื่อมโยงกับโหนดในแผนผังช่วงเวลา โครงสร้างข้อมูลนี้ประกอบด้วยสองรายการ รายการหนึ่งบรรจุช่วงเวลาทั้งหมดที่เรียงลำดับตามจุดเริ่มต้น และอีกรายการหนึ่งบรรจุช่วงเวลาทั้งหมดที่เรียงลำดับตามจุดสิ้นสุด ${\displaystyle S_{\textrm {center}}}$

ผลลัพธ์ที่ได้คือ โครงสร้าง ข้อมูลแบบต้นไม้ไบนารีโดยแต่ละโหนดจะเก็บข้อมูลดังต่อไปนี้:

• จุดศูนย์กลาง
• ตัวชี้ไปยังโหนดอื่นที่ประกอบด้วยช่วงเวลาทั้งหมดที่อยู่ทางซ้ายของจุดศูนย์กลาง
• ตัวชี้ไปยังโหนดอื่นที่ประกอบด้วยช่วงเวลาทั้งหมดที่อยู่ทางด้านขวาของจุดศูนย์กลาง
• ช่วงเวลาทั้งหมดที่ทับซ้อนกับจุดศูนย์กลาง เรียงลำดับตามจุดเริ่มต้น
• ช่วงเวลาทั้งหมดที่ทับซ้อนกับจุดกึ่งกลาง เรียงลำดับตามจุดสิ้นสุด

โครงสร้างข้อมูลแบบต้นไม้ช่วง (Interval tree) ช่วยให้สามารถคำนวณช่วงทั้งหมดที่ทับซ้อนกับข้อมูลป้อนเข้าใดๆ ได้อย่างรวดเร็ว

งานนี้คือการหาช่วงเวลาทั้งหมดในต้นไม้ที่ทับซ้อนกับจุดที่กำหนดต้นไม้จะถูกสำรวจด้วยอัลกอริทึมแบบเรียกซ้ำที่คล้ายกับที่ใช้ในการสำรวจต้นไม้ไบนารีแบบดั้งเดิม แต่มีตรรกะเพิ่มเติมเพื่อรองรับการค้นหาช่วงเวลาที่ทับซ้อนกับจุด "ศูนย์กลาง" ที่แต่ละโหนด ${\displaystyle x}$

สำหรับแต่ละโหนดในต้นไม้ ค่าจะถูกเปรียบเทียบกับ ค่ากึ่งกลางที่ใช้ในการสร้างโหนดข้างต้น ถ้าน้อยกว่า จะพิจารณาชุดช่วงซ้ายสุด ถ้า มากกว่า จะพิจารณา ชุดช่วงขวาสุด ${\displaystyle x}$${\displaystyle x_{\textrm {center}}}$${\displaystyle x}$${\displaystyle x_{\textrm {center}}}$${\displaystyle S_{\textrm {left}}}$${\displaystyle x}$${\displaystyle x_{\textrm {center}}}$${\displaystyle S_{\textrm {right}}}$

ขณะที่แต่ละโหนดถูกประมวลผลในระหว่างการสำรวจต้นไม้จากรากไปยังใบ ช่วงต่างๆ ในโหนดนั้น ก็จะถูกประมวลผลไปด้วย หากน้อยกว่า ช่วงทั้งหมดใน จะต้องสิ้นสุดหลังจากมิฉะนั้นช่วงเหล่านั้นจะไม่ทับซ้อนกัน ดังนั้นจึงจำเป็นต้องค้นหาเฉพาะช่วงในที่เริ่มต้นก่อน เท่านั้น สามารถตรวจสอบ รายการที่สร้างขึ้นแล้วได้ เนื่องจากเฉพาะจุดเริ่มต้นของช่วงเท่านั้นที่เกี่ยวข้องในสถานการณ์นี้ รายการจึงสามารถเรียงลำดับตามจุดเริ่มต้นได้ หากพบตัวเลขที่ใกล้เคียงที่สุดซึ่งไม่มากกว่า ในรายการนี้ ช่วงทั้งหมดตั้งแต่ต้นรายการจนถึงจุดที่พบนั้นจะทับซ้อนกันเนื่องจากเริ่มต้นก่อนและสิ้นสุดหลังจาก(เนื่องจากทับซ้อนกับ ซึ่งมากกว่า) ดังนั้นช่วงในรายการจึงสามารถแจงนับได้จนกว่าค่าเริ่มต้นจะเกิน ${\displaystyle S_{\textrm {center}}}$${\displaystyle x}$${\displaystyle x_{\textrm {center}}}$${\displaystyle S_{\textrm {center}}}$${\displaystyle x}$${\displaystyle x_{\textrm {center}}}$${\displaystyle S_{\textrm {center}}}$${\displaystyle x}$${\displaystyle S_{\textrm {center}}}$${\displaystyle x}$${\displaystyle x}$${\displaystyle x}$${\displaystyle x}$${\displaystyle x_{\textrm {center}}}$${\displaystyle x}$${\displaystyle x}$

ในทำนองเดียวกัน ถ้ามีค่ามากกว่า ช่วงเวลาทั้งหมดใน จะต้องเริ่มต้นก่อนดังนั้นช่วงเวลาที่สิ้นสุดหลังจากสามารถหาได้โดยใช้รายการที่เรียงลำดับตามการสิ้นสุดของช่วงเวลา ${\displaystyle x}$${\displaystyle x_{\textrm {center}}}$${\displaystyle S_{\textrm {center}}}$${\displaystyle x}$${\displaystyle x}$

หากตรงกันทุกประการ ช่วงเวลาทั้งหมดในนั้นสามารถถูกเพิ่มเข้าไปในผลลัพธ์ได้โดยไม่ต้องประมวลผลเพิ่มเติม และการท่องไปในโครงสร้างต้นไม้สามารถหยุดได้ ${\displaystyle x}$${\displaystyle x_{\textrm {center}}}$${\displaystyle S_{\textrm {center}}}$

เพื่อให้ช่วงผลลัพธ์ตัดกับช่วงการค้นหาจะต้องเป็นไปตามเงื่อนไขข้อใดข้อหนึ่งต่อไปนี้: ${\displaystyle r}$${\displaystyle q}$

• จุดเริ่มต้นหรือจุดสิ้นสุดของอยู่ในหรือ${\displaystyle r}$${\displaystyle q}$
• ${\displaystyle r}$ปิดล้อมอย่างสมบูรณ์${\displaystyle q}$

ขั้นแรก เราจะค้นหาช่วงเวลาทั้งหมดที่มีจุดเริ่มต้นและ/หรือจุดสิ้นสุดอยู่ภายในโดยใช้โครงสร้างต้นไม้ที่สร้างขึ้นแยกต่างหาก ในกรณีหนึ่งมิติ เราสามารถใช้ต้นไม้ค้นหาที่มีจุดเริ่มต้นและจุดสิ้นสุดทั้งหมดในชุดช่วงเวลา โดยแต่ละจุดมีตัวชี้ไปยังช่วงเวลาที่สอดคล้องกัน การค้นหาแบบไบนารีในช่วงเวลาสำหรับจุดเริ่มต้นและจุดสิ้นสุดจะเปิดเผยจุดต่ำสุดและจุดสูงสุดที่ต้องพิจารณา แต่ละจุดภายในช่วงนี้จะอ้างอิงถึงช่วงเวลาที่ทับซ้อนกันและจะถูกเพิ่มลงในรายการผลลัพธ์ ต้องระมัดระวังเพื่อหลีกเลี่ยงการซ้ำซ้อน เนื่องจากช่วงเวลาอาจเริ่มต้นและสิ้นสุดภายในช่วงเวลาเดียวกันได้ สามารถทำได้โดยใช้แฟล็กไบนารีบนแต่ละช่วงเวลาเพื่อทำเครื่องหมายว่าได้เพิ่มลงในชุดผลลัพธ์แล้วหรือไม่ ${\displaystyle q}$${\displaystyle O(\log n)}$${\displaystyle q}$${\displaystyle q}$${\displaystyle q}$

สุดท้าย เราต้องหาช่วงที่ล้อมรอบโดยการหาช่วงเหล่านี้ เราเลือกจุดใดก็ได้ภายในและใช้อัลกอริธึมข้างต้นเพื่อหาช่วงทั้งหมดที่ตัดกับจุดนั้น (โดยต้องระมัดระวังในการลบช่วงที่ซ้ำกันออก) ${\displaystyle q}$${\displaystyle q}$

โครงสร้างข้อมูลแบบต้นไม้ช่วงเวลาสามารถขยายไปสู่มิติที่สูงขึ้นได้โดยใช้เวลาและพื้นที่ ในการค้นหาและสร้างข้อมูลเท่าเดิม${\displaystyle N}$${\displaystyle O(n\log n)}$

ขั้นแรก จะสร้างโครงสร้าง ต้นไม้ช่วงในมิติต่างๆ เพื่อให้สามารถดึงข้อมูลช่วงทั้งหมดที่มีจุดเริ่มต้นและจุดสิ้นสุดอยู่ภายในขอบเขตการค้นหาได้อย่างมีประสิทธิภาพเมื่อพบช่วงที่สอดคล้องกันแล้ว สิ่งที่เหลืออยู่ก็คือช่วงที่ล้อมรอบขอบเขตในมิติใดมิติหนึ่ง เพื่อค้นหาส่วนที่ทับซ้อนกันเหล่านี้ จะสร้างโครงสร้างต้นไม้ช่วง และทำการค้นหาแกนที่ตัดกันสำหรับแต่ละส่วน ตัวอย่างเช่น ในสองมิติ ด้านล่างของสี่เหลี่ยมจัตุรัส (หรือเส้นแนวนอนอื่นๆ ที่ตัดกับ) จะถูกค้นหาในโครงสร้างต้นไม้ช่วงที่สร้างขึ้นสำหรับแกนแนวนอน ในทำนองเดียวกัน ด้านซ้าย (หรือเส้นแนวตั้งอื่นๆ ที่ตัดกับ) จะถูกค้นหาในโครงสร้างต้นไม้ช่วงที่สร้างขึ้นบนแกนแนวตั้ง ${\displaystyle N}$${\displaystyle R}$${\displaystyle N}$${\displaystyle R}$${\displaystyle R}$${\displaystyle R}$${\displaystyle R}$

ต้นไม้ช่วงเวลาแต่ละต้นยังต้องการส่วนเพิ่มเติมสำหรับมิติที่สูงขึ้นด้วย ในแต่ละโหนดที่เราสำรวจในต้นไม้จะมีการเปรียบเทียบ เพื่อหาส่วนที่ทับซ้อนกัน แทนที่จะใช้รายการจุดที่เรียงลำดับสองรายการดังที่ใช้ในกรณีหนึ่งมิติ จะมีการสร้างต้นไม้ช่วงขึ้นมา ซึ่งช่วยให้สามารถดึงข้อมูลจุดทั้งหมดใน บริเวณที่ทับซ้อนกันได้ อย่างมีประสิทธิภาพ${\displaystyle x}$${\displaystyle S_{\textrm {center}}}$${\displaystyle S_{\textrm {center}}}$${\displaystyle R}$

หากหลังจากลบช่วงเวลาออกจากต้นไม้แล้ว โหนดที่บรรจุช่วงเวลานั้นไม่มีช่วงเวลาอื่นเหลืออยู่ โหนดนั้นก็สามารถลบออกจากต้นไม้ได้เช่นกัน ซึ่งกระบวนการนี้ซับซ้อนกว่าการลบข้อมูลในต้นไม้ไบนารีแบบปกติ

ช่วงเวลาหนึ่งอาจทับซ้อนกับจุดศูนย์กลางของหลายโหนดในต้นไม้ เนื่องจากแต่ละโหนดจะเก็บช่วงเวลาที่ทับซ้อนกับมัน โดยช่วงเวลาทั้งหมดจะอยู่ทางซ้ายของจุดศูนย์กลางในซับทรีด้านซ้าย และเช่นเดียวกันสำหรับซับทรีด้านขวา ดังนั้นช่วงเวลาแต่ละช่วงจึงถูกเก็บไว้ในโหนดที่อยู่ใกล้กับรากมากที่สุดจากชุดของโหนดที่จุดศูนย์กลางของมันทับซ้อนอยู่

การดำเนินการลบตามปกติในต้นไม้ไบนารี (ในกรณีที่โหนดที่ถูกลบมีลูกสองตัว) เกี่ยวข้องกับการเลื่อนโหนดที่อยู่ห่างจากใบขึ้นไปอยู่ในตำแหน่งของโหนดที่ถูกลบ (โดยปกติจะเป็นลูกซ้ายสุดของต้นไม้ย่อยด้านขวา หรือลูกขวาสุดของต้นไม้ย่อยด้านซ้าย)

ผลจากการเลื่อนขั้นนี้ โหนดบางส่วนที่อยู่เหนือโหนดที่ถูกเลื่อนขั้นจะกลายเป็นโหนดลูกของโหนดนั้น จำเป็นต้องค้นหาช่วงเวลาที่ทับซ้อนกับโหนดที่ถูกเลื่อนขั้นในโหนดเหล่านั้น และย้ายช่วงเวลาเหล่านั้นเข้าไปในโหนดที่ถูกเลื่อนขั้น ผลที่ตามมาคือ อาจทำให้เกิดโหนดว่างใหม่ ซึ่งจะต้องถูกลบออกโดยใช้อัลกอริทึมเดียวกันอีกครั้ง

ปัญหาเดียวกันกับที่ส่งผลต่อการลบก็ส่งผลต่อการหมุนโหนดด้วยเช่นกัน การหมุนโหนดต้องรักษาสมบัติคงที่ที่ว่าโหนดจะถูกจัดเก็บไว้ใกล้กับรากมากที่สุดเท่าที่จะเป็นไปได้

อีกวิธีหนึ่งในการแสดงช่วงเวลาได้รับการอธิบายไว้ในCormen et al. (2009 , ส่วนที่ 14.3: แผนผังช่วงเวลา, หน้า 348–354)

ทั้งการแทรกและการลบต้องใช้เวลา โดยที่คือจำนวนช่วงเวลาทั้งหมดในโครงสร้างต้นไม้ก่อนที่จะดำเนินการแทรกหรือลบ ${\displaystyle O(\log n)}$${\displaystyle n}$

สามารถสร้างต้นไม้เสริมได้จากต้นไม้เรียงลำดับแบบง่าย เช่นต้นไม้ค้นหาแบบไบนารีหรือต้นไม้ค้นหาแบบไบนารีที่ปรับสมดุลตัวเองโดยเรียงลำดับตามค่า 'ต่ำ' ของช่วง จากนั้นจะเพิ่มคำอธิบายประกอบพิเศษให้กับทุกโหนด โดยบันทึกค่าสูงสุดด้านบนในบรรดาช่วงทั้งหมดจากโหนดนี้ลงไป การรักษาคุณลักษณะนี้เกี่ยวข้องกับการอัปเดตบรรพบุรุษทั้งหมดของโหนดจากล่างขึ้นบนทุกครั้งที่มีการเพิ่มหรือลบโหนด ซึ่งใช้เวลาเพียง O( h ) ขั้นตอนต่อการเพิ่มหรือลบโหนด โดยที่hคือความสูงของโหนดที่เพิ่มหรือลบในต้นไม้ หากมีการหมุนต้นไม้ระหว่างการแทรกและการลบ โหนดที่ได้รับผลกระทบอาจต้องได้รับการอัปเดตด้วยเช่นกัน

ในปัจจุบันเป็นที่ทราบกันดีว่าช่วงเวลาสองช่วงและจะทับซ้อนกันก็ต่อเมื่อทั้งและเท่านั้น เมื่อค้นหาโหนดในต้นไม้ที่ทับซ้อนกับช่วงเวลาที่กำหนด คุณสามารถข้ามขั้นตอนต่อไปนี้ได้ทันที: ${\displaystyle A}$${\displaystyle B}$${\displaystyle A_{\textrm {low}}\leq B_{\textrm {high}}}$${\displaystyle A_{\textrm {high}}\geq B_{\textrm {low}}}$

• โหนดทั้งหมดทางด้านขวาของโหนดที่มีค่าต่ำสุดเกินช่วงสิ้นสุดที่กำหนด
• โหนดทั้งหมดที่มีค่าสูงสุดต่ำกว่าจุดเริ่มต้นของช่วงเวลาที่กำหนด

ประสิทธิภาพอาจดีขึ้นหากโครงสร้างต้นไม้หลีกเลี่ยงการท่องไปในเส้นทางที่ไม่จำเป็น ซึ่งอาจเกิดขึ้นเมื่อเพิ่มช่วงเวลาที่เคยมีอยู่แล้ว หรือลบช่วงเวลาที่ไม่มีอยู่จริง

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

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

กุญแจสำคัญของแต่ละโหนดคือช่วงเวลานั้นเอง ดังนั้นโหนดจึงถูกจัดเรียงตามค่าต่ำสุดก่อนแล้วจึงเรียงตามค่าสูงสุด และค่าของแต่ละโหนดคือจุดสิ้นสุดของช่วงเวลานั้น:

public void add ( Interval i ) { put ( i , i . getEnd ()); }

ในการค้นหาช่วงเวลา จะทำการสำรวจโครงสร้างต้นไม้ โดยใช้คีย์ ( n.getKey()) และค่าสูงสุด ( n.getValue()) เพื่อละเว้นกิ่งก้านใดๆ ที่ไม่สามารถทับซ้อนกับคำค้นหาได้ กรณีที่ง่ายที่สุดคือการค้นหาแบบจุด:

// ค้นหาช่วงเวลาทั้งหมดที่มี "p" โดยเริ่มจากโหนด "n" และเพิ่มช่วงเวลาที่ตรงกันลงในรายการ "result" public void search ( IntervalNode n , Point p , List < Interval > result ) { // ไม่ค้นหาโหนดที่ไม่มีอยู่จริงif ( n == null ) return ;// ถ้า p อยู่ทางขวาของจุดขวาสุดของช่วงใดๆ// ในโหนดนี้และโหนดลูกทั้งหมด จะไม่มีการจับคู่ใดๆif ( p . compareTo ( n . getValue ()) > 0 ) return ;// ค้นหาลูกทางซ้ายsearch ( n . getLeft (), p , result );// ตรวจสอบโหนดนี้หาก( n.getKey (). contains ( p )) ผลลัพธ์. add ( n.getKey ( ) ) ;// ถ้า p อยู่ทางซ้ายของจุดเริ่มต้นของช่วงเวลานี้ // แสดงว่า p ไม่สามารถอยู่ในโหนดลูกทางขวาได้ถ้า( p.compareTo ( n.getKey ( ). getStart ( ) ) < 0 ) ให้คืนค่า;// มิ เช่นนั้น ให้ค้นหาลูกที่ถูกต้องsearch(n.getRight ( ) , p , result ) ; }

ที่ไหน

a.compareTo(b)ส่งคืนค่าลบหาก a < b

a.compareTo(b)ส่งคืนค่าศูนย์หาก a = b

a.compareTo(b)ส่งคืนค่าบวกหาก a > b

โค้ดสำหรับค้นหาช่วงเวลาจะคล้ายกัน ยกเว้นการตรวจสอบตรงกลาง:

// ตรวจสอบโหนดนี้หาก( n.getKey (). overlapsWith ( i )) ผลลัพธ์. add ( n.getKey ( ) ) ;

overlapsWith()มีนิยามดังนี้:

public boolean overlapsWith ( Interval other ) { return start.compareTo ( other.getEnd ( ) ) < = 0 && end.compareTo ( other.getStart ( ) ) > = 0 ; }​​

โครงสร้างข้อมูลแบบต้นไม้เสริมสามารถขยายไปยังมิติที่สูงขึ้นได้โดยการวนรอบมิติในแต่ละระดับของต้นไม้ ตัวอย่างเช่น สำหรับสองมิติ ระดับคี่ของต้นไม้อาจมีช่วงสำหรับ พิกัด xในขณะที่ระดับคู่จะมีช่วงสำหรับ พิกัด yวิธีการนี้จะแปลงโครงสร้างข้อมูลจากต้นไม้ไบนารีเสริมไปเป็นต้นไม้ kd เสริม ซึ่งทำให้ขั้นตอนวิธีปรับสมดุลสำหรับการแทรกและการลบมีความซับซ้อนมากขึ้นอย่างมาก

วิธีแก้ปัญหาที่ง่ายกว่าคือการใช้ต้นไม้ช่วงซ้อนกัน ขั้นแรก สร้างต้นไม้โดยใช้ช่วงของ พิกัด yจากนั้น สำหรับแต่ละโหนดในต้นไม้ ให้เพิ่มต้นไม้ช่วงอีกต้นหนึ่งบน ช่วง xสำหรับองค์ประกอบทั้งหมดที่มี ช่วง yเดียวกันกับช่วง y ของโหนดนั้น

ข้อดีของวิธีการนี้คือสามารถขยายไปยังมิติจำนวนเท่าใดก็ได้โดยใช้ฐานรหัสเดียวกัน

ในตอนแรก ค่าใช้จ่ายเพิ่มเติมของโครงสร้างต้นไม้ซ้อนกันอาจดูเหมือนสูงเกินไป แต่โดยปกติแล้วจะไม่เป็นเช่นนั้น เช่นเดียวกับวิธีแก้ปัญหาแบบไม่ซ้อนกันที่กล่าวถึงก่อนหน้านี้ จำเป็นต้องใช้โหนดหนึ่งโหนดต่อ พิกัด xทำให้ได้จำนวนโหนดเท่ากันสำหรับทั้งสองวิธี ค่าใช้จ่ายเพิ่มเติมเพียงอย่างเดียวคือค่าใช้จ่ายของโครงสร้างต้นไม้ซ้อนกัน หนึ่งโครงสร้างต่อช่วงแนวตั้ง โครงสร้างนี้โดยปกติจะมีขนาดเล็กมาก ประกอบด้วยเพียงตัวชี้ไปยังโหนดราก และอาจรวมถึงจำนวนโหนดและความลึกของต้นไม้ด้วย

ต้นไม้แบบเน้นค่ามัธยฐานหรือความยาวนั้นคล้ายกับต้นไม้แบบเสริม แต่มีความสมมาตร โดยต้นไม้ค้นหาแบบไบนารีจะเรียงลำดับตามจุดมัธยฐานของช่วง ในแต่ละโหนดจะมีฮีปแบบไบนารี ที่เน้นค่าสูงสุด เรียงลำดับตามความยาวของช่วง (หรือครึ่งหนึ่งของความยาว) นอกจากนี้ เรายังเก็บค่าต่ำสุดและค่าสูงสุดที่เป็นไปได้ของต้นไม้ย่อยไว้ในแต่ละโหนด (จึงทำให้เกิดความสมมาตร)

โดยใช้เพียงค่าเริ่มต้นและค่าสิ้นสุดของช่วงเวลาสองช่วงสำหรับการทดสอบการทับซ้อนสามารถทำได้ดังนี้: ${\displaystyle \left(a_{i},b_{i}\right)}$${\displaystyle i=0,1}$

${\displaystyle a_{0}<b_{1}}$และ${\displaystyle a_{1}<b_{0}}$

สามารถทำให้ง่ายขึ้นได้โดยใช้ผลบวกและผลต่าง:

${\displaystyle s_{i}=a_{i}+b_{i}}$

${\displaystyle d_{i}=b_{i}-a_{i}}$

ซึ่งจะลดการทดสอบการทับซ้อนเหลือเพียง:

${\displaystyle \left|s_{1}-s_{0}\right|<d_{0}+d_{1}}$

การเพิ่มช่วงเวลาใหม่ลงในต้นไม้จะเหมือนกับการเพิ่มช่วงเวลาในต้นไม้ค้นหาแบบไบนารีโดยใช้ค่ามัธยฐานเป็นคีย์ เราจะเพิ่มข้อมูลลงในฮีปไบนารีที่เชื่อมโยงกับโหนดนั้น และอัปเดตค่าต่ำสุดและสูงสุดที่เป็นไปได้ที่เชื่อมโยงกับโหนดระดับสูงกว่าทั้งหมด ${\displaystyle d_{i}}$

เราจะใช้สำหรับช่วงเวลาการค้นหา และสำหรับคีย์ของโหนด (เมื่อเทียบกับของช่วงเวลา) ${\displaystyle a_{q},b_{q},m_{q},d_{q}}$${\displaystyle M_{n}}$${\displaystyle m_{i}}$

เริ่มต้นจากโหนดราก ในแต่ละโหนด เราจะตรวจสอบก่อนว่าช่วงเวลาการค้นหาของเราทับซ้อนกับโครงสร้างย่อยของโหนดนั้นได้หรือไม่ โดยใช้ค่าต่ำสุดและสูงสุดของโหนด (หากไม่ทับซ้อน เราจะไม่ดำเนินการต่อสำหรับโหนดนั้น)

จากนั้นเราจะคำนวณหาช่วงเวลาภายในโหนดนี้ (ไม่ใช่โหนดลูก) ที่ทับซ้อนกับช่วงเวลาการค้นหา (โดยทราบว่า): ${\displaystyle \min \left\{d_{i}\right\}}$${\displaystyle m_{i}=M_{n}}$

${\displaystyle \min \left\{d_{i}\right\}=\left|m_{q}-M_{n}\right|-d_{q}}$

และทำการค้นหาในฮีปไบนารีเพื่อหาค่าที่มากกว่า${\displaystyle d_{i}}$${\displaystyle \min \left\{d_{i}\right\}}$

จากนั้นเราจะดำเนินการกับโหนดลูกทั้งด้านซ้ายและด้านขวา โดยทำเช่นเดียวกัน

ในกรณีที่เลวร้ายที่สุด เราต้องสแกนทุกโหนดของต้นไม้ค้นหาแบบไบนารี แต่เนื่องจากการค้นหาแบบฮีปไบนารีเป็นวิธีที่ดีที่สุด จึงยอมรับได้ (ปัญหา 2 มิติไม่สามารถเป็นวิธีที่ดีที่สุดได้ทั้งสองมิติ)

คาดว่าอัลกอริทึมนี้จะเร็วกว่าโครงสร้างต้นไม้ช่วงเวลาแบบดั้งเดิม (ต้นไม้เสริม) สำหรับการค้นหา การเพิ่มองค์ประกอบจะช้าลงเล็กน้อยในทางปฏิบัติ แม้ว่าลำดับการเติบโตจะเหมือนกันก็ตาม

• CGAL: Computational Geometry Algorithms Library ในภาษา C++มีการใช้งาน Range Tree ที่มีประสิทธิภาพสูง
• Boost.Iclนำเสนอการใช้งานเซตช่วงเวลาและแผนที่ช่วงเวลาในภาษา C++
• IntervalTree (Python) - โครงสร้างข้อมูลแบบ Interval Tree ที่มีศูนย์กลางอยู่ที่การปรับสมดุลด้วย AVL และใช้งานร่วมกับ Tagged Intervals ได้
• Interval Tree (C#) - โครงสร้าง Interval Tree ที่ได้รับการปรับปรุง พร้อมการปรับสมดุลด้วย AVL
• Interval Tree (Ruby) - โครงสร้างข้อมูลแบบ Interval Tree ที่มีศูนย์กลางอยู่ที่ค่าคงที่ ไม่สามารถเปลี่ยนแปลงได้ และใช้งานร่วมกับ Tagged Intervals ได้
• IntervalTree (Java) - โครงสร้างข้อมูลแบบ Interval Tree ที่ได้รับการปรับปรุง พร้อมการปรับสมดุลด้วย AVL รองรับการซ้อนทับ การค้นหา อินเทอร์เฟซ Collection และ Interval ที่เชื่อมโยงกับ ID
• Tree::Interval::Fast (Perl/C) - การสร้างและจัดการโครงสร้างต้นไม้แบบช่วง (Interval Tree) อย่างมีประสิทธิภาพ