Бинарни дрва AVL дрва B Дрва Red/Black дрва
Напредни видови дрва
BST...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Преглед
1 ...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Преглед
1 ...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Бинарно дрво
Дрво со...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Комплетно бинарно дрво
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Комплетно бинарно дрво
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Дегенерирано бинарно дрво
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Дегенерирано бинарно дрво
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Дегенерирано бинарно дрво
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Балансирано бинарно дрво
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Балансирано бинарно дрво
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Преглед
1 ...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Ротирање на бинарни дрва
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Ротирање на...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Примери и вежби
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Преглед
1 ...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
AVL дрво
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Време за извршување
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Баланс фактор
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
AVL дрво
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Преглед
1 ...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Вметнување
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Ротирање
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Бришење
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Пребарување
Исто ...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Преглед
1 ...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
B Дрво
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
B Дрво
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
B Дрво
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Преглед
1 ...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Вметнувањ...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Бришење
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Пребарување
Исто како...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Преглед
1 ...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Red/Black дрво
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Red/Black дрво
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Red/Black дрво
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Red/Black дрво
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Преглед
1 ...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Операции со Црвено/Црни дрва
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Операции со Црвено/Црни дрва
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Пример
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Заклучок
...
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Прашања пред краj?
Бинарни дрва AVL дрва B Дрва Red/Black дрва
Прашања пред краj?
Благода...
of 47

Napredni vidovi drva

BST, AVL, B-, Red/Black
Published on: Mar 3, 2016
Source: www.slideshare.net


