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

การหลอม HLT สูงสุดสองตัวในโครงสร้างข้อมูล


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

สมมติว่า A มีรากที่ใหญ่กว่า และนั่นคือทรีย่อยด้านซ้ายคือ L สมมติว่า C เป็น HBLT สูงสุด ซึ่งเป็นผลมาจากการรวมทรีย่อยด้านขวาของ A และ HBLT B เข้าด้วยกัน HBLT สุดท้ายจะมี A เป็นรูท และ L และ C เป็นทรีย่อย หากค่า s ของ L น้อยกว่า C แล้ว C ก็คือทรีย่อยด้านซ้าย มิฉะนั้น L จะถูกปล่อยออกจากทรีย่อย

สมมติว่าเรามีสององค์ประกอบเช่น -

การหลอม HLT สูงสุดสองตัวในโครงสร้างข้อมูล

เราต้องการที่จะรวมพวกเขา (โหนดถือค่า ตัวเลขภายนอกโหนดเป็นค่า s สำหรับโหนดที่เกี่ยวข้อง)

ตอนนี้เรามาดูวิธีการผสมกัน สมมติว่าเพิ่ม 7 เป็นลูกด้านขวาของ 9 แต่ที่นี่ s(L) ของ 9 คือ 0 และ s(R) ของ 9 คือ 1 ดังนั้นจะถูกสลับ และ 7 จะเป็นลูกที่ถูกต้อง

การหลอม HLT สูงสุดสองตัวในโครงสร้างข้อมูล

ตัวอย่างอื่น

การหลอม HLT สูงสุดสองตัวในโครงสร้างข้อมูล

เพิ่ม HBLT ที่เล็กกว่าไว้ชั่วคราวทางด้านขวาของอันที่ใหญ่กว่า

การหลอม HLT สูงสุดสองตัวในโครงสร้างข้อมูล

นี่ไม่ใช่การรักษาคุณสมบัติของ HBLT

การหลอม HLT สูงสุดสองตัวในโครงสร้างข้อมูล