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

Ralf HinzeและRoss Patersonระบุว่า finger tree เป็นการแสดงลำดับที่คงอยู่ซึ่งสามารถเข้าถึงปลายได้ในเวลาคงที่เฉลี่ย การต่อและการแยกสามารถทำได้ในเวลาลอการิทึมตามขนาดของชิ้นส่วนที่เล็กกว่า โครงสร้างนี้ยังสามารถสร้างเป็นโครงสร้างข้อมูลอเนกประสงค์ได้โดยการกำหนดการดำเนินการแยกในรูปแบบทั่วไป ทำให้สามารถทำหน้าที่เป็นลำดับ คิวลำดับความสำคัญ ต้นไม้ค้นหา หรือคิวค้นหาลำดับความสำคัญ รวมถึงประเภทข้อมูลนามธรรมอื่นๆ อีกมากมาย^{[ 1 ]}

นิ้ว คือ จุดที่สามารถเข้าถึงส่วนหนึ่งของโครงสร้างข้อมูลได้ ในภาษาเชิงคำสั่ง สิ่งนี้เรียกว่าตัวชี้^{[ 2 ]}ในต้นไม้แบบนิ้ว นิ้วคือโครงสร้างที่ชี้ไปยังปลายของลำดับหรือโหนดใบ นิ้วจะถูกเพิ่มเข้าไปในต้นไม้เดิมเพื่อให้สามารถเข้าถึงนิ้วได้ในเวลาคงที่ ในภาพที่แสดงด้านล่าง นิ้วคือเส้นที่ยื่นออกมาจากแกนกลางไปยังโหนด

ต้นไม้แบบนิ้วมือประกอบด้วยชั้น ต่างๆ ซึ่งสามารถระบุได้จากโหนดตามแนวแกนกลาง แกนกลางของต้นไม้สามารถคิดได้ว่าเป็นลำต้นในลักษณะเดียวกับที่ต้นไม้มีใบและราก แม้ว่าต้นไม้แบบนิ้วมือมักจะแสดงด้วยแกนกลางและกิ่งก้านที่แตกออกมาจากด้านข้าง แต่จริงๆ แล้วมีโหนดสองโหนดบนแกนกลางในแต่ละระดับที่จับคู่กันเพื่อสร้างแกนกลางนี้คำนำหน้าอยู่ทางด้านซ้ายของแกนกลาง ในขณะที่คำต่อท้ายอยู่ทางด้านขวา โหนดแต่ละโหนดเหล่านั้นมีการเชื่อมโยงไปยังระดับถัดไปของแกนกลางจนกว่าจะถึงราก^{[ 2 ]}

ระดับแรกของต้นไม้ประกอบด้วยค่าเท่านั้น ซึ่งก็คือโหนดใบของต้นไม้ และมีความลึก 0 ระดับที่สองมีความลึก 1 ระดับที่สามมีความลึก 2 และต่อไปเรื่อยๆ ยิ่งใกล้รากมากเท่าไหร่ โหนดก็จะยิ่งชี้ไปยังซับทรีของต้นไม้เดิม (ต้นไม้ก่อนหน้านี้เป็นฟิงเกอร์ทรี) ลึกมากขึ้นเท่านั้น ด้วยวิธีนี้ การทำงานลงไปในต้นไม้จึงเป็นการไปจากใบไปยังรากของต้นไม้ ซึ่งตรงกันข้ามกับโครงสร้างข้อมูลต้นไม้ทั่วไป เพื่อให้ได้โครงสร้างที่สวยงามและแปลกใหม่นี้ เราต้องแน่ใจว่าต้นไม้เดิมมีความลึกสม่ำเสมอ เพื่อให้แน่ใจว่าความลึกสม่ำเสมอ เมื่อประกาศออบเจ็กต์โหนด จะต้องกำหนดพารามิเตอร์ด้วยประเภทของลูก โหนดบนแกนกลางที่มีความลึก 1 ขึ้นไปจะชี้ไปยังต้นไม้ และด้วยการกำหนดพารามิเตอร์นี้ โหนดเหล่านั้นสามารถแสดงได้ด้วยโหนดที่ซ้อนกัน^{[ 3 ]}

เราจะเริ่มต้นกระบวนการนี้ด้วยโครงสร้างต้นไม้แบบสมดุล 2-3โหนด เพื่อให้โครงสร้างต้นไม้แบบนิ้วมือทำงานได้ โหนดใบทั้งหมดจะต้องอยู่ในระดับเดียวกันด้วย

