Самобалансирајуће бинарно стабло претраге — разлика између измена
Садржај обрисан Садржај додат
м ispravke |
|||
Ред 41:
Само-балансирајућа бинарна стабла претраге могу бити коришћена на природан начин да конструјиши и одржавају листе, као што је [[редни приоритет]]. Такође могу бити коришћена за [[асоцијативни низ]], кључним парововима је да једноставно буду уметнути са наручењем засновано само на кључу. У том својству, само-балансирајуће БСП има доста врлина и мана над главним конкурентом, [[хеш табела]]. Једна предност само-балансирајућег БСП је та да дозвољава брзо (свакако, симптотски оптимално) енумерациу података ''у кључном поретку'', што хеш табеле не пружају. Једна мана је та да њихови алгоритми претраге бива доста компликован кад постоји висе података са истим кључем. Само-балансирајуће БСП има боље горе-случајеве преформансе претраге него хеш табела (O(log n) у односу на O(n)), али има гори просечан-случај преформансе (O(log n) у односу на O(1)).
Само-балансирајуће БСП може бити корипћено да имплементира било који алгоритам који захтева requires променљиве листе, да би постигли оптимални најгори-случај асимптотске преформансе. На пример, ако [[Сортирање уз помоћ бинарног стабла]] је имплементирано са само-балансирајућим БСП-ом, имамо врло лако описив ипак [[асимптотски оптималан]] O(''n'' log ''n'') сортирајући алгоритам. Слично, многи алгоритми у [[рачунарској геометрији]] искоришћавају варијације над само-балансирајућим БСН-ом да реше проблеме као што су [[раскрснице дужи]] проблем и [[локације тачака]] ефикасно. (За просечан-случај преформанси, како год, само-балансирајуће БСП може да буде мање ефикасно од осталих солуција. Сортирање бинарног стабла, у пракси, вероватно ће бити спорије [[сортирање спајањем]], [[квиксорт]], or [[хипсорт]], због стабло-балаансирајућег рачунања а такође и
Само-балансирајућа БСП су флексибилне структуре података, у томе им је и лаксе да се прошире на ефикасније снимање података или извршавање нових операција. На пример, један може да сними одређен број чворова у сваком подстаблу имајући одређене особине, дозвољавајући једном да броји чворове у одређеном кључном растојању са тим особинама у O(log ''n'') времену. Ови наставци могу бити коришћени, на пример, да оптимизују упите базе података или друге алгоритме за обраду листа.
| |||