Википедија

Самобалансирајуће бинарно стабло претраге — разлика између измена

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
Нема описа измене
ознаке: Визуелно уређивање мобилна измена мобилно веб-уређивање
Autobot (разговор | доприноси)
1.572.075 измена
м Бот: обликујем ISBN; козметичке измене
Ред 1:
[[Датотека:Unbalanced binary tree.svg|thumbмини|rightдесно|251px|Пример неуравнотеженог стабла]]
[[Датотека:AVLtreef.svg|thumbмини|rightдесно|251px|Исто стабло после балансирања по висини]]
У [[рачунарство|рачунарству]], '''само-балансирајуће бинарно стабло претраге''' је свако [[бинарно стабло претраге]] које је засновано на [[Чвор|чворовимачвор]]овима и које аутоматски одржава своју висину након нових уметања и брисања.<ref name="knuth">[[Доналд Кнут|Donald Knuth]]. ''The Art of Computer Programming'', Volume 3: ''Sorting and Searching'', Second Edition. Addison-Wesley. {{page|year=1998|id=ISBN 978-0-201-89685-05|pages=}} Section 6.2.3: Balanced Trees, pp. 458-481.</ref>
 
Ова структура ефикасно омогућава имплементацију променљиво распоређених [[листа]], и може се користити за другу [[апстрактна структура података|апстрактну структуру података]] као што је [[асоцијативни низ]], [[редни приоритети]] и [[Скуп|сет]].
 
== Преглед ==
[[Датотека:BinaryTreeRotations.svg|thumbмини|300px|Ротирање стабла су врло честе унутрашње операције над само-баланисрајућим стаблом бинарне претраге које се користе да би стабло задржало савршен или скоро савршен баланс.]]
Већина операција над бинарним стаблом претраге(БСП) је временски директно сразмерна висини стабла, тако да је пожељно висину одржавати што мањом. Бинарно стабло са висином h може да садржи највише [[геометријска прогресија|2<sup>0</sup>+2<sup>1</sup>+···+2<sup>''h''</sup>&nbsp;=&nbsp;2<sup>''h''+1</sup>&minus;1−1]] чворова. Следи да за дрво са n чворова и h висина:
 
<math>n\le2^{h+1}-1</math>
Преузето из „https://sr.wikipedia.org/wiki/Самобалансирајуће_бинарно_стабло_претраге”