ผลต่างระหว่างรุ่นของ "Psl/binary search trees"
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
| แถว 24: | แถว 24: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
| + | === การเพิ่มข้อมูลใน bst (ไม่ balanced) === | ||
| − | + | โค้ดด้านล่างแสดงฟังก์ชัน <tt>insert</tt> สังเกตว่าเราใช้การส่งค่าแบบ reference ใน C++ ในการเขียนฟังก์ชันนี้ (เพราะว่าเราต้องการสร้างโหนดใหม่ในกรณีที่เจอโหนดว่าง) | |
<syntaxhighlight lang="cpp"> | <syntaxhighlight lang="cpp"> | ||
| แถว 40: | แถว 41: | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
| + | |||
| + | ตัวอย่างโปรแกรมหลัก: | ||
| + | |||
| + | <syntaxhighlight lang="cpp"> | ||
| + | main() | ||
| + | { | ||
| + | Node* r = 0; | ||
| + | |||
| + | insert(r,10); | ||
| + | insert(r,30); | ||
| + | insert(r,15); | ||
| + | } | ||
| + | </syntaxhighlight> | ||
| + | |||
| + | '''ทดลองคิด:''' ถ้าเราไม่เขียนฟังก์ชัน <tt>insert</tt> โดยใช้ reference เราจะเขียนอย่างไร? | ||
=== การเก็บข้อมูลเพิ่มใน bst === | === การเก็บข้อมูลเพิ่มใน bst === | ||
== Balanced bst == | == Balanced bst == | ||
รุ่นแก้ไขเมื่อ 02:25, 9 กุมภาพันธ์ 2558
ในส่วนนี้เราจะหัดใช้โครงสร้างข้อมูลแบบ binary search tree
Bst เป็นโครงสร้างข้อมูลที่นอกจากจะรองรับการค้นหาด้วย key แล้ว ยังสามารถตอบคำถามว่า key ใดมีค่า "ก่อนหน้า" key ที่เราค้นหาได้ด้วย (predecessor search) ลักษณะนี้จะอาจจะทำไม่ได้ในโครงสร้างข้อมูลที่รองรับการค้นด้วย key อย่างเดียว เช่น hash table
อ่านพื้นฐานและดูตัวอย่างของ bst ได้ที่ลิงก์ต่อไปนี้
เนื้อหา
มาเขียนกัน!
ส่วนพื้นฐานของโครงสร้างข้อมูลดังกล่าวคือ 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);
}
ทดลองคิด: ถ้าเราไม่เขียนฟังก์ชัน insert โดยใช้ reference เราจะเขียนอย่างไร?
