Википедија

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

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
Нема описа измене
Нема описа измене
ознаке: Визуелно уређивање мобилна измена мобилно веб-уређивање
Ред 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 0-201-89685-0|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]] чворова. Следи да за дрво са n чворова и h висина:
 
<math>n\le2^{h+1}-1</math>
Ред 15:
<math>h\ge\lceil\log_2(n+1)-1\rceil\ge \lfloor\log_2 n\rfloor</math>.
 
Другим речима, минималнанајмања висина дрвета саод ''n'' чворова је [[Логаритам|log]]<sub>2</sub>(''n''), спратне и ћелијске функције; које су, <math> \lfloor \log_2 n\rfloor</math>:.<ref name="knuth"/>
 
Иначе, најједноставнији алгоритам БСП уметањем података може да носи стабло висине n у радије општим ситуацијама. На пример, када су подаци уметани у сротирани [[примарни кључ]], стабло се дегенерише у [[повезана листа|повезану листу]] са n чворова. Разлика у преформансама између две ситуације може бити огромна: за n=1,000,000, на пример, минимална висина је <math> \lfloor \log_2(n) \rfloor = 19 </math>.
Ред 23:
Само-балансирајуће бинарно стабло решава овај проблем изводећи трансформације над стаблом(као што су [[ротација стабла]] на књичним местима) да би задржала пропорцијоналну висину log<sub>2</sub>(''n'').
 
Одржавајучи висину на минималнојнајмањој вредности <math>\lfloor \log_2(n) \rfloor</math> није увек могуће; може бити доказано да сваки алгоритам уметања који то ради би имао прекомерно рачунање. Тиме, већина само-балансирајућих БСП алгоритама одржава висину у оквиру константног фактора доње границе.
 
У асимптотском смислу ([[Велико О]]), само-балансирајуће БСП структура садржавајући n података дозвољава проналажења, уметања, и уклањања података O(log ''n''), најгори случај, и [[обилазак стабла]] свих чланова O(n) времена. За неке имплементације ово је граница пре-операционог времена, док за неке су [[амортизација]] граница преко низа операција. Ова времена су асимптотски оптимална међу свим структурама података које манипулишу кључем кроз поређења.
Преузето из „https://sr.wikipedia.org/wiki/Самобалансирајуће_бинарно_стабло_претраге”