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

การดำเนินการ WBLT สูงสุดในโครงสร้างข้อมูล


ที่นี่เราจะมาดูกันว่าการดำเนินการ Max-WBLT ต่างกันอย่างไร HBLT มีการดำเนินการที่แตกต่างกัน เช่น การแทรก การลบ และการเริ่มต้น พวกมันค่อนข้างคล้ายกับ WBLT เช่นกัน อย่างไรก็ตาม การทำ Meld สามารถทำได้ในการผ่านจากบนลงล่างเพียงครั้งเดียว

WBLT สามารถดำเนินการผสมผ่านครั้งเดียวได้ เพราะเราสามารถหาค่า w ได้ระหว่างทางลง เราสามารถอัปเดตค่า w และสลับแผนผังย่อยได้ตามความจำเป็น สำหรับ HBLT เราไม่พบค่า s ระหว่างทางลงไปที่ต้นไม้

เนื่องจากสามารถทำได้ในการผ่านจากบนลงล่างเพียงครั้งเดียว ดังนั้นการแทรกและการลบจึงสามารถทำได้อย่างมีประสิทธิภาพเช่นกัน ดังนั้นการแทรกและการลบจึงเร็วขึ้นด้วยปัจจัยคงที่ ที่นี่เราไม่สามารถลบองค์ประกอบในโหนด K ที่ตั้งอยู่โดยพลการในเวลา O(log n) เหตุผลเบื้องหลังว่า โหนด K อาจมีบรรพบุรุษ O(n) ซึ่งค่า w จะได้รับการอัปเดต จึงไม่เป็นผลดีสำหรับแอปพลิเคชันคิวลำดับความสำคัญแบบดับเบิ้ลเอนด์ที่ผสานได้