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)

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);
}