ทรีพ
ทรีพ (treap) | |
---|---|
![]() การจัดเรียงข้อมูลตัวอักษรแบบทรีพ โดยใช้ข้อมูลเสริมในลักษณะการเรียงของฮีปมากสุด | |
ความสำคัญของลำดับ | เรียงจากน้อยไปมาก |
การซ้ำกันของสมาชิก | อนุญาตให้ซ้ำได้ |
เวลาที่ใช้ค้นหาตามดัชนี | - |
เวลาที่ใช้ค้นหาตามค่า | O (log n) |
เวลาที่ใช้ในการเข้าถึง | O (log n) |
การทำให้ว่าง | ทำให้รากเป็น null |
เวลาที่ใช้ทำให้ว่าง | O (1) |
โครงสร้างต้นแบบ | ต้นไม้ค้นหาแบบทวิภาค |
โครงสร้างที่นำไปใช้ | - |
ทรีพ (อังกฤษ: Treap) เป็นต้นไม้ค้นหาแบบทวิภาคประเภทหนึ่ง ที่มีการประกันความสูง เฉลี่ยเป็น O (log n) โดยวิธีการนำแนวคิดเรื่องของฮีป เข้ามาช่วย โดยคำว่าทรีพ (treap) นั้นเป็นคำที่เกิดจากการประกอบของคำว่า binary search tree รวมกับคำว่า heap เป็น treap นั้นเอง
ประวัติของการคิดค้นทรีพ
[แก้]ทรีพถูกคิดค้นโดย Cecilia R. Aragon และ Raimund G. Seidel ในปี 1989 เนื่องจากการสร้างข้อมูลเสริมแบบสุ่ม ทรีพ จึงมีอีกชื่อหนึ่งว่า randomized binary search tree หรือ RBST
ลักษณะของทรีพ
[แก้]ปมของต้นไม้ทรีพนอกจากจะมีการเก็บข้อมูลหลักแล้ว จะมีการเก็บข้อมูลเสริม ซึ่งได้มาจากการสุ่มจำนวนจริงขึ้นมา โดยเมื่อมองจากข้อมูลเสริมของต้นไม้ทรีพ จะมีลักษณะการเรียงแบบฮีป กล่าวคือปมพ่อจะมีลำดับความสำคัญมากกว่า ปมลูกทั้งสองข้าง การจัดเรียงแบบนี้จะช่วยประกันได้ว่า ความสูงของต้นไม้จะ เตี้ยที่สุดเท่าที่ทำได้ หรือเป็น O (log n)
จุดเด่นของทรีพ
[แก้]จุดเด่นของทรีพคือการประกันว่าความสูงของต้นไม้จะ เตี๊ยที่สุดเท่าที่ทำได้ หรือเป็น O (log n) โดยสมบัตินี้เกิดการสุ่มที่มีการกระจายแบบฮาร์โมนิก คือ การกระจายที่เท่าๆกัน ส่งผลให้การเรียงเลขที่เกิดจากการสุ่มขึ้นมาเป็นฮีป จะทำให้ต้นไม้อยู่ ในรูปร่างเตี้ยที่สุดได้
บริการที่มักจะมี
[แก้]- การเพิ่ม ลบ ค้นหาข้อมูลอย่างรวดเร็ว
ความเร็วที่ใช้ในการทำงาน
[แก้]จุดมุ่งหมายของทรีพจะเน้นการเข้าถึงข้อมูลอย่างรวดเร็ว เนื่องจากสร้าง เป็นต้นไม้ที่ประกันความสูงเป็น O (log n)
ประเภทข้อมูลที่ใช้สร้างทรีพ
[แก้]ปมของต้นไม้ทรีพแตกต่างจาก ปมของต้นไม้ค้นหาแบบทวิภาค ตรงที่เก็บตัวแปรเพิ่มเป็นจำนวนจริงหนึ่งตัว ซึ่งถูกสุ่มค่าขึ้นมาตั้งแต่ตอนสร้างปม ข้อมูลเสริมส่วนนี้จะใช้ในการเปรียบเทียบเพื่อใช้ในการเรียงโครงสร้างของทรีพ เมื่อมองเฉพาะข้อมูลเสริมจะมีความสัมพันธ์แบบฮีป
การสร้างบริการของทรีพ
[แก้]การเพิ่มสมาชิก
[แก้]ขั้นตอนของการเพิ่มข้อมูล จะเพิ่มโดยเหมือนการเพิ่มต้นไม้ค้นหาแบบทวิภาคทุกประการ แต่หลังจากเพิ่มเสร็จแล้วจะทำการเปรียบเทียบข้อมูลเสริมของปมที่เพิ่มว่ามีมีความสำคัญมากกว่าปมพ่อหรือไม่ ที่มีความสำคัญ จะทำการหมุนปมพ่อลงมา และหมุนปมพ่อลงไปเรื่อยๆ จนกว่า ปมพ่อของปมที่เพิ่งเพิ่มมาจะมีความ สำคัญมากกว่า ซึ่งตรงกับนิยามของฮีป การหมุนปมจะทำให้ความสัมพันธ์แบบต้นไม้ค้นหาแบบทวิภาค ที่ข้อมูลในต้นไม้ย่อยด้านซ้ายน้อยกว่าราก และข้อมูลในต้นไม้ย่อยด้านขวามากกว่าราก ยังไม่เสียไป
การลบสมาชิก
[แก้]ขั้นตอนการลบสมาชิกนั้นทำได้โดยการหมุนปมที่อยากจะลบให้เป็นใบก่อน แล้วจึงลบใบทิ้ง โดยการทำให้เป็น null
การค้นหาสมาชิก
[แก้]การค้นหาสมาชิกทำได้เหมือนต้นไม้ค้นหาแบบทวิภาคทั่วไป