นิ้วคือ "โครงสร้างที่ให้การเข้าถึงโหนดของต้นไม้ได้อย่างมีประสิทธิภาพใกล้กับตำแหน่งที่โดดเด่น" ^{[ 1 ]}ในการสร้างต้นไม้แบบนิ้ว เราต้องวางนิ้วไว้ที่ปลายด้านขวาและด้านซ้ายของต้นไม้และแปลงมันเหมือนซิปซึ่งทำให้เราสามารถเข้าถึงปลายลำดับได้ในเวลาเฉลี่ยคงที่

ในการแปลง ให้เริ่มต้นด้วยโครงสร้างต้นไม้แบบสมดุล 2–3

นำโหนดภายในซ้ายสุดและขวาสุดของต้นไม้ขึ้นมา เพื่อให้ส่วนที่เหลือของต้นไม้ห้อยอยู่ระหว่างโหนดทั้งสอง ดังแสดงในภาพด้านขวา

นำส่วนสันมาประกอบกันเพื่อให้ได้ทรงต้นไม้มาตรฐานที่มี 2-3 นิ้ว

สามารถอธิบายได้ดังนี้: ^{[ 1 ]}

ข้อมูลFingerTree a = ว่างเปล่า| เดี่ยวa | ลึก( ตัวเลขa ) ( FingerTree ( โหนดa )) ( ตัวเลขa )ข้อมูลNode a = Node2 a a | Node3 a a a

ตัวเลขในตัวอย่างที่แสดงคือโหนดที่มีตัวอักษร แต่ละรายการจะถูกแบ่งตามคำนำหน้าหรือคำต่อท้ายของแต่ละโหนดบนแกนหลัก ในโครงสร้างต้นไม้แบบ 2–3 ที่แปลงแล้ว ดูเหมือนว่ารายการตัวเลขในระดับบนสุดจะมีขนาดความยาวสองหรือสาม ในขณะที่ระดับล่างจะมีขนาดความยาวเพียงหนึ่งหรือสองเท่านั้น เพื่อให้การใช้งานโครงสร้างต้นไม้แบบนิ้วบางอย่างทำงานได้อย่างมีประสิทธิภาพ โครงสร้างต้นไม้แบบนิ้วจึงอนุญาตให้มีต้นไม้ย่อยได้ระหว่างหนึ่งถึงสี่ต้นในแต่ละระดับ

ตัวเลขของต้นไม้นิ้วสามารถแปลงเป็นรายการได้ดังนี้: ^{[ 1 ]}

พิมพ์ตัวเลขa = หนึ่งa | สองa a | สามa a a | สี่a a a a

ดังนั้นในภาพ ระดับบนสุดจะมีองค์ประกอบประเภทaระดับถัดไปจะมีองค์ประกอบประเภทNode aเนื่องจากโหนดที่อยู่ระหว่างแกนกลางและใบ และสิ่งนี้จะดำเนินต่อไป ซึ่งหมายความว่าโดยทั่วไปแล้ว ระดับที่ nของต้นไม้จะมีองค์ประกอบประเภทaหรือต้นไม้ 2–3 ต้นที่มีความลึก n ซึ่งหมายความว่าลำดับของ องค์ประกอบ nตัวจะถูกแทนด้วยต้นไม้ที่มีความลึก Θ(log n ) ยิ่งไปกว่านั้น องค์ประกอบ ที่อยู่ห่างจากปลายที่ใกล้ที่สุด d ตำแหน่ง จะถูกจัดเก็บไว้ที่ความลึก Θ(log d) ในต้นไม้^{[ 1 ]}${\displaystyle โหนด^{n}}$

กระบวนการนี้สามารถทำได้กับโครงสร้างต้นไม้แบบอื่น ๆ เช่นโครงสร้างต้นไม้แบบ 2–3–4ทางด้านขวา ซึ่งจะช่วยให้เห็นว่าตัวเลขเหล่านั้นคือคำอธิบายประกอบที่อยู่ภายในโครงสร้างต้นไม้ และตัวเลขแต่ละตัวจะเชื่อมโยงกับโครงสร้างต้นไม้ย่อยซึ่งอาจว่างเปล่าก็ได้

