ต้นไม้เฟนวิก

จากวิกิพีเดีย สารานุกรมเสรี

ในวิทยาการคอมพิวเตอร์ ต้นไม้เฟนวิก (อังกฤษ: Fenwick tree) หรืออาจเรียกว่า binary indexed tree เป็นโครงสร้างข้อมูลที่ใช้ในการคำนวณผลรวมนำหน้า (prefix sum) ของตารางข้อมูลได้อย่างมีประสิทธิภาพ โครงสร้างข้อมูลนี้คิดค้นโดย Peter Fenwick ใน พ.ศ. 2537[1]

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

อ้างอิง[แก้]

  1. Peter M. Fenwick (1994). "A new data structure for cumulative frequency tables". Software: Practice and Experience 24 (3): 327–336. doi:10.1002/spe.4380240306. 

แหล่งข้อมูลอื่น[แก้]