home

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

การลบโหนด Arbitrary จาก Max HBLT ในโครงสร้างข้อมูล

กฎการลบโหนด Arbitrary

การลบโหนด Arbitrary จาก Max/Min HBLT ไม่ใช่ Standard Operation สำหรับ Priority Queue หรือ HBLT ถ้าต้องการลบโหนด K:

  1. Detach Subtree ที่ Root = K ออกจากต้นไม้ แทนที่ด้วย Meld ของ Subtrees ของ K
  2. อัปเดต s Values จากเส้นทาง K ถึง Root และ Swap Subtrees ตามเส้นทางนั้นเพื่อรักษา HBLT Property

การอัปเดต s Values

ต้องการ Parent Pointer สำหรับแต่ละโหนด การอัปเดตหยุดเมื่อ s Value ไม่เปลี่ยน s Values ที่เปลี่ยนต้องเป็น Ascending Sequence เพราะแต่ละโหนดต้องมากกว่าก่อนหน้า 1 เนื่องจาก Max s Value = O(log n) และ s > 0 สูงสุดเจอ O(log n) โหนด แต่ละโหนด O(1) รวม Complexity = O(log n)