На упражнението споменахме някои дървета. Навсякъде, където говорим за индексиране или търсене в данни, задължително стигаме до необходимостта от ефективни структури от данни.

Когато разглеждаме коя да е структура от данни, важно е да обърнем внимание на следните критерии:

    Колко бързо добавяме елемент
    Колко бързо извличаме елемент
    Колко бързо трием елемент
    Колко памет заема структурата

Хубавото на дърветата е, че по първите 3 точки се справят с логаритмична сложност, а по четвъртата точка са също доста ефективни.

По-долу са няколко Wiki страници, в които има по-подробни описания на споменатите дървета, за любознателните от вас:

    Дървета(увод) - http://www.introprogramming.info/intro-csharp-book/read-online/glava17-durveta-i-grafi/
    B-дърво(споменахме го по-накратко предния път): http://en.wikipedia.org/wiki/B-tree
    Префиксно дърво(дърво на представките на думи, trie): http://en.wikipedia.org/wiki/Trie
    Компактно префиксно дърво(radix tree, patricia trie): http://en.wikipedia.org/wiki/Radix_tree
    Суфиксно дърво(дърво на наставките на думите): http://en.wikipedia.org/wiki/Suffix_tree

Последно модифициране: неделя, 24 март 2013, 12:12