Psl/binary search trees

หน้านี้เป็นส่วนหนึ่งของ Problem solving lab

ในส่วนนี้เราจะหัดใช้โครงสร้างข้อมูลแบบ binary search tree

Bst เป็นโครงสร้างข้อมูลที่นอกจากจะรองรับการค้นหาด้วย key แล้ว ยังสามารถตอบคำถามว่า key ใดมีค่า "ก่อนหน้า" key ที่เราค้นหาได้ด้วย (predecessor search) ลักษณะนี้จะอาจจะทำไม่ได้ในโครงสร้างข้อมูลที่รองรับการค้นด้วย key อย่างเดียว เช่น hash table

อ่านพื้นฐานและดูตัวอย่างของ bst ได้ที่ลิงก์ต่อไปนี้

• อ่านในวิกิพีเดีย
• bst ที่ visual algo

มาเขียนกัน!

ส่วนพื้นฐานของโครงสร้างข้อมูลดังกล่าวคือ tree node ซึ่งจะประกอบด้วยที่สำหรับเก็บ key และ/หรือข้อมูล, และ pointer สองอันที่ชี้ไปยังโหนดลูกด้านซ้ายและด้านขวา นิยามได้ดังนี้

struct Node {
  int val;
  Node* left;
  Node* right;

  Node(int v, Node* l=0, Node* r=0)
    : val(v), left(l), right(r)
  {}
};

การเพิ่มข้อมูลใน bst (ไม่ balanced)

โค้ดด้านล่างแสดงฟังก์ชัน insert ที่เขียนแบบเรียกตัวเอง สังเกตว่าเราใช้การส่งค่าแบบ reference ใน C++ ในการเขียนฟังก์ชันนี้ (เพราะว่าเราต้องการสร้างโหนดใหม่ในกรณีที่เจอโหนดว่าง)

void insert(Node*& root, int x)
{
  if(root == 0) {
    root = new Node(x);
    return;
  }
  if(x > root->val)
    insert(root->right, x);
  else if(x < root->val)
    insert(root->left, x);
}

ตัวอย่างโปรแกรมหลัก:

main()
{
  Node* r = 0;

  insert(r,10);
  insert(r,30);
  insert(r,15);
}

ทดลองคิด 1: ถ้าเราไม่เขียนฟังก์ชัน insert โดยใช้ reference เราจะเขียนอย่างไร?

ทดลองคิด 2: ถ้าเราไม่เขียนฟังก์ชัน insert แบบเรียกตัวเอง เราจะเขียนอย่างไร?

การลบข้อมูล

เราสามารถทำได้หลายแบบ วิธีที่ง่ายที่สุดคือลบโดยไม่ลบข้อมูลจริง ๆ แต่เก็บ flag ว่าข้อมูลนี้ถูกลบแล้ว อย่างไรก็ตาม วิธีนี้เมื่อทำงานไปนาน ๆ อาจจะต้องมีการเก็บกวาดเนื่องจาก tree อาจจะเต็มไปด้วยข้อมูลที่ไม่ใช่ข้อมูลที่มีอยู่จริงแล้ว จนทำให้ประสิทธิภาพของการค้นหาถดถอยลง

อีกวิธีคือการลบข้อมูลทิ้งจริง ๆ โดยจะต้องมีการจัดการกับต้นไม้ที่แยกออกจากกันเมื่อมีการลบข้อมูล อ่านรายละเอียดจากวิกิพีเดีย

การเก็บข้อมูลเพิ่มใน bst

หลายครั้งที่เราสามารถเก็บข้อมูลเพิ่มที่โหนดใน bst เพื่อลดระยะเวลาการคำนวณต่าง ๆ ได้ ข้อมูลเพิ่มเติมโดยมากจะเป็นข้อมูลที่ รวบรวม มาจากโหนดอื่น ๆ ที่เป็นโหนดลูกหลานของโหนดนั้นๆ ยกตัวอย่างเช่น เราอาจจะเก็บจำนวนโหนดทั้งหมดที่เป็นลูกหลานของโหนดใด ๆ

struct Node {
  // ...
  int descendent_count;
  // ...
};

ด้วยข้อมูลนี้ เราสามารถคำนวณค่าหลายอย่างได้ เช่น จำนวนข้อมูลที่มีค่ามากกว่าค่าบางค่า โดยใช้เวลาในการคำนวณไม่เกินความลึกของ bst

Balanced bst

มีหลายวิธีที่จะ implement balanced bst ที่จะรับประกันว่าความลึกของ tree มีค่าเป็น O(log n) เมื่อ n เป็นจำนวนโหนดใน tree แต่ละวิธีจะมีการรักษาคุณสมบัติบางอย่างของต้นไม้ เพื่อรับประกันความ balance นี้

AVL Tree

วิธีแรกที่มีคนค้นพบคือ [AVL tree] คิดโดย Adelson-Velsky และ Landis

เงื่อนไขในความสมดุลย์ ความลึกของต้นไม้ย่อยของลูกด้านซ้ายจะต่างจากความลึกของต้นไม้ย่อยของลูกด้านขวาไม่เกิน 1

ในการ implement โครงสร้างข้อมูลนี้ เราจะเก็บค่า ความลึก ไว้ที่แต่ละโหนด และจะมีการดำเนินการพิเศษเพื่อรักษาความสมดุลย์ เรียกว่าการ rotate ซึ่งมีสองแบบคือการหมุนแบบธรรมดา กับการหมุนแบบสองชั้น (double rotation)

วิธีอื่น ๆ

ยังมีวิธีอื่น ๆ อีกหลายแบบในการจัดการกับเวลาการค้นหาและประมวลผลด้วย bst เช่น

• red-black trees
• B-tree
• Splay tree - มีเวลาการทำงานเป็น amortized
• Scapegoat tree - มีเวลาการทำงานเป็น amortized เช่นเดียวกัน
• Treap - เป็นโครงสร้างข้อมูลแบบ randomized