การหมุน AVL ใน Javascript

เพื่อสร้างสมดุลให้ตัวเอง ต้นไม้ AVL อาจทำการหมุนสี่ประเภทต่อไปนี้ -

• หมุนซ้าย
• หมุนขวา
• หมุนซ้าย-ขวา
• หมุนซ้าย-ขวา

การหมุนสองรอบแรกเป็นการหมุนครั้งเดียว และการหมุนสองครั้งถัดไปจะเป็นการหมุนสองครั้ง ในการมีต้นไม้ที่ไม่สมดุล อย่างน้อยที่สุดเราก็ต้องมีต้นไม้สูง 2 ต้น ด้วยต้นไม้ง่ายๆ นี้ เรามาทำความเข้าใจกันทีละต้น

หมุนซ้าย

หากต้นไม้ไม่สมดุล เมื่อโหนดถูกแทรกลงในทรีย่อยด้านขวาของทรีย่อยด้านขวา เราจะทำการหมุนซ้ายครั้งเดียว -

ในตัวอย่างของเรา โหนด A เกิดความไม่สมดุลเมื่อโหนดถูกแทรกในทรีย่อยด้านขวาของทรีย่อยด้านขวาของ A เราหมุนซ้ายโดยทำ A ทรีย่อยด้านซ้ายของ B . การหมุนนี้เรียกอีกอย่างว่าการหมุน LL ให้เราดูว่าเราจะนำไปใช้ได้อย่างไร -

function rotationLL(node) {
let tmp = node.left;
node.left = tmp.right;
tmp.right = node;
return tmp;
}

หมุนขวา

แผนผัง AVL อาจไม่สมดุลหากมีการแทรกโหนดในทรีย่อยด้านซ้ายของทรีย่อยด้านซ้าย ต้นไม้นั้นต้องการการหมุนที่เหมาะสม

ดังที่ปรากฎ โหนดที่ไม่สมดุลจะกลายเป็นลูกด้านขวาของลูกด้านซ้ายโดยทำการหมุนทางขวา เรียกอีกอย่างว่าการหมุน RR เรามาดูกันว่ามันมีลักษณะอย่างไรในโค้ด -

function rotationRR(node) {
let tmp = node.right;
node.right = tmp.left;
tmp.left = node;
return tmp;
}

หมุนซ้าย-ขวา

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

สถานะ	การกระทำ
	มีการแทรกโหนดลงในทรีย่อยด้านขวาของทรีย่อยด้านซ้าย ทำให้ C โหนดที่ไม่สมดุล สถานการณ์เหล่านี้ทำให้แผนผัง AVL ทำการหมุนซ้าย-ขวา
	ขั้นแรก เราทำการหมุนซ้ายบนทรีย่อยด้านซ้ายของ C. ทำให้ A , ทรีย่อยด้านซ้ายของ B .
	โหนด C ยังคงไม่สมดุล แต่ตอนนี้ เป็นเพราะทรีย่อยด้านซ้ายของทรีย่อยด้านซ้าย
	ตอนนี้เราจะหมุนต้นไม้ให้ถูกต้อง ทำให้ B โหนดรูทใหม่ของแผนผังย่อยนี้ ค ตอนนี้กลายเป็นทรีย่อยด้านขวาของทรีย่อยด้านซ้ายของตัวเอง
	ตอนนี้ต้นไม้ได้สมดุลแล้ว

สิ่งนี้เรียกอีกอย่างว่าการหมุน LR เนื่องจากเราทำการหมุนซ้ายก่อนแล้วตามด้วยการหมุนขวา สามารถทำได้โดยใช้ 2 วิธีก่อนหน้านี้ดังนี้ −

function rotationLR(node) {
node.left = rotationRR(node.left);
return rotationLL(node);
}

หมุนซ้าย-ขวา

การหมุนสองครั้งประเภทที่สองคือการหมุนซ้าย-ขวา เป็นการผสมผสานระหว่างการหมุนขวาตามด้วยการหมุนซ้าย

สถานะ	การกระทำ
	มีการแทรกโหนดลงในทรีย่อยด้านซ้ายของแผนผังย่อยด้านขวา ทำให้ A โหนดที่ไม่สมดุลพร้อมปัจจัยสมดุล 2
	ขั้นแรก เราหมุนขวาตาม C โหนดทำให้ C ต้นไม้ย่อยด้านขวาของต้นไม้ย่อยด้านซ้ายของตัวเอง B . ตอนนี้ B กลายเป็นต้นไม้ย่อยที่ถูกต้องของ A .
	โหนด A ยังคงไม่สมดุลเนื่องจากทรีย่อยด้านขวาของทรีย่อยด้านขวา และต้องหมุนซ้าย
	การหมุนซ้ายทำได้โดยทำให้ B โหนดรูทใหม่ของทรีย่อย เอ กลายเป็นทรีย่อยด้านซ้ายของทรีย่อยด้านขวา B .
	ตอนนี้ต้นไม้ได้สมดุลแล้ว

สิ่งนี้เรียกอีกอย่างว่าการหมุน RL เนื่องจากเราทำการหมุนทางขวาในครั้งแรกแล้วตามด้วยการหมุนซ้าย สามารถทำได้โดยใช้ 2 วิธีก่อนหน้านี้ดังนี้ −

function rotationRL(node) {
node.right = rotationLL(node.right);
return rotationRR(node);
}