ในวิทยาการคอมพิวเตอร์ a trie ( / ˈ t r aɪ / , / ˈ t r iː /^ⓘ ) หรือที่รู้จักกันในชื่อต้นไม้ดิจิทัลหรือต้นไม้คำนำหน้า[^{1 ]}เป็นต้นไม้ค้นหาที่ใช้ในการจัดเก็บและเรียกสตริงจากพจนานุกรมหรือชุดข้อมูล แตกต่างจาก^{ต้นไม้}ค้นหาแบบไบนารีโหนดในไทรจะไม่จัดเก็บคีย์ที่เกี่ยวข้อง แต่ตำแหน่งภายในไทรจะเป็นตัวกำหนดคีย์ที่เกี่ยวข้อง โดยการเชื่อมต่อระหว่างโหนดจะถูกกำหนดโดยอักขระแทนที่จะเป็นคีย์ทั้งหมด

โครงสร้างข้อมูลแบบ Trie มีประสิทธิภาพเป็นพิเศษสำหรับงานต่างๆ เช่น การเติมข้อความอัตโนมัติ การตรวจสอบการสะกดคำ และการกำหนดเส้นทาง IP โดยมีข้อดีเหนือกว่าตารางแฮชเนื่องจากการจัดระเบียบตามคำนำหน้าและการไม่มีการชนกันของแฮช โหนดลูกแต่ละโหนดจะใช้คำนำหน้า เดียวกัน กับโหนดแม่ และโหนดรากจะแสดงถึงสตริงว่างแม้ว่าการใช้งาน Trie ขั้นพื้นฐานอาจใช้หน่วยความจำมาก แต่ก็มีการพัฒนาเทคนิคการเพิ่มประสิทธิภาพต่างๆ เช่น การบีบอัดและการแสดงผลแบบบิตไวส์ เพื่อปรับปรุงประสิทธิภาพ หนึ่งในเทคนิคการเพิ่มประสิทธิภาพที่โดดเด่นคือRadix Treeซึ่งให้การจัดเก็บข้อมูลตามคำนำหน้าที่มีประสิทธิภาพมากขึ้น

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

แนวคิดของไทร (trie) สำหรับการแสดงเซตของสตริงได้รับการอธิบายในเชิงนามธรรมครั้งแรกโดยAxel Thueในปี พ.ศ. 2455 ^{[ 2 ] [ 3 ]}ไทรได้รับการอธิบายในบริบทของคอมพิวเตอร์ครั้งแรกโดย René de la Briandais ในปี พ.ศ. 2492 ^{[ 4 ] [ 3 ] [ 5 ] : 336}

แนวคิดนี้ได้รับการอธิบายอย่างอิสระในปี พ.ศ. 2503 โดยEdward Fredkin [ ^{6 ] ซึ่ง}บัญญัติศัพท์คำว่าtrieโดยออกเสียงว่า/ ˈ t r iː / (เหมือน "tree") ตามพยางค์กลางของretrieval [ ^{7 ] [ 8 ] อย่างไรก็ตาม}ผู้เขียนคนอื่นๆ ออกเสียงว่า/ ˈ t r aɪ / (เหมือน "try") เพื่อพยายามแยกแยะออกจาก "tree" ^{[ 7 ] [ 8 ] [ 3 ]}

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

Trie สามารถมีประสิทธิภาพในอัลกอริทึมการค้นหาสตริงเช่นการทำนายข้อความการจับคู่สตริงโดยประมาณและการตรวจสอบการสะกดคำเมื่อเปรียบเทียบกับต้นไม้ค้นหาแบบไบนารี^{[ 11 ] [ 8 ] [ 12 ] : 358} Trie สามารถมองได้ว่าเป็นออโตมาตา จำกัดแบบกำหนดได้ที่มีรูปร่างเหมือนต้นไม้^{[ 13 ]}

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

ลิงก์ว่างภายในโหนดลูกเน้นลักษณะดังต่อไปนี้: ^{[ 14 ] : 734 [ 5 ] : 336}

