Језик :
SWEWE Члан :Пријава |Регистрација
Претражи
Енциклопедија заједница |Енциклопедија Одговори |Пошаљи питање |Речник Знање |Додај знања
Претходна 1 Следећи Изаберите Странице

Уравнотежена бинарно стабло

Балансирани бинарно стабло (Баланцед Бинарно дрво) је такође познат као АВЛ стабла (другачији од АВЛ алгоритма), и има следеће особине: то је апсолутна разлика између висине празног стабла или под-стабло своје леве и десне није више од 1, и око две под-стабла су балансирана бинарно стабло. Методи прилагођавања обично користи да изгради уравнотежену бинарни дрво са црвеним и црним дрвећем, АВЛ, Треап, истезање дрвећа. Формула Ноде минимална избалансиране бинарни стабло како следи ф (н) = Ф (н-1) Ф (н-2) 1 Ово је слично рекурзивне секвенци, може се односити на Фибоначијев низ је корен ф (н- 1) је број чвора леве подстабло чвора десном дечјег Ф је број броја (н-2).Акција

Ми знамо да је, за просечног бинарне претраге стабла (Бинарно претраживање Трее), његова жељена висина (када је дрво избалансиран дрво) је лог2н, сложеност време њених различитих операција (О (лог2н)) али такође доводи одлука . Међутим, у неким екстремним случајевима (као што је предвиђено у секвенци се убацује), бинарни претраживање стабло деградиран у ланце или слично, онда, комплексност време његовог функционисања дегенерише у линеарним, тј, О (н). Можемо изградити бинарни претрагу дрво од насумичног да покуша да то избегли, али након спровођења неколико операција, због брисања, ми смо увек изабрати наследник чвор ће бити избрисани уместо сопствених, који би резултира смањењем броја чворова је увек у праву стабла на левој тако да делимична лавабо. То ће такође изазвати оштећење стабла равнотеже, повећање сложености време њеног пословања.

Уравнотежена бинарни претрагу дрво (Балансирани Бинарно дрво) има следеће особине: то је празна дрво или апсолутна вредност разлике између висине његове леве и десне субтреес од не више од 1, и лево и десно под-стабла су балансирана бинарно стабло. Заједнички црвено-црна стабла алгоритам, АВЛ, Треап, истезање дрвеће. У уравнотеженом бинарног стабла претраге, можемо видети да је његова висина је генерално добро одржавана у О (лог2н), у великој мери смањује сложеност време операције.

Алгоритам

Црвено-црни дрво

Црвено-црни дрво је само-балансирање бинарног претраживање дрво, користи се у компјутерске науке, структура података, типична употреба је да се постигне асоцијативни низ. То је било у 1972 Рудолф Баиер проналаском, који је назвао "симетрични бинарни Б-стабло," који се добија модеран назив у Лео Ј. Гуибас и Роберт Седгевицк написао папир у 1978. То је сложен, али његов рад има добру најгори Потребно време, и веома је ефикасан у пракси: она може да уради да се пронађе, убаците и брисање у О (лог н) времену, где је н дрво елеменат број.

АВЛ

АВЛ је само-балансирање бинарног стабла претраживање алгоритам први измислио. Највећа разлика у висини АВЛ два сина било ког чвора је као под-стабло, тако да се такође зове висина избалансирана дрво. Тражи, уметак, и брисање су О (лог н) у најгорем случају и просечне. Повећања и брисања може тражити од једног или више стабала да поново успостави равнотежа ротирајуће дрво.

Треап

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

Пружи дрво

Пружи дрво (сплаи дрво) је бинарни врста стабло, то може да се убаци у завршетак О (лог н), наћи и брисање операције. Настала је Даниел Слеатор и Роберт Тарјан. Његова предност је у томе што постоји запис сувишно информације користи да избалансира дрво. У принципу се рад базира на дрво истезања истезање.

СБТ

Величина Балансирани дрво (скраћено СБТ) је само-балансирање бинарног претраживање дрво, користи се у компјутерске науке, структура података. Она се састоји од Кина Гуандонг Зхонгсхан Меморијал Средња Школа Чен Кифенг проналаска. Чен Кифенг крајем 2006 да заврши папира "Величина Баланцед дрво", и информатику на Зимском кампу за младе Национална олимпијада 2007 објављен. Пошто СБТ правопис је лако наћи кинески хомоним, често је кинеска информатика такмичар и АЦМ / ИЦПЦ играчи назван "глупо Б-дрво", "супер" БТ и тако даље. У поређењу са само-балансирање црвено-црна стабла дрвећа, АВЛ стабла бинарног претрагу, СБТ лакше да спроведе. Према Чен Кифенг изјавио у новинама, СБТ је "далеко најбржи напредна претрага бинарни дрво." СБТ може да заврши све бинарну претрагу дрво (БСТ) у вези операције у О (лог н) времену, у поређењу са обичним бинарном стаблу претраге, СБТ само придружио компактни језгро оперативног Одржавајте. Пошто је величина СБТ да одржи равнотежу на који домен него други "бескорисно" домен, који се могу лако остварити динамичан реда статистику изаберите и ранга операцијама.


Претходна 1 Следећи Изаберите Странице
Корисник Преглед
Но цомментс иет
Ја желим да коментаришем [Посетилац (3.235.*.*) | Пријава ]

Језик :
| Проверите код :


Претражи

版权申明 | 隐私权政策 | Ауторско право @2018 Свет енциклопедијско знање