პრეფიქსული ხე

კომპიუტერულ მეცნიერებაში, პრეფიქსული ხე, ასევე ცნობილი როგორც ციფრული ხე, არის სპეციალიზებული ძებნის ხის მონაცემთა სტრუქტურა, რომელიც გამოიყენება სიმრავლეში სტრინგების შენახვასა და მოძიებისთვის. ორობითი ძებნის ხისგან განსხვავებით, ნოდები პრეფიქსულ ხეში არ ინახავენ ასოცირებულ მნიშვნელობას. არამედ თითოეული ნოდის პოზიცია განსაზღვრავს მისთვის ასოცირებულ მნიშვნელობას.

პრეფიქსული ხეები უპირატესობას წარმოადგენენ ჰაშ-ცხრილებთან შედარებით, რაც განსაკუთრებით აისახება ისეთი დავალებებისთვის, როგორიცაა მართლწერის შემოწმება და IP როუტინგი. თითოეული შვილი ნოდი იზიარებს იმავე პრეფიქსს, რასაც მისი მშობელი; ფუძის ნოდი ცარიელ სტრინგს წარმოადგენს. რადგანაც შესაძლოა პრეფიქსული ხის საბაზისო იმპლემენტაციები მეხსიერება-ინტენსური იყოს, მათი ეფექტურობის გასაუმჯობესებლად შემუშავებულია ოპტიმიზაციები, როგორიცაა შეკუმშვა და ბიტური წარდგენა. აღსანიშნავია რადიქსული ხე.

 მიმოხილვა 
პრეფიქსული ხე ძებნის მონაცემთა სტრუქტურაა, რომელიც გამოიყენება სიტყვების ისე შესანახად, რომ მათი მოძიებაც ეფექტური იყოს. იგი წარმოადგენს დალაგებულ ხეს, რომელიც აღწერს სასრული ალფაბეტიდან შედგენილი სტრინგების იმ ნაკრებს, რომლებსაც საერთო პრეფიქსი გააჩნიათ.

 ოპერაციები 
პრეფიქსული ხე მხარს უჭერს ოპერაციებს როგორიცაა ჩასმა, წაშლა და ძიება. ის შედგება ნოდებისგან, რომლებიც შეიცავენ ბმულებს; თითოეული ბმული მიუთითებს სხვა სუფიქსის შვილობილ ნოდზე, ან ნულზე. როგორც ყველა ხის, ასევე პრეფიქსული ხის თითოეული ნოდი (ფუძის გარდა), მიუთითებს მხოლოდ ერთ სხვა მშობელ ნოდზე, თითოეული ნოდი შეიცავს იმდენ ბმულს, რამდენ სიმბოლოსაც შეიცავს შესაბამისი ალფაბეტი.

ნოდის ძირითადი სტრუქტურის ტიპი პრეფიქსულ ხეში შემდეგნაირია; ნოდი Node შეიძლება შეიცავდეს არასავალდებულო მნიშვნელობას value.struct Node:
    children: Node[AlphabetSize]
    is_terminal: Boolean
    value: DataT</code>

კატეგორია:მონაცემთა სტრუქტურა