Psl/binary search trees

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

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

ส่วนพื้นฐานของโครงสร้างข้อมูลดังกล่าวคือ tree node ซึ่งจะประกอบด้วยที่สำหรับเก็บข้อมูลและ 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);
}