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

С Википедије, слободне енциклопедије
Садржај обрисан Садржај додат
Нема описа измене
Нема описа измене
Ред 3: Ред 3:
[[Датотека:AVLtreef.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, 1998. ISBN 0-201-89685-0. Section 6.2.3: Balanced Trees, pp.458&ndash;481.}-</ref>
<ref name="knuth">
[[Donald Knuth]]. ''The Art of Computer Programming'', Volume 3: ''Sorting and Searching'', Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 6.2.3: Balanced Trees, pp.458&ndash;481.
</ref>


Ова структура ефикасно омогућава имплементацију променљиво распоређених [[листа]], и може се користити за другу [[апстрактна структура података|апстрактну структуру података]] као што је [[асоцијативни низ]], [[редни приоритети]] и [[Скуп|сет]].

Ова структура ефикасно омогућава имплементацију променљиво распоређених [[листа]], и може се користити за другу [[апстрактну структуру података]] као што је [[асоцијативни низ]], [[редни приоритети]] и [[Скуп|сет]].


== Преглед ==
== Преглед ==
[[Датотека:BinaryTreeRotations.svg|thumb|300px|Ротирање стабла су врло честе унутрашње операције над само-баланисрајућим стаблом бинарне претраге да би задржало савршен или скоро савршен баланс.]]
[[Датотека: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 висина:<br />
Већина операциај над бинарним стаблом претраге(БСП) је временски директно пропорцијонална висини стабла, тако да је поѕењно висину одржавати што мањом. Бинарно стабло са висином 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> <br />
<math>n\le2^{h+1}-1</math>


Што подразумева:<br />
Што подразумева:


<math>h\ge\lceil\log_2(n+1)-1\rceil\ge \lfloor\log_2 n\rfloor</math>.<br />
<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"/><br />
Другим речима, минимална висина дрвета са ''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>.<br />
Иначе, најједноставнији алгоритам БСП уметањем података може да носи стабло висине n у радије општим ситуацијама. На пример, када су подаци уметани у сротирани [[примарни кључ]], стабло се дегенерише у [[повезана листа|повезану листу]] са n чворова. Разлика у преформансама између две ситуације може бити огромна: за n=1,000,000, на пример, минимална висина је <math> \lfloor \log_2(n) \rfloor = 19 </math>.


Ако су подаци познати пре времена, висина се може одржати малом, у просечном смислу, додавањем вредности у насумичном поретку, резултујући у [[произвољно бинарно стабло претраге]]. Како било,има много ситуација(као што су [[мрежни алгоритми]]) где ова [[насумичност]] није одржива.
Ако су подаци познати пре времена, висина се може одржати малом, у просечном смислу, додавањем вредности у насумичном поретку, резултујући у [[произвољно бинарно стабло претраге]]. Како било,има много ситуација(као што су [[мрежни алгоритми]]) где ова [[насумичност]] није одржива.
Ред 30: Ред 27:
Одржавајучи висину на минималној вредности <math>\lfloor \log_2(n) \rfloor</math> није увек могуће; може бити доказано да сваки алгоритам уметања који то ради би имао прекомерно рачунање. Тиме,већина само-балансирајућих БСП алгоритама одржава висину у оквиру константног фактора доње границе.
Одржавајучи висину на минималној вредности <math>\lfloor \log_2(n) \rfloor</math> није увек могуће; може бити доказано да сваки алгоритам уметања који то ради би имао прекомерно рачунање. Тиме,већина само-балансирајућих БСП алгоритама одржава висину у оквиру константног фактора доње границе.


У асимптотском смислу([[Велико О]]), само-балансирајуће БСП структура садржавајући n података дозвољава проналажења,уметања, и уклањања података O(log ''n''), најгори случај, и [[обилазак стабла]] свих чланова O(n) времена.За неке имплементације ово је граница пре-операционог времена, док за неке су [[амортизација]] граница преко низа операција. Ова времена су асимптотски оптимална међу свим структурама података које манипулишу кључем кроз поређења.<br />
У асимптотском смислу ([[Велико О]]), само-балансирајуће БСП структура садржавајући n података дозвољава проналажења,уметања, и уклањања података O(log ''n''), најгори случај, и [[обилазак стабла]] свих чланова O(n) времена.За неке имплементације ово је граница пре-операционог времена, док за неке су [[амортизација]] граница преко низа операција. Ова времена су асимптотски оптимална међу свим структурама података које манипулишу кључем кроз поређења.


== Имплементације ==
== Имплементације ==
Ред 40: Ред 37:
* [[Жртвени-јарац стабло]]
* [[Жртвени-јарац стабло]]
* [[Угао стабло]]
* [[Угао стабло]]
* [[Треп]]<br />
* [[Треп]]


== Апликације ==
== Апликације ==
Само-балансирајућа бинарна стабла претраге могу бити коришћена на природан начин да конструјиши и одржавају листе, као што је [[редни приоритет]]. Такође могу бити коришћена за [[асоцијативни низ]], кључним парововима је да једноставно буду уметнути са наручењем засновано само на кључу. У том својству, само-балансирајуће БСП има [[associative array#Efficient representations|доста врлина и мана]] над главним конкурентом, [[хеш табела]]. Једна предност само-балансирајућег БСП је та да дозвољава брзо (свакако, симптотски оптимално) енумерациу података ''у кључном поретку'', што хеш табеле не пружају. Једна мана је та да њихови алгоритми претраге бива доста компликован кад постоји висе података са истим кључем. Само-балансирајуће БСП има боље горе-случајеве преформансе претраге него хеш табела (O(log n) у односу на O(n)), али има гори просечан-случај преформансе (O(log n) у односу на O(1)).
Само-балансирајућа бинарна стабла претраге могу бити коришћена на природан начин да конструјиши и одржавају листе, као што је [[редни приоритет]]. Такође могу бити коришћена за [[асоцијативни низ]], кључним парововима је да једноставно буду уметнути са наручењем засновано само на кључу. У том својству, само-балансирајуће БСП има доста врлина и мана над главним конкурентом, [[хеш табела]]. Једна предност само-балансирајућег БСП је та да дозвољава брзо (свакако, симптотски оптимално) енумерациу података ''у кључном поретку'', што хеш табеле не пружају. Једна мана је та да њихови алгоритми претраге бива доста компликован кад постоји висе података са истим кључем. Само-балансирајуће БСП има боље горе-случајеве преформансе претраге него хеш табела (O(log n) у односу на O(n)), али има гори просечан-случај преформансе (O(log n) у односу на O(1)).


Само-балансирајуће БСП може бити корипћено да имплементира било који алгоритам који захтева requires променљиве листе, да би постигли оптимални најгори-случај асимптотске преформансе. На пример, ако [[Сортирање уз помоћ бинарног стабла]] је имплементирано са само-балансирајућим БСП-ом, имамо врло лако описив ипак [[асимптотски оптималан]] O(''n'' log ''n'') сортирајући алгоритам. Слично, многи алгоритми у [[рачунарској геометрији]] искоришћавају варијације над само-балансирајућим БСН-ом да реше проблеме као што су [[раскрснице дужи]] проблем и [[локације тачака]] ефикасно. (За просечан-случај преформанси, како год, само-балансирајуће БСП може да буде мање ефикасно од осталих солуција. Сортирање бинарног стабла, у пракси, вероватно ће бити спорије [[сортирање спајањем]], [[квиксорт]], or [[хипсорт]],због стабло-балаансирајућег рачунања а такође и ѕбог [[Кеш меморија|кеш]] приступа.
Само-балансирајуће БСП може бити корипћено да имплементира било који алгоритам који захтева requires променљиве листе, да би постигли оптимални најгори-случај асимптотске преформансе. На пример, ако [[Сортирање уз помоћ бинарног стабла]] је имплементирано са само-балансирајућим БСП-ом, имамо врло лако описив ипак [[асимптотски оптималан]] O(''n'' log ''n'') сортирајући алгоритам. Слично, многи алгоритми у [[рачунарској геометрији]] искоришћавају варијације над само-балансирајућим БСН-ом да реше проблеме као што су [[раскрснице дужи]] проблем и [[локације тачака]] ефикасно. (За просечан-случај преформанси, како год, само-балансирајуће БСП може да буде мање ефикасно од осталих солуција. Сортирање бинарног стабла, у пракси, вероватно ће бити спорије [[сортирање спајањем]], [[квиксорт]], or [[хипсорт]],због стабло-балаансирајућег рачунања а такође и ѕбог [[Кеш меморија|кеш]] приступа.
Ред 51: Ред 48:
== Такође погледати ==
== Такође погледати ==
* [[Дан–Стаут–Њорен алгоритам]]
* [[Дан–Стаут–Њорен алгоритам]]
* [[Fuziono stablo]]
* [[Фузионо стабло]]
* [[Прескакање листа]]
* [[Прескакање листа]]
* [[Уређивање]]
* [[Уређивање]]


== Референце ==
== Референце ==
{{reflist}}
{{рефлист}}


== Спољшњи линкови ==
== Спољшњи линкови ==

Верзија на датум 8. јун 2013. у 23:22

Пример неизбалансираног стабла
Исто стабло после балансирања по висини

У рачунарским наукама, само-балансирајуће бинарно стабло претраге је свако чвор-засновано бинарно стабло претраге које аутоматски одржава своју висину малом због нових уметања и брисања. [1]

Ова структура ефикасно омогућава имплементацију променљиво распоређених листа, и може се користити за другу апстрактну структуру података као што је асоцијативни низ, редни приоритети и сет.

Преглед

Ротирање стабла су врло честе унутрашње операције над само-баланисрајућим стаблом бинарне претраге да би задржало савршен или скоро савршен баланс.

Већина операциај над бинарним стаблом претраге(БСП) је временски директно пропорцијонална висини стабла, тако да је поѕењно висину одржавати што мањом. Бинарно стабло са висином h може да садржи највише 20+21+···+2h = 2h+1−1 чворова. Следи да за дрво са n чворова и h висина:

Што подразумева:

.

Другим речима, минимална висина дрвета са n чворова је log2(n), спратне и ћелијске функције; које су, :.[1]

Иначе, најједноставнији алгоритам БСП уметањем података може да носи стабло висине n у радије општим ситуацијама. На пример, када су подаци уметани у сротирани примарни кључ, стабло се дегенерише у повезану листу са n чворова. Разлика у преформансама између две ситуације може бити огромна: за n=1,000,000, на пример, минимална висина је .

Ако су подаци познати пре времена, висина се може одржати малом, у просечном смислу, додавањем вредности у насумичном поретку, резултујући у произвољно бинарно стабло претраге. Како било,има много ситуација(као што су мрежни алгоритми) где ова насумичност није одржива.

Само-балансирајуће бинарно стабло решава овај проблем изводећи трансформације над стаблом(као што су ротација стабла на књичним местима) да би задржала пропорцијоналну висину log2(n).

Одржавајучи висину на минималној вредности није увек могуће; може бити доказано да сваки алгоритам уметања који то ради би имао прекомерно рачунање. Тиме,већина само-балансирајућих БСП алгоритама одржава висину у оквиру константног фактора доње границе.

У асимптотском смислу (Велико О), само-балансирајуће БСП структура садржавајући n података дозвољава проналажења,уметања, и уклањања података O(log n), најгори случај, и обилазак стабла свих чланова O(n) времена.За неке имплементације ово је граница пре-операционог времена, док за неке су амортизација граница преко низа операција. Ова времена су асимптотски оптимална међу свим структурама података које манипулишу кључем кроз поређења.

Имплементације

Популарна структура података која имплементира овај тип стабла укључује:

Апликације

Само-балансирајућа бинарна стабла претраге могу бити коришћена на природан начин да конструјиши и одржавају листе, као што је редни приоритет. Такође могу бити коришћена за асоцијативни низ, кључним парововима је да једноставно буду уметнути са наручењем засновано само на кључу. У том својству, само-балансирајуће БСП има доста врлина и мана над главним конкурентом, хеш табела. Једна предност само-балансирајућег БСП је та да дозвољава брзо (свакако, симптотски оптимално) енумерациу података у кључном поретку, што хеш табеле не пружају. Једна мана је та да њихови алгоритми претраге бива доста компликован кад постоји висе података са истим кључем. Само-балансирајуће БСП има боље горе-случајеве преформансе претраге него хеш табела (O(log n) у односу на O(n)), али има гори просечан-случај преформансе (O(log n) у односу на O(1)).

Само-балансирајуће БСП може бити корипћено да имплементира било који алгоритам који захтева requires променљиве листе, да би постигли оптимални најгори-случај асимптотске преформансе. На пример, ако Сортирање уз помоћ бинарног стабла је имплементирано са само-балансирајућим БСП-ом, имамо врло лако описив ипак асимптотски оптималан O(n log n) сортирајући алгоритам. Слично, многи алгоритми у рачунарској геометрији искоришћавају варијације над само-балансирајућим БСН-ом да реше проблеме као што су раскрснице дужи проблем и локације тачака ефикасно. (За просечан-случај преформанси, како год, само-балансирајуће БСП може да буде мање ефикасно од осталих солуција. Сортирање бинарног стабла, у пракси, вероватно ће бити спорије сортирање спајањем, квиксорт, or хипсорт,због стабло-балаансирајућег рачунања а такође и ѕбог кеш приступа.

Само-балансирајућа БСП су флексибилне структуре података, у томе им је и лаксе да се прошире на ефикасније снимање података или извршавање нових операција. На пример, један може да сними одређен број чворова у сваком подстаблу имајући одређене особине, дозвољавајући једном да броји чворове у одређеном кључном растојању са тим особинама у O(log n) времену. Ови наставци могу бити коришћени, на пример, да оптимизују упите базе података или друге алгоритме за обраду листа.

Такође погледати

Референце

  1. ^ а б Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 6.2.3: Balanced Trees, pp.458–481.

Спољшњи линкови