${\displaystyle {\begin{aligned}\mathrm {instance} &\ Reduce\ Node\ \mathrm {where} &&\\&reducer\ (\prec )\ (Node2\ a\ b)\ z&=&\ a\ \prec (b\ \prec \ z)\\&reducer\ (\prec )\ (Node3\ a\ b\ c)\ z&=&\ a\ \prec (\ b\prec (c\ \prec \ z))\\\\&reducel\ (\succ )\ z\ (Node2\ b\ a)\ &=&\ (z\ \succ \ b)\ \succ \ a\\&reducel\ (\succ )\ z\ (Node3\ c\ b\ a)\ &=&\ ((z\ \succ \ c)\succ \ b)\succ \ a\\\end{aligned}}}$${\displaystyle {\begin{aligned}\mathrm {instance} &\ Reduce\ FingerTree\ \mathrm {where} &&\\&reducer\ (\prec )\ (Empty)\ z\ &=&\ z\\&reducer\ (\prec )\ (Single\ x)\ z&=&\ x\ \prec \ z\\&reducer\ (\prec )\ (Deep\ pr\ m\ sf)\ z&=&\ pr\ \prec '\ (m\ \prec ''\ (sf\ \prec '\ z))\\&\ \ \ \ where\\&\ \ \ \ \ \ \ (\prec ')\ =reducer\ (\prec )\\&\ \ \ \ \ \ \ (\prec '')\ =reducer\ (reducer\ (\prec ))\\\\&reducel\ (\succ )\ z\ (ว่างเปล่า)\ &=&\ z\\&reducel\ (\succ )\ z\ (เดี่ยว\ \ x)\ &=&\ z\ \succ \ x\\&reducel\ (\succ )\ z\ (ลึก\ \ pr\ m\ sf)\ &=&\ ((z\ \succ '\ pr)\ \succ ''\ m)\ \succ '\ sf)\\&\ \ \ \ โดยที่\\&\ \ \ \ \ \ \ (\succ ')\ =reducel\ (\succ )\\&\ \ \ \ \ \ \ (\succ '')\ =reducel\ (reducel\ (\succ ))\\\end{aligned}}}$

ต้นไม้แบบนิ้วยังทำให้deque มีประสิทธิภาพอีกด้วย ไม่ว่าโครงสร้างจะคงอยู่หรือไม่ การดำเนินการทั้งหมดใช้เวลาเฉลี่ย Θ(1) การวิเคราะห์สามารถเปรียบเทียบได้กับ deque โดยปริยายของ Okasaki ความแตกต่างเพียงอย่างเดียวคือประเภท FingerTree จัดเก็บโหนดแทนที่จะเป็นคู่^{[ 1 ]}

ต้นไม้แบบนิ้วมือสามารถใช้สร้างต้นไม้อื่นๆ ได้^{[ 4 ]}ตัวอย่างเช่นคิวลำดับความสำคัญสามารถนำไปใช้ได้โดยการติดป้ายกำกับโหนดภายในตามลำดับความสำคัญต่ำสุดของลูกๆ ในต้นไม้ หรือรายการ/อาร์เรย์แบบมีดัชนีสามารถนำไปใช้ได้โดยการติดป้ายกำกับโหนดตามจำนวนใบในลูกๆ แอปพลิเคชันอื่นๆ ได้แก่ ลำดับการเข้าถึงแบบสุ่ม ซึ่งจะอธิบายต่อไปลำดับที่เรียงลำดับและต้นไม้ช่วงเวลา^{[ 1 ]}

โครงสร้างข้อมูลแบบ Finger tree สามารถให้ประสิทธิภาพการประมวลผลแบบเฉลี่ย O(1) สำหรับการผลัก การกลับทิศทาง การดึงออก การเพิ่ม และการแยก และสามารถปรับให้เป็นลำดับดัชนีหรือลำดับที่เรียงลำดับได้ และเช่นเดียวกับโครงสร้างข้อมูลเชิงฟังก์ชันทั้งหมด โครงสร้างนี้มีความคงทน โดยธรรมชาติ กล่าวคือ เวอร์ชันเก่าของต้นไม้จะถูกเก็บรักษาไว้เสมอ