1. ตัวอักษรและคีย์สตริงจะถูกจัดเก็บโดยปริยายในโครงสร้างข้อมูลแบบไทร (trie) และมีค่าตัวบ่งชี้การสิ้นสุดของสตริง ด้วย
2. แต่ละโหนดจะมีลิงก์ที่เป็นไปได้หนึ่งลิงก์ไปยังคำนำหน้าของคีย์ที่แข็งแกร่งของชุดนั้น

โครงสร้างพื้นฐานของโหนดในไทรมีรูปแบบดังนี้: อาจมีพารามิเตอร์เสริมซึ่งเชื่อมโยงกับคีย์ที่ตรงกับโหนดนั้น ${\displaystyle {\text{โหนด}}}$${\displaystyle {\text{Value}}}$

โครงสร้างโหนดโครงสร้างสิ้นสุด ของโหนด ลูก[ ขนาดตัวอักษร] ค่าชนิดข้อมูล

การค้นหาค่าในไทรจะถูกนำทางโดยอักขระในคีย์สตริงการค้นหา เนื่องจากแต่ละโหนดในไทรจะมีลิงก์ที่สอดคล้องกับอักขระที่เป็นไปได้แต่ละตัวในสตริงที่กำหนด ดังนั้น การติดตามสตริงภายในไทรจะให้ค่าที่เกี่ยวข้องสำหรับคีย์สตริงที่กำหนด ลิงก์ที่เป็นค่าว่างในระหว่างการค้นหาบ่งชี้ว่าคีย์นั้นไม่มีอยู่^{[ 14 ] : 732-733}

รหัสเทียมต่อไปนี้ใช้ขั้นตอนการค้นหาสำหรับ คีย์สตริงที่กำหนดในไทรรากx ^{[ 15 ]} : ¹³⁵

Trie-Find(x, key) สำหรับ 0 ≤ i < key.length ทำซ้ำถ้า x.Children[key[i]] = nil ให้คืนค่า nil  x := x.Children[key[i]] ทำซ้ำส่งกลับค่า x 

ในรหัสเทียมข้างต้นxและkeyสอดคล้องกับตัวชี้ของโหนดรากของไทรและสตริง key ตามลำดับ การดำเนินการค้นหาใช้เวลา โดยที่คือขนาดของพารามิเตอร์สตริงkeyในทางกลับกันในต้นไม้ค้นหาไบนารีที่สมดุล จะใช้ เวลา ในกรณีที่เลวร้ายที่สุด เนื่องจากkeyจำเป็นต้องถูกเปรียบเทียบกับคีย์อื่นๆ และการเปรียบเทียบแต่ละครั้งใช้เวลา ในกรณีที่เลวร้ายที่สุด^{[ 12 ] : 358} ${\displaystyle O(m)}$${\displaystyle m}$${\displaystyle O(m\log n)}$${\displaystyle O(\log n)}$${\displaystyle O(m)}$

โครงสร้างข้อมูลแบบไทร (trie) ใช้พื้นที่น้อยกว่าเมื่อเปรียบเทียบกับต้นไม้ค้นหาแบบไบนารี (binary search tree) ในกรณีที่มีสตริงสั้นจำนวนมาก เนื่องจากโหนดต่างๆ ใช้ลำดับย่อยของสตริงเริ่มต้นร่วมกันและจัดเก็บคีย์โดยปริยาย^{[ 12 ] : 358}

การแทรกเข้าไปในไทรจะถูกนำทางโดยใช้ชุดอักขระเป็นดัชนีไปยังอาร์เรย์ลูกจนกว่าจะถึงอักขระตัวสุดท้ายของคีย์สตริง^{[ 14 ] : 733-734} แต่ละโหนดในไทรจะสอดคล้องกับการเรียกใช้รูที น การเรียงลำดับแบบเรเดียล หนึ่งครั้ง เนื่องจากโครงสร้างไทรสะท้อนรูปแบบการดำเนินการของการเรียงลำดับแบบเรเดียลจากบนลงล่าง^{[ 15 ] : 135}

Trie-Insert(x, key, value) สำหรับ 0 ≤ i < key.length ทำซ้ำถ้า x.Children[key[i]] = nil แล้ว x.Children[key[i]] := Create-New-Node() จบถ้า x := x.Children[key[i]] ทำซ้ำ x.Value := value 

