درخت پسوندی
پیاده‌سازی

اگر هر گره و یال را بتوان در فضای حافظه‌ای از  \Theta (1) ذخیره کرد، می‌توان تمام درخت را در فضای حافظه‌ای از  \Theta (n) ذخیره نمود. جمع طول تمامی رشته‌های روی همه‌ی یال‌ها در درخت از  O(n^{2}) است، اما هر یال می‌تواند با دو عدد به صورت مکان و طول زیررشته‌ای از  S ذخیره شود؛ که در کل ذخیره‌ی همه‌ی یال‌ها حافظه‌ای از  \Theta (n) اشغال می‌کند.
در اینجا دو روش برای ساخت درخت پسوندی را بررسی می‌کنیم.
در زمان  O(n^{2})
به عنوان یک روش ساده برای حالتی که طول رشته کوتاه است می‌توانیم از آن استفاده کنیم. کافی است تمام پسوند‌ها را در یک درخت پیشوندی درج کنیم.
در زمان  O(n)، Ukkonen's algorithm
این الگوریتم ساخت درخت پسوندی را به تعداد فاز تقسیم می‌کند که هرکدام مراحلی دارند. در فاز  i ام، برای اولین بار حرف  i ام رشته را در نظر میگیریم و بعد از تمام شدن آن انتظار داریم تمام پسوند‌های زیررشته  S[1..i] در درخت درج شده باشند. در هر مرحله  j از این فاز،  S[j..i] درج می‌شود. قبل از فاز  i ام فاز  i-1 تمام شده، پس رشته  S[j..i-1] را داخل درخت جستجو می‌کنیم. ۳ حالت امکان دارد رخ دهد که در هر حالت طبق قانون خاصی ادامه می‌دهیم.
رشته کامل پیدا می‌شود و مسیر در یک راس برگ تمام می‌شود. در این حالت حرف  i ام به آخرین یال اضافه می‌شود و راس جدیدی هم نمی‌سازیم.
رشته کامل پیدا می‌شود و مسیر وسط یک یال تمام می‌شود و حرف بعدی رشته روی یال برابر   S[i] نیست یا مسیر روی یک راس درونی‌(غیر برگ) تمام می‌شود. اگر مسیر روی راس درونی تمام شود، یک برگ جدید ایجاد می‌کنیم. در حالت اول یک راس میانی و یک برگ جدید ایجاد می‌کنیم.
پسوند  S[j..i-1] پیدا می‌شود و مسیر روی یال تمام می‌شود در حالی که حرف بعدی آن مساوی  S[i] است. در این حالت هیچ بروزرسانی‌ای انجام نمی‌شود.
اگر همه فاز‌ها و مراحل را به شکل جستجوی جامع انجام دهیم چون  n فاز  n مرحله‌ای داریم و جستجوی درخت هم  O(n) است در نهایت الگوریتم از  O(n^{3}) می‌شود. برای کاهش آن از پیوند‌های پسوندی استفاده می‌کنیم.
تعریف پیوند پسوندی: فرض کنید رشته  X در درخت وجود دارد و مسیر آن به راس  v ختم می‌شود. رشته  aX ‌(  a حرفی دلخواه از الفبا) هم موجود است و به راس  u ختم می‌شود. به پیوندی از راس  u به  v پیوند پسوندی گفته می‌شود. در شکل اول این پیوند‌ها با خط‌چین نشان داده شده‌اند.
وقتی در حال انجام مرحله  j فاز  i هستیم، باید انتهای مسیر  S[j..i-1] را بدانیم. همچنین در مرحله  j+1 مسیر  S[j+1..i-1]. قبل از انجام فاز  i فاز  i-1 انجام شده یعنی دو رشته  S[j..i-1] و  S[j+1..i-1] در درخت هستند.  S[j..i-1] همان  S[j][j+1..i-1] است پس ما یک پیوند پسوندی از راس انتهایی  S[j..i-1] به  S[j+1..i-1] داریم پس به جای جستجو از ریشه می‌توانیم از آن استفاده کنیم. در این حالت صرفا زمان جستجو بهتر می‌شود تا به  O(n^{2}) برسیم.
برای اینکه پیچیدگی زمان  O(n) شود حتما باید رشته‌های روی یال را به صورت زیر‌بازه‌ای از رشته اصلی ذخیره کنیم.  s[startIndex..endIndex] با ذخیره دو عدد شروع و پایان.
قوانینی که به آن اشاره شد، در یک فاز به ترتیب عمل می‌کنند. یعنی اولین مراحل قانون ۱ عمل می‌کند،‌ بعد مدتی دومی و در آخر همیشه حالت سوم رخ خواهد داد. پس مثلا وقتی به حالت ۳ برسیم دیگر انجام آن فاز عملا تمام شده. وقتی یک برگ جدید میسازیم، همیشه برگ باقی می‌ماند صرفا امکان دارد یال آن به پدرش طولانی شود.(در حالت ۱) همچنین برای تمام برگ‌ها  endIndex یکسان می‌ماند. پس در هر فاز قانون یک در زمان ثابت با ذخیره با لیست همگانی از  endIndex های برگ‌ها قابل انجام است.
وقتی قانون دوم اجرا می‌شود هم، برگ جدید ایجاد می‌شود. و اگر یکبار در مرحله  j اجرا شود، در تمامی فاز‌های بعدی این مرحله قانون اول رخ می‌دهد. پس در بدترین حالت  n بار اجرا می‌شود چون  n برگ داریم. پس طبق خاصیت‌های گفته شده مرتبه زمانی به  O(n) کاهش پیدا کرد.
یک نمونه از پیاده‌سازی آن به زبان  C++ را در اینجا ببینید.
یک انتخاب مهم هنگام پیاده‌سازی یک درخت پسوندی، رابطه‌ی پدر-فرزندی بین گره‌ها است. استفاده از یک نوع لیست پیوندی به نام لیست خواهر و برادرها متداول‌ترین نوع است. هر گره یک اشاره‌گر به فرزند اولش و یک اشاره‌گر به فرزند بعدی در لیست فرزندهایی که عضو آنها است، دارد. پیاده‌سازی‌های دیگر با زمان اجرای کارآمد از جداول درهم‌سازی، آرایه‌های مرتب یا نامرتب، (آرایه پویا)، یا درخت‌های جست‌وجوی دودویی خود-متوازن استفاده می‌کنند.
فاکتورهای زیر در پیاده سازی مهم هستند:
هزینه‌ی پیدا کردن یک فرزند با یک حرف داده شده
هزینه‌ی درج یک فرزند
هزینه‌ی پیدا کردن تمام فرزندان یک گره (تقسیم شده بر تعداد فرزندان در جدول زیر)
اگر  \sigma  تعداد حروف الفبا باشد، هزینه‌ها به شرح زیر است:
{\begin{array}{r|lll}&{\text{Lookup}}&{\text{Insertion}}&{\text{Traversal}}\\\hline {\text{Sibling lists / unsorted arrays}}&O(\sigma )&\Theta (1)&\Theta (1)\\{\text{Bitwise sibling trees}}&O(\log \sigma )&\Theta (1)&\Theta (1)\\{\text{Hash maps}}&\Theta (1)&\Theta (1)&O(\sigma )\\{\text{Balanced search tree}}&O(\log \sigma )&O(\log \sigma )&O(1)\\{\text{Sorted arrays}}&O(\log \sigma )&O(\sigma )&O(1)\\{\text{Hash maps + sibling lists}}&O(1)&O(1)&O(1)\end{array}}
هزینه‌ی درج سرشکن است، و هزینه‌ی درهم‌سازی برای درهم‌سازی کامل داده شده است.