ต้นไม้แบบนิ้วสามารถใช้งานลำดับการเข้าถึงแบบสุ่มได้อย่างมีประสิทธิภาพ ซึ่งควรจะรองรับการดำเนินการตามตำแหน่งอย่างรวดเร็ว รวมถึงการเข้าถึงองค์ประกอบที่nและการแยกลำดับที่ตำแหน่งที่กำหนด ในการทำเช่นนี้ เราจะใส่คำอธิบายประกอบให้กับต้นไม้แบบนิ้วด้วยขนาด^{[ 1 ]}

ขนาดชนิดใหม่= ขนาด{ getSize :: N } อนุพันธ์( Eq , Ord )อินสแตน ซ์ Monoid Size ที่∅ = Size 0 Size m ⊕ Size n = Size ( m + n )

ตัว อักษร Nย่อมาจากจำนวนธรรมชาติ ชนิดข้อมูลใหม่นี้จำเป็นเพราะชนิดข้อมูลนี้เป็นตัวกลางของโมโนอิดที่แตกต่างกัน และยังจำเป็นต้องมีชนิดข้อมูลใหม่สำหรับองค์ประกอบในลำดับที่แสดงด้านล่างอีกด้วย

newtype Elem a = Elem { getElem :: a } newtype Seq a = Seq ( FingerTree Size ( Elem a ))instance Measured ( Elem a ) Size where || Elem || = Size 1

บรรทัดโค้ดเหล่านี้แสดงให้เห็นว่า instance ทำงานเป็นกรณีพื้นฐานสำหรับการวัดขนาด และองค์ประกอบมีขนาดหนึ่ง การใช้newtype s ไม่ทำให้เกิดภาระด้านเวลาในการรันไทม์ใน Haskell เนื่องจากในไลบรารี ประเภท SizeและElemจะถูกซ่อนจากผู้ใช้ด้วยฟังก์ชัน wrapper

ด้วยการเปลี่ยนแปลงเหล่านี้ ความยาวของลำดับจึงสามารถคำนวณได้ในเวลาคงที่

ต้นไม้แบบ Finger tree ได้รับการตีพิมพ์ครั้งแรกในปี พ.ศ. 2520 โดยLeonidas J. Guibas [ ^{5 ] และได้}รับการปรับปรุงเป็นระยะตั้งแต่นั้นมา (เช่น เวอร์ชันที่ใช้ต้นไม้ AVL [ ^{6 ]}ต้นไม้แบบ Finger tree ที่ไม่ใช่แบบ lazy ต้นไม้แบบ Finger tree 2–3 ที่เรียบง่ายกว่าที่แสดงไว้ที่นี่^{[ 1 ]}ต้นไม้ B และอื่นๆ)

ตั้งแต่นั้นมา Finger trees ได้ถูกนำไปใช้ใน ไลบรารีหลักของ Haskell (ในการใช้งานData.Sequence ) และมี การใช้งานใน OCaml ^{[ 7 ]}ซึ่งได้มาจากการใช้งานRocq ที่ได้รับการพิสูจน์แล้วว่าถูกต้อง ^{[ 8 ]}นอกจากนี้ยังมีการใช้งานที่ได้รับการตรวจสอบแล้วในIsabelle (ตัวช่วยพิสูจน์)ซึ่งสามารถสร้างโปรแกรมใน Haskell และภาษาอื่นๆ (เชิงฟังก์ชัน) ได้^{[ 9 ]} Finger trees สามารถใช้งานได้โดยมีหรือไม่มี การประเมิน แบบขี้เกียจ^{[ 10 ]}แต่การประเมินแบบขี้เกียจช่วยให้การใช้งานง่ายขึ้น

• โมโนอิด
• ต้นไม้ค้นหานิ้วมือ
• ซิป

• http://www.soi.city.ac.uk/~ross/papers/FingerTree.html
• http://hackage.haskell.org/packages/archive/EdisonCore/1.2.1.1/doc/html/Data-Edison-Concrete-FingerTree.html
• ตัวอย่างโครงสร้างต้นไม้ 2-3 ต้นในภาษา C#
• ตัวอย่างโครงสร้างข้อมูลแบบ Hinze/Paterson Finger Tree ในภาษา Java
• ตัวอย่างโครงสร้าง Finger Tree แบบ Hinze/Paterson ในภาษา C#
• โมโนอิดและฟิงเกอร์ทรีในฮัสเคลล์
• ไลบรารี Finger tree สำหรับ Clojure
• ต้นไม้นิ้วมือใน Scalaz