หากพบลิงก์ว่างก่อนถึงอักขระตัวสุดท้ายของคีย์สตริง จะมีการสร้างโหนดใหม่^{[ 14 ] : 745} ค่าอินพุตจะถูกกำหนดให้กับค่าของโหนดสุดท้ายที่สำรวจ ซึ่งเป็นโหนดที่สอดคล้องกับคีย์

การลบคู่คีย์-ค่าออกจากไทรเกี่ยวข้องกับการค้นหาโหนดที่สอดคล้องกับคีย์ ตั้งค่าของโหนดนั้นเป็นค่าว่าง และลบโหนดที่ไม่มีลูกออกโดยวิธีเรียกซ้ำ^{[ 14 ] : 740}

Trie-Delete(x, key) ถ้า x = nil ให้คืนค่า nil มิฉะนั้น ถ้า key = "" แล้ว x.Value := nil อื่น x.Children[key[0]] := Trie-Delete(x.Children[key[0]], key[1:]) ถ้า x.Value ไม่เท่ากับ nil ให้คืนค่า x จากนั้นวนลูปสำหรับ 0 ≤ i < x.Children.length ถ้า x.Children[i] ไม่เท่ากับ nil ให้คืนค่า x จากนั้นวนลูปซ้ำและคืนค่า nil 

ขั้นตอนเริ่มต้นด้วยการตรวจสอบคีย์หากสตริงว่างแสดงว่ามาถึงโหนดที่ตรงกับคีย์ (เดิม) แล้ว ในกรณีนี้ค่าของคีย์จะถูกตั้งเป็น null หากโหนดนั้นมีค่าเป็น null และไม่มีโหนดลูก โหนดนั้นจะถูกลบออกจากไทรโดยการส่งค่า null กลับมา มิเช่นนั้น โหนดนั้นจะถูกเก็บไว้โดยการส่งค่าโหนดนั้นกลับมา

สามารถใช้ไทรแทนตารางแฮช ได้ ซึ่งมีข้อดีดังต่อไปนี้: ^{[ 12 ] : 358}

• การค้นหาโหนดที่มีคีย์ที่เกี่ยวข้องขนาดมีความซับซ้อนเท่ากับในขณะที่ฟังก์ชันแฮชที่ไม่สมบูรณ์อาจมีคีย์ที่ชนกันจำนวนมาก และความเร็วในการค้นหาในกรณีที่เลวร้ายที่สุดของตารางดังกล่าวจะเป็นโดยที่หมายถึงจำนวนโหนดทั้งหมดภายในตาราง${\displaystyle m}$${\displaystyle O(m)}$${\displaystyle O(N)}$${\displaystyle N}$
• โครงสร้างข้อมูลแบบไทร (Trie) ไม่จำเป็นต้องใช้ฟังก์ชันแฮชในการดำเนินการ ต่างจากตารางแฮช (Hash Table) นอกจากนี้ยังไม่มีการชนกันของคีย์ที่แตกต่างกันในโครงสร้างข้อมูลแบบไทร อีกด้วย
• ภายในโครงสร้างข้อมูลแบบไทร (trie) สามารถจัดเรียงคีย์ตามลำดับตัวอักษรได้ อย่างมีประสิทธิภาพ

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

โครงสร้างข้อมูลแบบไทรสามารถแสดงได้หลายวิธี ซึ่งสอดคล้องกับการแลกเปลี่ยนที่แตกต่างกันระหว่างการใช้หน่วยความจำและความเร็วในการดำเนินการ^{[ 5 ] : 341} การใช้เวกเตอร์ของตัวชี้เพื่อแสดงโครงสร้างข้อมูลแบบไทรนั้นใช้พื้นที่มหาศาล อย่างไรก็ตาม พื้นที่หน่วยความจำสามารถลดลงได้โดยแลกกับเวลาในการทำงาน หาก ใช้ รายการเชื่อมโยงเดี่ยวสำหรับเวกเตอร์โหนดแต่ละโหนด เนื่องจากรายการส่วนใหญ่ของเวกเตอร์ประกอบด้วย[ ^{3 ] : 495} ${\displaystyle {\text{nil}}}$

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

