อัลกอริธึมการปรับสมดุล

อัลกอริธึมการปรับสมดุลสามารถทำได้ดังนี้ -

อัลกอริธึม Day-Stout-Warren

เราสามารถใช้วิธีปรับสมดุลได้จริงโดยใช้อัลกอริทึม Day-Stout-Warren ซึ่งเป็นจำนวนโหนดเชิงเส้นตรง

ต่อไปนี้คือการนำเสนอของอัลกอริทึม DSW พื้นฐานในโค้ดหลอก

• มีการจัดสรรโหนดที่เรียกว่า "รากเทียม" และทำให้รากที่แท้จริงของต้นไม้เป็นลูกที่ถูกต้องของรากเทียม
• เรียกฟังก์ชัน tree-to-vine เพื่อแปลง tree เป็น sorted linked list โดยมี pseudo-root เป็นอาร์กิวเมนต์
• เรียกฟังก์ชัน vine-to-tree เพื่อแปลงรายการที่เชื่อมโยงที่เรียงลำดับแล้วเป็นทรีอีกครั้งโดยใช้รากเทียมและขนาด (จำนวนองค์ประกอบ) ของต้นไม้เป็นอาร์กิวเมนต์
• ควรสร้างรากที่แท้จริงของต้นไม้ให้เท่ากับลูกที่ถูกต้องของรากเทียม
• ในที่สุด pseudo-root ควรถูกกำจัด

แผนผัง "คัดลอกเมื่อเขียน"

หากเราสามารถทนต่อการขาดความเป็นเส้นตรงได้ (เช่น เราเขียนค่า แต่เมื่อเราค้นหาทันทีหลังจากไม่พบ มันก็จะพบในที่สุด แต่หลังจาก 100 มิลลิวินาที-10 วินาที) สามารถใช้แผนผัง "คัดลอกเมื่อเขียน" ได้:การเขียนทั้งหมดดำเนินการโดยเธรดเดียว (ด้วยการปรับสมดุล) และเราคัดลอกแผนผังเป็นระยะเป็นสำเนาแบบอ่านอย่างเดียวที่สามารถนำมาใช้โดยการอ่านเธรดโดยไม่มีการควบคุมการทำงานพร้อมกัน เราจำเป็นต้องเผยแพร่แบบอะตอมมิก

รายการข้ามพร้อมกัน

อีกทางเลือกหนึ่งคือการใช้รายการข้ามที่เกิดขึ้นพร้อมกัน:ให้เวลาการค้นหา/ลบ/แทรกกรณีเฉลี่ยลอการิทึม และสามารถขนานกันได้ง่ายขึ้น มีการใช้งานแบบปลอดล็อกมาตรฐานสำหรับ Java หากคุณติดตั้งใช้งาน เราสามารถรับข้อมูลเพิ่มเติมเกี่ยวกับรายการข้ามพร้อมกันและแผนผังการค้นหาที่สมดุลได้ที่นี่ โดยเฉพาะอย่างยิ่ง เราสามารถรับการกล่าวถึงต้นไม้สีซึ่งแสดงเป็นแผนผังการค้นหาแบบไบนารีที่ได้รับการปรับให้เหมาะสมสำหรับการปรับสมดุลพร้อมกัน