Ребаланс на идеално-балансирано дърво за претърсване с пренаправяне на дървото


Категория на документа: Други


Нoв Бългaрcки Yнивeрcитeт

Реферат
пo
CSCB595

Тема: Ребаланс на идеално-балансирано дърво за претърсване с пренаправяне на
дървото

Изгoтвeн oт : Прeпoдaвaтeл:
Никoлaй Хриcтoв дoц. д-р Велина Славова

F-40461

Съдържание:

1. Въведение. Същност на дървото.
2. Елементи на дървото.
3. Видове дървета.
4. Търсене в подредено дърво.
5. Търсене в Идеално-балансирано дърво.
6. Примери за ротации.
7. Използвана литература.

1. Въведение. Същност на дървото.

Това е или празна структора или структора, която се състои от един специален елемент - корен на дървото и краен брой непресичащи се подмножества от елементи, всяко от които също представлява дърво (поддърво).

фиг.1 Илюстрация на дърво.

Дърветата са удобна структора за съхраняване на данни, когато е необходимо бързо търсене.

2. Елементи на дървото.

Елементите на дървото понякога се наричат възли, връзката възел - поддърво се нарича клон (ребра). Възлите от поддърветата на даден възел се наричат потомци (наследници), а той техен предшественик (баща, родител). Има преки и непреки предшественици, единственият възел без предшественици е корен на дървото, а възлите без потомци се наричат листа. Корените на поддърветата на даден възел се наричат братя. Ако от някой възел, преминавайки по някой от клоновете на неговите поддървета можем да достигнем до друг възел, то казваме, че между двата възела има път.

Осноените понятия при дърветата са:
- Ниво на възела - това е разтоянието до корена, дължината на пътя до корена. Корена има ниво 0, нивото на всеки един възел е с 1 по-голям от нивото на неговия баща. Разпределението на възлите по нива е причина дървото да се счита за йерархична структора от данни.
- Дълбочина (височина) на дървото - максималното ниво на листо от дървото т.е. най-дългия път (най-голямото разстояние) от корена до лист на дървото.
- Степен на възела - това е броят на синовете на възела.
- Тегло на дърво - броят на възлите в дървото.

3. Видове дървета.
- Подредено дърво - ако всеки елемент се подрежда в дървото в зависимост от някакъв признак (ключ)
- Балансирано дърво (с балансирана височина) - ако височината на всички поддървета се различва с не повече от 1.
- Идеално-балансирано дърво - наричат се още AVL-дървета в чест на Adelson Velskii и Landis, идеално-балансираните дървета са дървета, в които разликата в броя на възлите на лявото и дясното поддърво на всеки от върховете е най-много с единици.

Примери: Дърво със следната структура:

е идеално балансирано, но дърво със структура:




Сподели линка с приятел:





Яндекс.Метрика
Ребаланс на идеално-балансирано дърво за претърсване с пренаправяне на дървото 9 out of 10 based on 2 ratings. 2 user reviews.