Пређи на садржај

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

нема резимеа измене
{{МАТФ052013}}
[[Датотека:Unbalanced binary tree.svg|thumb|right|251px|Пример неизбалансираног стабла]]
[[Датотека:AVLtreef.svg|thumb|right|251px|Исто стабло полсепосле балансирања по висини]]
У [[рачунарским наукама]], '''само-балансирајуће бинарно стабло претраге''' је свако [[чвор]]-засновано [[бинарно стабло претраге]] које аутоматски одржава своју висину малом због нових уметања и брисања.
<ref name="knuth">
 
== Преглед ==
[[Датотека:BinaryTreeRotations.svg|thumb|300px|TreeРотирање rotationsстабла areсу veryврло commonчесте internalунутрашње operationsоперације onнад selfсамо-balancingбаланисрајућим binaryстаблом treesбинарне toпретраге keepда perfectби orзадржало near-to-perfectсавршен или скоро савршен balanceбаланс.]]
Већина операциај над бинарним стаблом претраге(БСП) је временски директно пропорцијонална висини стабла, тако да је поѕењно висину одржавати што мањом. Бинарно стабло са висином h може да садржи највише [[Геометријски низ|2<sup>0</sup>+2<sup>1</sup>+···+2<sup>''h''</sup>&nbsp;=&nbsp;2<sup>''h''+1</sup>&minus;1]] чворова. Следи да за дрво са n чворова и h висина:<br />
 
26

измена