Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> การเขียนโปรแกรม

แผนผังช่วงเวลาในโครงสร้างข้อมูล


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

ช่วงเวลานั้นเป็นช่วง ดังนั้นหากช่วงหนึ่งเขียนเป็น [a, b] แสดงว่าช่วงเริ่มต้นจาก a และสิ้นสุดที่ b

ตอนนี้ สมมติว่ามีช่วงเวลา [10, 20] จึงมีค่าช่วงสามค่า อันแรกคือ -∞ ถึง 10, 10 ถึง 20 และสุดท้ายคือ 20 ถึง ∞

แผนผังช่วงเวลาในโครงสร้างข้อมูล

ตอนนี้ สมมติว่าเราจะสร้างช่วงที่สองจาก [15, 25] มันจะเป็นเช่นนี้ -

แผนผังช่วงเวลาในโครงสร้างข้อมูล

ทำช่วงอื่นจาก [18, 22] ดังนั้นจะเป็นเช่น -

แผนผังช่วงเวลาในโครงสร้างข้อมูล

จึงมีช่วงและช่วงย่อยต่างกัน พวกเขาเป็นเหมือนด้านล่าง

ชื่อช่วงเวลา ช่วงช่วง ช่วงย่อย
ช่วงที่ 1 [10, 20] [10, 15], [15, 18], [18, 20]
ช่วงที่ 2 [15, 25] [15, 18], [18, 20], [20, 22], [22, 25]
ช่วงที่ 3 [18, 22] [18, 20], [20, 22]

เราสามารถสร้างแผนผังช่วงเวลาได้จากข้อมูลนี้ ช่วงเวลาย่อยจะอยู่ภายในแผนผังย่อย

ในแผนผังช่วงเวลา โหนดลีฟทุกโหนดจะแสดงทุกช่วงเบื้องต้น ด้านบนของใบไม้เหล่านี้ คือการสร้างไบนารีทรีที่สมบูรณ์

แผนผังช่วงเวลาในโครงสร้างข้อมูล