ผลต่างระหว่างรุ่นของ "Psl/binary search trees"
ไปยังการนำทาง
ไปยังการค้นหา
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
| แถว 1: | แถว 1: | ||
ในส่วนนี้เราจะหัดใช้โครงสร้างข้อมูลแบบ binary search tree | ในส่วนนี้เราจะหัดใช้โครงสร้างข้อมูลแบบ binary search tree | ||
| + | |||
| + | Bst เป็นโครงสร้างข้อมูลที่นอกจากจะรองรับการค้นหาด้วย key แล้ว ยังสามารถตอบคำถามว่า key ใดมีค่า "ก่อนหน้า" key ที่เราค้นหาได้ด้วย (predecessor search) ลักษณะนี้จะอาจจะทำไม่ได้ในโครงสร้างข้อมูลที่รองรับการค้นด้วย key อย่างเดียว เช่น hash table | ||
| + | |||
| + | อ่านพื้นฐานและดูตัวอย่างของ bst ได้ที่ลิงก์ต่อไปนี้ | ||
* [http://en.wikipedia.org/wiki/Binary_search_tree อ่านในวิกิกพีเดีย] | * [http://en.wikipedia.org/wiki/Binary_search_tree อ่านในวิกิกพีเดีย] | ||
* [http://www.comp.nus.edu.sg/~stevenha/visualization/bst.html bst ที่ visual algo] | * [http://www.comp.nus.edu.sg/~stevenha/visualization/bst.html bst ที่ visual algo] | ||
| + | |||
| + | == มาเขียนกัน! == | ||
ส่วนพื้นฐานของโครงสร้างข้อมูลดังกล่าวคือ tree node ซึ่งจะประกอบด้วยที่สำหรับเก็บ key และ/หรือข้อมูล, และ pointer สองอันที่ชี้ไปยังโหนดลูกด้านซ้ายและด้านขวา นิยามได้ดังนี้ | ส่วนพื้นฐานของโครงสร้างข้อมูลดังกล่าวคือ tree node ซึ่งจะประกอบด้วยที่สำหรับเก็บ key และ/หรือข้อมูล, และ pointer สองอันที่ชี้ไปยังโหนดลูกด้านซ้ายและด้านขวา นิยามได้ดังนี้ | ||
| แถว 18: | แถว 24: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
| − | == การเพิ่มข้อมูลใน bst (ไม่ balanced) == | + | |
| + | === การเพิ่มข้อมูลใน bst (ไม่ balanced) === | ||
<syntaxhighlight lang="cpp"> | <syntaxhighlight lang="cpp"> | ||
| แถว 34: | แถว 41: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
| − | == การเก็บข้อมูลเพิ่มใน bst == | + | === การเก็บข้อมูลเพิ่มใน bst === |
== Balanced bst == | == Balanced bst == | ||
รุ่นแก้ไขเมื่อ 02:21, 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)
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);
}
