Psl/binary search trees - ประวัติรุ่นแก้ไข

Jittat: /* AVL Tree */

2017-03-10T03:49:03Z

AVL Tree

Jittat เมื่อ 07:04, 16 กุมภาพันธ์ 2558

2015-02-16T07:04:43Z

Jittat: /* การลบข้อมูล */

2015-02-09T02:45:24Z

การลบข้อมูล

Jittat: /* การลบข้อมูล */

2015-02-09T02:44:07Z

การลบข้อมูล

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

2015-02-09T02:42:21Z

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

Jittat: /* วิธีอื่น ๆ */

2015-02-09T02:37:04Z

วิธีอื่น ๆ

Jittat: /* Balanced bst */

2015-02-09T02:34:30Z

Balanced bst

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

2015-02-09T02:29:20Z

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

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

2015-02-09T02:25:52Z

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

Jittat: /* มาเขียนกัน! */

2015-02-09T02:25:12Z

มาเขียนกัน!

@@ แถว 83: / แถว 83: @@
 === AVL Tree ===
-วิธีแรกที่มีคนค้นพบคือ [[http://en.wikipedia.org/wiki/AVL_tree AVL tree]] คิดโดย Adelson-Velsky และ Landis
+วิธีแรกที่มีคนค้นพบคือ [http://en.wikipedia.org/wiki/AVL_tree AVL tree] คิดโดย Adelson-Velsky และ Landis
 '''เงื่อนไขในความสมดุลย์''' ความลึกของต้นไม้ย่อยของลูกด้านซ้ายจะต่างจากความลึกของต้นไม้ย่อยของลูกด้านขวาไม่เกิน 1

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 07:04, 16 กุมภาพันธ์ 2558
แถว 1:		แถว 1:
		+	: ''หน้านี้เป็นส่วนหนึ่งของ [[Problem solving lab]]''
		+
	ในส่วนนี้เราจะหัดใช้โครงสร้างข้อมูลแบบ binary search tree		ในส่วนนี้เราจะหัดใช้โครงสร้างข้อมูลแบบ binary search tree

@@ แถว 62: / แถว 62: @@
 เราสามารถทำได้หลายแบบ วิธีที่ง่ายที่สุดคือลบโดยไม่ลบข้อมูลจริง ๆ แต่เก็บ flag ว่าข้อมูลนี้ถูกลบแล้ว  อย่างไรก็ตาม วิธีนี้เมื่อทำงานไปนาน ๆ อาจจะต้องมีการเก็บกวาดเนื่องจาก tree อาจจะเต็มไปด้วยข้อมูลที่ไม่ใช่ข้อมูลที่มีอยู่จริงแล้ว จนทำให้ประสิทธิภาพของการค้นหาถดถอยลง
-อีกวิธีคือการลบข้อมูลทิ้งจริง ๆ โดยจะต้องมีการจัดการกับต้นไม้ที่แยกออกจากกันเมื่อมีการลบข้อมูล
+อีกวิธีคือการลบข้อมูลทิ้งจริง ๆ โดยจะต้องมีการจัดการกับต้นไม้ที่แยกออกจากกันเมื่อมีการลบข้อมูล [http://en.wikipedia.org/wiki/Binary_search_tree#Deletion อ่านรายละเอียดจากวิกิพีเดีย]
 === การเก็บข้อมูลเพิ่มใน bst ===

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 02:44, 9 กุมภาพันธ์ 2558
แถว 60:		แถว 60:

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

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

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 02:42, 9 กุมภาพันธ์ 2558
แถว 58:		แถว 58:

	'''ทดลองคิด 2:''' ถ้าเราไม่เขียนฟังก์ชัน <tt>insert</tt> แบบเรียกตัวเอง เราจะเขียนอย่างไร?		'''ทดลองคิด 2:''' ถ้าเราไม่เขียนฟังก์ชัน <tt>insert</tt> แบบเรียกตัวเอง เราจะเขียนอย่างไร?
		+
		+	=== การลบข้อมูล ===

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

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 02:37, 9 กุมภาพันธ์ 2558
แถว 83:		แถว 83:

	=== วิธีอื่น ๆ ===		=== วิธีอื่น ๆ ===
		+	ยังมีวิธีอื่น ๆ อีกหลายแบบในการจัดการกับเวลาการค้นหาและประมวลผลด้วย 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

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 02:34, 9 กุมภาพันธ์ 2558
แถว 73:		แถว 73:

	== Balanced 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)
		+
		+	=== วิธีอื่น ๆ ===

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 02:29, 9 กุมภาพันธ์ 2558
แถว 60:		แถว 60:

	=== การเก็บข้อมูลเพิ่มใน bst ===		=== การเก็บข้อมูลเพิ่มใน bst ===
		+	หลายครั้งที่เราสามารถเก็บข้อมูลเพิ่มที่โหนดใน bst เพื่อลดระยะเวลาการคำนวณต่าง ๆ ได้ ข้อมูลเพิ่มเติมโดยมากจะเป็นข้อมูลที่ '''รวบรวม''' มาจากโหนดอื่น ๆ ที่เป็นโหนดลูกหลานของโหนดนั้นๆ ยกตัวอย่างเช่น เราอาจจะเก็บจำนวนโหนดทั้งหมดที่เป็นลูกหลานของโหนดใด ๆ
		+
		+	<syntaxhighlight lang="cpp">
		+	struct Node {
		+	// ...
		+	int descendent_count;
		+	// ...
		+	};
		+	</syntaxhighlight>
		+
		+	ด้วยข้อมูลนี้ เราสามารถคำนวณค่าหลายอย่างได้ เช่น จำนวนข้อมูลที่มีค่ามากกว่าค่าบางค่า โดยใช้เวลาในการคำนวณไม่เกินความลึกของ bst

	== Balanced bst ==		== Balanced bst ==

@@ แถว 26: / แถว 26: @@
 === การเพิ่มข้อมูลใน bst (ไม่ balanced) ===
-โค้ดด้านล่างแสดงฟังก์ชัน <tt>insert</tt>  สังเกตว่าเราใช้การส่งค่าแบบ reference ใน C++ ในการเขียนฟังก์ชันนี้ (เพราะว่าเราต้องการสร้างโหนดใหม่ในกรณีที่เจอโหนดว่าง)
+โค้ดด้านล่างแสดงฟังก์ชัน <tt>insert</tt> ที่เขียนแบบเรียกตัวเอง สังเกตว่าเราใช้การส่งค่าแบบ reference ใน C++ ในการเขียนฟังก์ชันนี้ (เพราะว่าเราต้องการสร้างโหนดใหม่ในกรณีที่เจอโหนดว่าง)
 <syntaxhighlight lang="cpp">
@@ แถว 55: / แถว 55: @@
 </syntaxhighlight>
-'''ทดลองคิด:''' ถ้าเราไม่เขียนฟังก์ชัน <tt>insert</tt> โดยใช้ reference เราจะเขียนอย่างไร?
+'''ทดลองคิด 1:''' ถ้าเราไม่เขียนฟังก์ชัน <tt>insert</tt> โดยใช้ reference เราจะเขียนอย่างไร?
 === การเก็บข้อมูลเพิ่มใน bst ===
 == Balanced bst ==