ЛУ- 11
Дървета
Цел: Придобиване на пракически навици в дефинирането на дървовидни структури от данни, действия над тях и използването им в програми на С/С++
Теоретична част:
Дървото може да бъде определено като рекурсивна структура, състояща се от корен и поддървета, като поддървото също е дърво. Възлите се представят като структури(в C/C++), с членове - за значение( поне един) и указатели за следващ възел.
При двоичното дърво указателите са 2 – един за ляв и един за десен “син”. Пример за такова дърво е даден на следващата фиг.11.1:
Ред за
пристигане
на числата:
15,8,5,10,23 114,28
Фиг.11.1. Сортирано дърво по метода : “ляво_поддръво-корен-дясно_поддърво”
Задача 1: Сортиране и търсене в двоично дърво
Сортирането в двоично дърво е всъщност процесът на изграждане на дървото по реда на пристигащите елементи[9]. Един от алгоритмите подрежда всеки пристигнал елемент в лявото поддърво на корена, ако той е по-малък от корена, и в дясното поддърво – в обратен случай и това се повтаря рекурсивно, като всеки следващ възел става корен. Сортирането на дървото се свежда до намиране на място за новопостъпил елемент. При този подход оценката за сложността е
Т ср.мин = O(N*log N)
Тср.макс= О(N*N)
и зависи от големината на образуваното до момента дърво. Ако дървото е балансирано, то разстоянието от кой да е възел до корена не надвишава log N – оценката е минимална. Оценката е максимална при изродено (в линеен списък) дърво.
Следващата функция сортира (вмъква елемент в) двоично дърво.
void B_tree(pointer p){
if (p==NULL) {
p->L=NULL; p->R=NULL;}
else {
if (new_key>p->x)
B_tree(p->R);
else
B_tree(p->L);
}
Въпроси по темата и задачи за изпълнение:
1. Дайте пример с поредица от числени стойности, при постъпването на които, изгражданото дърво се изражда в линеен списък, ако сортирането е по метода “ляво_поддърво – корен – дясно_поддърво”?
2. Какви са оценките за Тср.мин и Тср.макс при претърсване на едно неизродено дърво? А при изродено дърво?
3. Да се напише програма на С/С++, която реализира сортиране на двоично дърво от числени елементи по метода “ляво_поддърво – корен – дясно_поддърво”
Сподели с приятели: |