ผลต่างระหว่างรุ่นของ "Psl/binary search trees"

รุ่นแก้ไขปัจจุบันเมื่อ 03:49, 10 มีนาคม 2560

หน้านี้เป็นส่วนหนึ่งของ Problem solving lab

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

Bst เป็นโครงสร้างข้อมูลที่นอกจากจะรองรับการค้นหาด้วย key แล้ว ยังสามารถตอบคำถามว่า key ใดมีค่า "ก่อนหน้า" key ที่เราค้นหาได้ด้วย (predecessor search) ลักษณะนี้จะอาจจะทำไม่ได้ในโครงสร้างข้อมูลที่รองรับการค้นด้วย key อย่างเดียว เช่น hash table

อ่านพื้นฐานและดูตัวอย่างของ bst ได้ที่ลิงก์ต่อไปนี้

เนื้อหา

1 มาเขียนกัน!
2 Balanced bst
- 2.1 AVL Tree
- 2.2 วิธีอื่น ๆ

มาเขียนกัน!

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

การลบข้อมูล

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

อีกวิธีคือการลบข้อมูลทิ้งจริง ๆ โดยจะต้องมีการจัดการกับต้นไม้ที่แยกออกจากกันเมื่อมีการลบข้อมูล อ่านรายละเอียดจากวิกิพีเดีย

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

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

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

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

Balanced bst

มีหลายวิธีที่จะ implement balanced bst ที่จะรับประกันว่าความลึกของ tree มีค่าเป็น O(log n) เมื่อ n เป็นจำนวนโหนดใน tree แต่ละวิธีจะมีการรักษาคุณสมบัติบางอย่างของต้นไม้ เพื่อรับประกันความ balance นี้

AVL Tree

วิธีแรกที่มีคนค้นพบคือ AVL tree คิดโดย Adelson-Velsky และ Landis

เงื่อนไขในความสมดุลย์ ความลึกของต้นไม้ย่อยของลูกด้านซ้ายจะต่างจากความลึกของต้นไม้ย่อยของลูกด้านขวาไม่เกิน 1

ในการ implement โครงสร้างข้อมูลนี้ เราจะเก็บค่า ความลึก ไว้ที่แต่ละโหนด และจะมีการดำเนินการพิเศษเพื่อรักษาความสมดุลย์ เรียกว่าการ rotate ซึ่งมีสองแบบคือการหมุนแบบธรรมดา กับการหมุนแบบสองชั้น (double rotation)

วิธีอื่น ๆ

ยังมีวิธีอื่น ๆ อีกหลายแบบในการจัดการกับเวลาการค้นหาและประมวลผลด้วย bst เช่น

red-black trees
B-tree
Splay tree - มีเวลาการทำงานเป็น amortized
Scapegoat tree - มีเวลาการทำงานเป็น amortized เช่นเดียวกัน
Treap - เป็นโครงสร้างข้อมูลแบบ randomized

@@ แถว 1: / แถว 1: @@
+: ''หน้านี้เป็นส่วนหนึ่งของ [[Problem solving lab]]''
 ในส่วนนี้เราจะหัดใช้โครงสร้างข้อมูลแบบ binary search tree
