Psl/binary search trees

ในส่วนนี้เราจะหัดใช้โครงสร้างข้อมูลแบบ 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 แบบเรียกตัวเอง เราจะเขียนอย่างไร?

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

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

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

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