Bitwise tries ใช้เพื่อแก้ปัญหาความต้องการพื้นที่จำนวนมหาศาลสำหรับโหนด trie ในการใช้งานเวกเตอร์พอยเตอร์แบบง่ายๆ แต่ละอักขระในชุดคีย์สตริงจะถูกแทนด้วยบิตแต่ละตัว ซึ่งใช้ในการท่อง trie เหนือคีย์สตริง การใช้งาน trie ประเภทนี้ใช้คำสั่ง CPU แบบเวกเตอร์ เพื่อ ค้นหาบิตที่ตั้งค่าตัวแรกในอินพุตคีย์ที่มีความยาวคงที่ (เช่นฟังก์ชันภายในของGCC ) ดังนั้น บิตที่ตั้งค่าจึงถูกใช้เพื่อจัดทำดัชนีรายการแรก หรือโหนดลูก ในต้นไม้บิตwise ที่มี 32 หรือ 64 รายการ จากนั้นการค้นหาจะดำเนินการโดยการทดสอบแต่ละบิตถัดไปในคีย์^{[ 17 ]}__builtin_clz()

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

Radix treeหรือที่รู้จักกันในชื่อcompressed trieคือ trie รูปแบบที่ปรับให้เหมาะสมกับพื้นที่จัดเก็บ โดยที่โหนดใดๆ ที่มีลูกเพียงตัวเดียวจะถูกรวมเข้ากับโหนดแม่ การกำจัดกิ่งของโหนดที่มีลูกเพียงตัวเดียวส่งผลให้เมตริกดีขึ้นทั้งในด้านพื้นที่จัดเก็บและเวลา^{[ 18 ] [ 19 ] : 452} วิธีนี้ได้ผลดีที่สุดเมื่อ trie ยังคงคงที่และชุดของคีย์ที่จัดเก็บนั้นกระจัดกระจายมากภายในพื้นที่การแสดงผล^{[ 20 ] : 3–16}

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

การแสดงผลแบบต้นไม้แพทริเซียของชุดสตริง{in, integer, interval, string, structure }

ต้นไม้แพทริเซียเป็นการใช้งานเฉพาะของไทรไบนารีแบบบีบอัดที่ใช้การเข้ารหัสไบนารีของคีย์สตริงในการแสดงผล^{[ 21 ] [ 15 ] : 140} ทุกโหนดในต้นไม้แพทริเซียจะมีดัชนีที่เรียกว่า "หมายเลขข้าม" ซึ่งเก็บดัชนีการแตกแขนงของโหนดเพื่อหลีกเลี่ยงต้นไม้ย่อยที่ว่างเปล่าระหว่างการสำรวจ^{[ 15 ] : 140-141} การใช้งานไทรแบบง่ายๆ จะใช้พื้นที่จัดเก็บมหาศาลเนื่องจากจำนวนโหนดใบที่มากขึ้นซึ่งเกิดจากการกระจายคีย์แบบเบาบาง ต้นไม้แพทริเซียจึงมีประสิทธิภาพสำหรับกรณีดังกล่าว^{[ 15 ] : 142 [ 22 ] : 3}

ภาพแสดงโครงสร้างต้นไม้แพทริเซียแสดงอยู่ทางด้านขวา ค่าดัชนีแต่ละค่าที่อยู่ติดกับโหนดแสดงถึง "หมายเลขข้าม" ซึ่งเป็นดัชนีของบิตที่จะใช้ในการตัดสินใจแยกสาขา^{[ 22 ] : 3} หมายเลขข้าม 1 ที่โหนด 0 สอดคล้องกับตำแหน่งที่ 1 ใน ASCII ที่เข้ารหัสแบบไบนารี ซึ่งบิตซ้ายสุดแตกต่างกันในชุดคีย์X ^{[ 22 ] : 3-4} หมายเลขข้ามมีความสำคัญต่อการค้นหา การแทรก และการลบโหนดในต้นไม้แพทริเซีย และจะมีการดำเนินการปิดบังบิต ในทุก รอบ การวนซ้ำ ^{[ 15 ] : 143}

