Кожен вузол трійкового дерева пошуку зберігає один символ, об'єкт (або вказівник на об'єкт, залежно від реалізації), і три вказівники (троє дітей), умовно названих equal kid, lo kid і hi kid, які також можуть називатися відповідно як середня дитина, мала дитина і велика дитина[1] . Вузол може також мати вказівник на батьківський вузол, а також позначку того, чи є вузол кінцем слова. Вказівник lo kid повинен вказувати на вузол, значення символу якого менше ніж поточний вузол . Вказівник hi kid повинен вказувати на вузол, символ якого більше ніж значення у поточному вузлі[2]. Equal kid вказує на наступного символ у слові. На малюнку нижче показано трійкове дерево пошуку, яке зберігає у собі такі рядки: «cute», «cup», «at», «as», «he», «us» та «i»:
c
/ | \
a u h
| | | \
t t e u
/ / | / |
s p e i s
Як і у випадку з іншими видами префіксних дерев, кожен вузол у трійковому дереві пошуку представляє префікс збережених рядків. Усі рядки в середньому піддереві вузла починаються з цього префікса.
Застосування
Трійкове дерева пошуку використовуються для вирішення багатьох проблем, де потрібно зберегти велику кількість рядків і потім шукати чи діставати рядок у довільному порядку. Нижче наведено деякі найпоширеніші або найкорисніші з них:
Якщо вже використовується префіксне дерево, але потрібно забезпечити менше споживання пам'яті[1].