Transcripts - Napredni vidovi drva

  • 1. Бинарни дрва AVL дрва B Дрва Red/Black дрва Напредни видови дрва BST, AVL, B , Red/Black Васил Танески Институт за информатика Природно – математички факултeт 18.12.2007 / ПРК
  • 2. Бинарни дрва AVL дрва B Дрва Red/Black дрва Преглед 1 Бинарни дрва Видови и дефиниции Ротирање на бинарни дрва 2 AVL дрва Дефинициjа Операции со AVL дрва 3B Дрва Дефиниции Операции со B дрва 4 Red/Black дрва Дефиниции Операции со Црвено/Црно дрва
  • 3. Бинарни дрва AVL дрва B Дрва Red/Black дрва Преглед 1 Бинарни дрва Видови и дефиниции Ротирање на бинарни дрва 2 AVL дрва Дефинициjа Операции со AVL дрва 3B Дрва Дефиниции Операции со B дрва 4 Red/Black дрва Дефиниции Операции со Црвено/Црно дрва
  • 4. Бинарни дрва AVL дрва B Дрва Red/Black дрва Бинарно дрво Дрво со наjмногу две деца. • Вистинско бинарно дрво • Комплетно бинарно дрво • Дегенерирано бинарно дрво • Балансирано бинарно дрво
  • 5. Бинарни дрва AVL дрва B Дрва Red/Black дрва Комплетно бинарно дрво def. Комплетно бинарно дрво е дрво со n нивоа, каде во секое ниво d ≤ n − 1 има точно 2d jазли и jазлите во n–тото ниво се пополнети од лева страна.
  • 6. Бинарни дрва AVL дрва B Дрва Red/Black дрва Комплетно бинарно дрво слика
  • 7. Бинарни дрва AVL дрва B Дрва Red/Black дрва Дегенерирано бинарно дрво def. Дегенерирано бинарно дрво е дрво каде секоj jазол–татко е татко на само едно дете. Ова бинарно дрво се однесува како листа
  • 8. Бинарни дрва AVL дрва B Дрва Red/Black дрва Дегенерирано бинарно дрво слика 1
  • 9. Бинарни дрва AVL дрва B Дрва Red/Black дрва Дегенерирано бинарно дрво слика 2
  • 10. Бинарни дрва AVL дрва B Дрва Red/Black дрва Балансирано бинарно дрво def. Балансирано бинарно дрво е дрво во кое разликата ме´у г било кои два листа е 1.
  • 11. Бинарни дрва AVL дрва B Дрва Red/Black дрва Балансирано бинарно дрво слика
  • 12. Бинарни дрва AVL дрва B Дрва Red/Black дрва Преглед 1 Бинарни дрва Видови и дефиниции Ротирање на бинарни дрва 2 AVL дрва Дефинициjа Операции со AVL дрва 3B Дрва Дефиниции Операции со B дрва 4 Red/Black дрва Дефиниции Операции со Црвено/Црно дрва
  • 13. Бинарни дрва AVL дрва B Дрва Red/Black дрва Ротирање на бинарни дрва дефинициjа Операциjа при коjа се менува структурата на бинарното дрво, но не и inorder редоследот. • Единечна ротациjа - Лева ротациjа - Десна ротациjа • Двоjа ротациjа - Лева/десна ротациjа - Десна/лев ротациjа
  • 14. Бинарни дрва AVL дрва B Дрва Red/Black дрва Ротирање на бинарно дрво слика Истото бинарно дрво од сликата 1 на Дегенерирани б.д.
  • 15. Бинарни дрва AVL дрва B Дрва Red/Black дрва Примери и вежби http://bach.taneski.com/applet/rot/
  • 16. Бинарни дрва AVL дрва B Дрва Red/Black дрва Преглед 1 Бинарни дрва Видови и дефиниции Ротирање на бинарни дрва 2 AVL дрва Дефинициjа Операции со AVL дрва 3B Дрва Дефиниции Операции со B дрва 4 Red/Black дрва Дефиниции Операции со Црвено/Црно дрва
  • 17. Бинарни дрва AVL дрва B Дрва Red/Black дрва AVL дрво Прво дрво од овоj вид (самобалансирачки дрва). Г. Аделсон–Велски и Е. Ландис 1962
  • 18. Бинарни дрва AVL дрва B Дрва Red/Black дрва Време за извршување За трите основни операции: • Вметнување • Пребарување • Бришење (log n)
  • 19. Бинарни дрва AVL дрва B Дрва Red/Black дрва Баланс фактор За секоj jазол покраj вредност и Баланс фактор ∈ {−1, 0, 1}. def. Баланс фактор на AVL дрво е разликата ме´у висините на г десното и левото поддрво.
  • 20. Бинарни дрва AVL дрва B Дрва Red/Black дрва AVL дрво слика
  • 21. Бинарни дрва AVL дрва B Дрва Red/Black дрва Преглед 1 Бинарни дрва Видови и дефиниции Ротирање на бинарни дрва 2 AVL дрва Дефинициjа Операции со AVL дрва 3B Дрва Дефиниции Операции со B дрва 4 Red/Black дрва Дефиниции Операции со Црвено/Црно дрва
  • 22. Бинарни дрва AVL дрва B Дрва Red/Black дрва Вметнување • Класично изминување до точната локациjа • Класично вметнување • Ажурирање на баланс факторите движеj´ и се кон к коренот • Ротирање ако новиот баланс фактор на некоj jазол е −2 или 2
  • 23. Бинарни дрва AVL дрва B Дрва Red/Black дрва Ротирање • Ако е −2 (левата страна повисока) десна ротациjа • Ако е 2 (десната страна повисока) лева ротациjа
  • 24. Бинарни дрва AVL дрва B Дрва Red/Black дрва Бришење Слично како и за вметнувањето. • Класично изминување до точната локациjа • Бришење како при BST • Ажурирање на баланс факторите движеj´ и се кон к коренот • Ротирање ако новиот баланс фактор на некоj jазол е −2 или 2
  • 25. Бинарни дрва AVL дрва B Дрва Red/Black дрва Пребарување Исто како и каj BST.
  • 26. Бинарни дрва AVL дрва B Дрва Red/Black дрва Пример http://bach.taneski.com/applet/ ´ Ке направиме AVL дрво со следните вредности: (во во овоj редослед) 8, 9, 13, 3, 4, 2, 10, 14, 12, 11, 7, 6, 5, 15, 1
  • 27. Бинарни дрва AVL дрва B Дрва Red/Black дрва Преглед 1 Бинарни дрва Видови и дефиниции Ротирање на бинарни дрва 2 AVL дрва Дефинициjа Операции со AVL дрва 3B Дрва Дефиниции Операции со B дрва 4 Red/Black дрва Дефиниции Операции со Црвено/Црно дрва
  • 28. Бинарни дрва AVL дрва B Дрва Red/Black дрва B Дрво За разлика од AVL и Red/Black дрвото ова не бинарно дрво. Rudolf Bayer и Ed McCreight 1972
  • 29. Бинарни дрва AVL дрва B Дрва Red/Black дрва B Дрво дефинициjа def. B дрво е дрво од ред m > 1 кое задоволува: • секоj jазол има m ≤ m деца 2 • коренот има барем 2 деца • сите лисjа имаат се на исто ниво (имаат иста висина) • Внатрешен jазол со k деца има k − 1 вредности
  • 30. Бинарни дрва AVL дрва B Дрва Red/Black дрва B Дрво слика
  • 31. Бинарни дрва AVL дрва B Дрва Red/Black дрва Преглед 1 Бинарни дрва Видови и дефиниции Ротирање на бинарни дрва 2 AVL дрва Дефинициjа Операции со AVL дрва 3B Дрва Дефиниции Операции со B дрва 4 Red/Black дрва Дефиниции Операции со Црвено/Црно дрва
  • 32. Бинарни дрва AVL дрва B Дрва Red/Black дрва Вметнување Секое вметнување е на листовите. • Класично изминување до точната локациjа • Ако листот има помалку вредности од максималниот, вметнуваме тука (задржуваj´и го редоследот) к • Ако нема помалку од максималниот броj вредности: - Избираме средина ме´у вредностите вклучуваj´и jа и г к новата вредност - Вредностите помали од избраната ги ставаме во нов jазол лево, а поголемите во нов десно. - Избраната се вметнува каj таткото, што може да го продолжи делењето нагоре.
  • 33. Бинарни дрва AVL дрва B Дрва Red/Black дрва Бришење Се пронао´а елементот коj треба да се избрише, се брише и г се преструктуира дрвото нагоре. Наjлесно е бришење во лисjата.
  • 34. Бинарни дрва AVL дрва B Дрва Red/Black дрва Пребарување Исто како и каj BST дрвата.
  • 35. Бинарни дрва AVL дрва B Дрва Red/Black дрва Пример http://bach.taneski.com/applet/ ´ Ке направиме B дрво со следните вредности: (во во овоj редослед) 8, 9, 13, 3, 4, 2, 10, 14, 12, 11, 7, 6, 5, 15, 1
  • 36. Бинарни дрва AVL дрва B Дрва Red/Black дрва Преглед 1 Бинарни дрва Видови и дефиниции Ротирање на бинарни дрва 2 AVL дрва Дефинициjа Операции со AVL дрва 3B Дрва Дефиниции Операции со B дрва 4 Red/Black дрва Дефиниции Операции со Црвено/Црно дрва
  • 37. Бинарни дрва AVL дрва B Дрва Red/Black дрва Red/Black дрво Симетрично бинарно B дрво Rudolph Bayer 1972 Исто како и двете претходните дрва, за сите операции времето е (log n)
  • 38. Бинарни дрва AVL дрва B Дрва Red/Black дрва Red/Black дрво дефинициjа def. Црвено/Црно дрво е самобалансирачко бинарно пребарувачко дрво. Покраj вредност секоj jазол има и боjа ∈ црвена, црна . Треба да биде запазено и: • Секоj jазол има или црвена или црна боjа. • Коренот има црна боjа. • Сите лисjа се црни (лисjата се nil) • Двете деца на црвен jазол се црни. • Патеката од било коj jазол до било коj лист коj призлегува од него содржи ист броj на црни jазли.
  • 39. Бинарни дрва AVL дрва B Дрва Red/Black дрва Red/Black дрво Red/Black дрво Претходно наведените ограничувања jа наметнуваат главната особина на R/B дрвата: Наjдолгиот пат од коренот до некоj лист е не пове´е од два к пати подолг од наjкраткиот пат во дрвото.
  • 40. Бинарни дрва AVL дрва B Дрва Red/Black дрва Red/Black дрво слика
  • 41. Бинарни дрва AVL дрва B Дрва Red/Black дрва Преглед 1 Бинарни дрва Видови и дефиниции Ротирање на бинарни дрва 2 AVL дрва Дефинициjа Операции со AVL дрва 3B Дрва Дефиниции Операции со B дрва 4 Red/Black дрва Дефиниции Операции со Црвено/Црно дрва
  • 42. Бинарни дрва AVL дрва B Дрва Red/Black дрва Операции со Црвено/Црни дрва Операциите вметнување и бришење за овие дрва се доста комплексни. • При вметнување постоjат 5 различни случаи • При бришење 6 различни случаи Пребарувањето е исто како и каj BSD дрвата. ´ Ке ги разгледаме на примерот.
  • 43. Бинарни дрва AVL дрва B Дрва Red/Black дрва Операции со Црвено/Црни дрва Иако тешки за имплементациjа овие дрва се доста користени поради доброто време на извршување при наjлош случаj.
  • 44. Бинарни дрва AVL дрва B Дрва Red/Black дрва Пример http://bach.taneski.com/applet/ ´ Ке направиме Црвено/Црно дрво со следните вредности: (во во овоj редослед) 8, 9, 13, 3, 4, 2, 10, 14, 12, 11, 7, 6, 5, 15, 1
  • 45. Бинарни дрва AVL дрва B Дрва Red/Black дрва Заклучок За да се искористи придобивката на логаритамско време за пребарување/вметнување/бришење елементи на структурата дрво балансирањето е многу битно.
  • 46. Бинарни дрва AVL дрва B Дрва Red/Black дрва Прашања пред краj?
  • 47. Бинарни дрва AVL дрва B Дрва Red/Black дрва Прашања пред краj? Благодарам за вниманието.

Related Documents