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

Max WBLT Operations ในโครงสร้างข้อมูล


Max-WBLT Operations

HBLT มี Operations: Insert, Delete, Initialize คล้าย WBLT แต่ Meld Operation ทำได้ใน Single Top-to-Bottom Pass

ข้อได้เปรียบของ WBLT

Meld ทำได้ใน Single Pass เพราะหา w values ได้ขณะลงมา (Top-down) อัปเดต w และ Swap Subtrees ได้ตามต้องการ สำหรับ HBLT หา s values ขณะลงมาไม่ได้

เพราะ Meld ทำได้ใน Single Pass Insert และ Delete จึงทำได้เร็วขึ้น Constant Factor แต่ไม่สามารถลบโหนด K ที่ Arbitrary Location ใน O(log n) ได้ เพราะ K อาจมี O(n) Ancestors ที่ w value ต้องอัปเดต ไม่เหมาะสำหรับ Mergeable Double-Ended Priority Queue