โครงสร้างข้อมูล Trie มักใช้ในพจนานุกรมข้อความทำนายหรือ พจนานุกรม เติมคำอัตโนมัติและอัลกอริธึมการจับคู่โดยประมาณ [ ^{11 ] Trie}ช่วยให้การค้นหาเร็วขึ้น ใช้พื้นที่น้อยลง โดยเฉพาะอย่างยิ่งเมื่อชุดข้อมูลมีสตริงสั้นๆ จำนวนมาก จึงใช้ในการตรวจสอบการสะกดคำ การแบ่งคำ และอัลกอริธึมการจับคู่คำนำหน้าที่ยาวที่สุด^{[ 8 ] [ 12 ] : 358} อย่างไรก็ตาม หากจำเป็นต้องจัดเก็บเฉพาะคำในพจนานุกรม (เช่น ไม่จำเป็นต้องจัดเก็บข้อมูลเมตาที่เกี่ยวข้องกับแต่ละคำ) ออโตมาตาสถานะจำกัดแบบไม่มีวงจรที่กำหนดขั้นต่ำ (DAFSA) หรือต้นไม้รากจะใช้พื้นที่จัดเก็บน้อยกว่า Trie เนื่องจาก DAFSA และต้นไม้รากสามารถบีบอัดสาขาที่เหมือนกันจาก Trie ที่สอดคล้องกับคำต่อท้าย (หรือส่วนต่างๆ) ของคำต่างๆ ที่จัดเก็บไว้ พจนานุกรมสตริงยังถูกนำมาใช้ในการประมวลผลภาษาธรรมชาติเช่น การค้นหาคำศัพท์ของคลังข้อความ^{[ 23 ] : 73}

การเรียงลำดับแบบเลกซิโคกราฟิกของชุดคีย์สตริงสามารถนำไปใช้ได้โดยการสร้างไทรสำหรับคีย์ที่กำหนดและท่องไปตามต้นไม้ในลักษณะพรีออร์เดอร์^{[ 24 ]}ซึ่งเป็นรูปแบบหนึ่งของ การเรียงลำดับแบบ เรดิกซ์เช่นกัน^{[ 25 ]}ไทรยังเป็นโครงสร้างข้อมูลพื้นฐานสำหรับเบิร์สต์ซอร์ตซึ่งโดดเด่นในฐานะอัลกอริธึมการเรียงลำดับสตริงที่เร็วที่สุดในปี 2007 ^{[ 26 ]} ซึ่งทำได้โดย การใช้แคช CPU อย่างมีประสิทธิภาพ ^{[ 27 ]}

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

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

มีการใช้ Trie ในชีวสารสนเทศโดยเฉพาะอย่างยิ่งใน แอปพลิเคชันซอฟต์แวร์ การจัดเรียงลำดับเช่นBLASTซึ่งจัดทำดัชนีสตริงย่อยที่แตกต่างกันทั้งหมดที่มีความยาวk (เรียกว่าk-mers ) ของข้อความโดยการจัดเก็บตำแหน่งของการเกิดขึ้นในฐานข้อมูลลำดับ Trie ที่บีบอัด^{[ 23 ] : 75}

รูปแบบที่บีบอัดของไทร เช่น ฐานข้อมูลสำหรับการจัดการForwarding Information Base (FIB) ใช้ในการจัดเก็บคำนำหน้าที่อยู่ IPภายในเราเตอร์และบริดจ์สำหรับการค้นหาตามคำนำหน้าเพื่อแก้ไข การดำเนินการ ตามมาสก์ใน การ กำหนดเส้นทาง IP ^{[ 23 ] : 75}

วิกิมีเดียคอมมอน ส์มีสื่อที่เกี่ยวข้องกับTrie

ลองค้นหาคำว่า trieใน Wiktionary ซึ่งเป็นพจนานุกรมฟรี

• พจนานุกรมอัลกอริทึมและโครงสร้างข้อมูลของ NIST: ไทร (Trie)