-* [http://en.wikipedia.org/wiki/Binary_search_tree อ่านในวิกิกพีเดีย]
+Bst เป็นโครงสร้างข้อมูลที่นอกจากจะรองรับการค้นหาด้วย key แล้ว ยังสามารถตอบคำถามว่า key ใดมีค่า "ก่อนหน้า" key ที่เราค้นหาได้ด้วย (predecessor search) ลักษณะนี้จะอาจจะทำไม่ได้ในโครงสร้างข้อมูลที่รองรับการค้นด้วย key อย่างเดียว เช่น hash table
+อ่านพื้นฐานและดูตัวอย่างของ bst ได้ที่ลิงก์ต่อไปนี้
+* [http://en.wikipedia.org/wiki/Binary_search_tree อ่านในวิกิพีเดีย]
 * [http://www.comp.nus.edu.sg/~stevenha/visualization/bst.html bst ที่ visual algo]
-ส่วนพื้นฐานของโครงสร้างข้อมูลดังกล่าวคือ tree node ซึ่งจะประกอบด้วยที่สำหรับเก็บข้อมูลและ pointer สองอันที่ชี้ไปยังโหนดลูกด้านซ้ายและด้านขวา นิยามได้ดังนี้
+== มาเขียนกัน! ==
+ส่วนพื้นฐานของโครงสร้างข้อมูลดังกล่าวคือ tree node ซึ่งจะประกอบด้วยที่สำหรับเก็บ key และ/หรือข้อมูล, และ pointer สองอันที่ชี้ไปยังโหนดลูกด้านซ้ายและด้านขวา นิยามได้ดังนี้
 <syntaxhighlight lang="cpp">
@@ แถว 18: / แถว 26: @@
 </syntaxhighlight>
-== การเก็บข้อมูลเพิ่มใน bst ==
+=== การเพิ่มข้อมูลใน bst (ไม่ balanced) ===
-== การเพิ่มข้อมูลใน bst (ไม่ balanced) ==
+โค้ดด้านล่างแสดงฟังก์ชัน <tt>insert</tt> ที่เขียนแบบเรียกตัวเอง สังเกตว่าเราใช้การส่งค่าแบบ reference ใน C++ ในการเขียนฟังก์ชันนี้ (เพราะว่าเราต้องการสร้างโหนดใหม่ในกรณีที่เจอโหนดว่าง)
 <syntaxhighlight lang="cpp">
@@ แถว 35: / แถว 43: @@
 }
 </syntaxhighlight>
+ตัวอย่างโปรแกรมหลัก:
+<syntaxhighlight lang="cpp">
+main()
+{
+  Node* r = 0;
+  insert(r,10);
+  insert(r,30);
+  insert(r,15);
+}
+</syntaxhighlight>
+'''ทดลองคิด 1:''' ถ้าเราไม่เขียนฟังก์ชัน <tt>insert</tt> โดยใช้ reference เราจะเขียนอย่างไร?
+'''ทดลองคิด 2:''' ถ้าเราไม่เขียนฟังก์ชัน <tt>insert</tt> แบบเรียกตัวเอง เราจะเขียนอย่างไร?
+=== การลบข้อมูล ===
+เราสามารถทำได้หลายแบบ วิธีที่ง่ายที่สุดคือลบโดยไม่ลบข้อมูลจริง ๆ แต่เก็บ flag ว่าข้อมูลนี้ถูกลบแล้ว  อย่างไรก็ตาม วิธีนี้เมื่อทำงานไปนาน ๆ อาจจะต้องมีการเก็บกวาดเนื่องจาก tree อาจจะเต็มไปด้วยข้อมูลที่ไม่ใช่ข้อมูลที่มีอยู่จริงแล้ว จนทำให้ประสิทธิภาพของการค้นหาถดถอยลง
+อีกวิธีคือการลบข้อมูลทิ้งจริง ๆ โดยจะต้องมีการจัดการกับต้นไม้ที่แยกออกจากกันเมื่อมีการลบข้อมูล [http://en.wikipedia.org/wiki/Binary_search_tree#Deletion อ่านรายละเอียดจากวิกิพีเดีย]
+=== การเก็บข้อมูลเพิ่มใน bst ===
+หลายครั้งที่เราสามารถเก็บข้อมูลเพิ่มที่โหนดใน bst เพื่อลดระยะเวลาการคำนวณต่าง ๆ ได้  ข้อมูลเพิ่มเติมโดยมากจะเป็นข้อมูลที่ '''รวบรวม''' มาจากโหนดอื่น ๆ ที่เป็นโหนดลูกหลานของโหนดนั้นๆ ยกตัวอย่างเช่น เราอาจจะเก็บจำนวนโหนดทั้งหมดที่เป็นลูกหลานของโหนดใด ๆ
+<syntaxhighlight lang="cpp">
+struct Node {
+  // ...
+  int descendent_count;
+  // ...
+};
+</syntaxhighlight>
+ด้วยข้อมูลนี้ เราสามารถคำนวณค่าหลายอย่างได้ เช่น จำนวนข้อมูลที่มีค่ามากกว่าค่าบางค่า โดยใช้เวลาในการคำนวณไม่เกินความลึกของ bst
 == Balanced bst ==
+มีหลายวิธีที่จะ implement balanced bst ที่จะรับประกันว่าความลึกของ tree มีค่าเป็น O(log n) เมื่อ n เป็นจำนวนโหนดใน tree  แต่ละวิธีจะมีการรักษาคุณสมบัติบางอย่างของต้นไม้ เพื่อรับประกันความ balance นี้
+=== AVL Tree ===
+วิธีแรกที่มีคนค้นพบคือ [http://en.wikipedia.org/wiki/AVL_tree AVL tree] คิดโดย Adelson-Velsky และ Landis
+'''เงื่อนไขในความสมดุลย์''' ความลึกของต้นไม้ย่อยของลูกด้านซ้ายจะต่างจากความลึกของต้นไม้ย่อยของลูกด้านขวาไม่เกิน 1
+ในการ implement โครงสร้างข้อมูลนี้ เราจะเก็บค่า '''ความลึก''' ไว้ที่แต่ละโหนด และจะมีการดำเนินการพิเศษเพื่อรักษาความสมดุลย์ เรียกว่าการ rotate  ซึ่งมีสองแบบคือการหมุนแบบธรรมดา กับการหมุนแบบสองชั้น (double rotation)
+=== วิธีอื่น ๆ ===
+ยังมีวิธีอื่น ๆ อีกหลายแบบในการจัดการกับเวลาการค้นหาและประมวลผลด้วย bst เช่น
+* [http://en.wikipedia.org/wiki/Red%E2%80%93black_tree red-black trees]
+* [http://en.wikipedia.org/wiki/B-tree B-tree]
+* [http://en.wikipedia.org/wiki/Splay_tree Splay tree] - มีเวลาการทำงานเป็น amortized
+* [http://en.wikipedia.org/wiki/Scapegoat_tree Scapegoat tree] - มีเวลาการทำงานเป็น amortized เช่นเดียวกัน
+* [http://en.wikipedia.org/wiki/Treap Treap] - เป็นโครงสร้างข้อมูลแบบ randomized

ผลต่างระหว่างรุ่นของ "Psl/binary search trees"

รุ่นแก้ไขปัจจุบันเมื่อ 03:49, 10 มีนาคม 2560

เนื้อหา

มาเขียนกัน!

การเพิ่มข้อมูลใน bst (ไม่ balanced)

การลบข้อมูล

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

Balanced bst

AVL Tree

วิธีอื่น ๆ

รายการเลือกการนำทาง

เครื่องมือส่วนตัว

เนมสเปซ

สิ่งที่แตกต่าง

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