home

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

AVL Rotations ใน JavaScript

เพื่อปรับสมดุล AVL tree อาจทำ rotation 4 แบบ:

  • Left rotation
  • Right rotation
  • Left-Right rotation
  • Right-Left rotation

สองแบบแรกเป็น single rotations สองแบบถัดไปเป็น double rotations เพื่อให้มี unbalanced tree เราต้องมี tree สูงอย่างน้อย 2 ด้วย tree เรียบง่ายนี้ มาเข้าใจทีละแบบ:

Left Rotation

ถ้า tree ไม่สมดุลเมื่อ node ถูก insert เข้า right subtree ของ right subtree เราจะทำ single left rotation:

AVL Rotations ใน JavaScript

ในตัวอย่าง node A ไม่สมดุลเพราะมี node insert ใน right subtree ของ A's right subtree เราทำ left rotation โดยทำให้ A เป็น left-subtree ของ B Rotation นี้เรียกว่า LL rotation มาดูโค้ด:

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

Right Rotation

AVL tree อาจไม่สมดุลถ้า node ถูก insert ใน left subtree ของ left subtree Tree ต้องการ right rotation

AVL Rotations ใน JavaScript

ตามภาพ unbalanced node กลายเป็น right child ของ left child โดย right rotation เรียกว่า RR rotation มาดูโค้ด:

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

Left-Right Rotation

Double rotations เป็นเวอร์ชันซับซ้อนของ rotations ที่อธิบายไปแล้ว เพื่อเข้าใจดีกว่า ให้สังเกตแต่ละ action ขณะ rotation มาดู Left-Right rotation ก่อน Left-right rotation เป็นการรวม left rotation ตามด้วย right rotation

State Action
AVL Rotations ใน JavaScript Node ถูก insert เข้า right subtree ของ left subtree ทำให้ C ไม่สมดุล สถานการณ์นี้ทำให้ AVL tree ทำ left-right rotation
AVL Rotations ใน JavaScript เราทำ left rotation บน left subtree ของ C ก่อน ทำให้ A กลายเป็น left subtree ของ B
AVL Rotations ใน JavaScript Node C ยังไม่สมดุล แต่ตอนนี้เป็นเพราะ left-subtree ของ left-subtree
AVL Rotations ใน JavaScript เราทำ right-rotate ทำให้ B กลายเป็น root ใหม่ของ subtree นี้ C กลายเป็น right subtree ของ left subtree ของมันเอง
AVL Rotations ใน JavaScript Tree สมดุลแล้ว

เรียกว่า LR rotation เพราะทำ left rotation ก่อนแล้ว right rotation สามารถนำไปใช้ด้วยเมธอดก่อนหน้า 2 ตัวได้ดังนี้:

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

Right-Left Rotation

Double rotation ประเภทที่สองคือ Right-Left Rotation เป็นการรวม right rotation ตามด้วย left rotation

State Action
AVL Rotations ใน JavaScript Node ถูก insert เข้า left subtree ของ right subtree ทำให้ A ไม่สมดุลกับ balance factor 2
AVL Rotations ใน JavaScript ก่อนอื่น ทำ right rotation ตาม C node ทำให้ C กลายเป็น right subtree ของ left subtree ของมันเอง B ตอนนี้ B กลายเป็น right subtree ของ A
AVL Rotations ใน JavaScript Node A ยังไม่สมดุลเพราะ right subtree ของ right subtree ต้องการ left rotation
AVL Rotations ใน JavaScript ทำ left rotation โดยทำให้ B เป็น root ใหม่ของ subtree A กลายเป็น left subtree ของ right subtree B
AVL Rotations ใน JavaScript Tree สมดุลแล้ว

เรียกว่า RL rotation เพราะทำ right rotation ก่อนแล้ว left rotation นำไปใช้ด้วยเมธอดก่อนหน้า 2 ตัวได้ดังนี้:

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