Т-стабло

Пример Т-стабла

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

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

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

'Т' у Т-стаблу означава облик чвора структуре података у изворном раду који је први описао овакву врсту индекса.

Стуктура чворова

Чвор Т-стабла

Чвор Т-стабла обично се састоји од показивача на родитељски чвор, левог и десног сина (чвор дете), низ уређених (сортираних) показивача података и нешто додатних, контролних података. Дакле, сами подаци записани су на неком другом месту у меморији, а Т-стабло, односно поље података садржи само показиваче на њих. Постоје три врсте чворова: Чворови са два подстабла зову се унутрашњи чворови, чворови са само једним подстаблом зову се полу-листови, а они без подстабала зову се листови (енгл. леаф ноде).

Зависно од врсте чвора, један може садржати највише онолико елемената колико их стане у поље података. Поље података је увек сортирано од елемента са најмањом вредношћу (минималног елемента), до елемента са максималном вредношћу (максималног елемента). За сваки унутрашњи чвор постоје два припадајућа чвора листа (или полу-листа), од којих један садржи вредност која претходи минималном елементу, а други вредност која следи максималном елементу (односно, ради се о показивачима на вредности/податке). Вредност која претходи минималној вредности унутрашњег чвора назива се највећом доњом границом, а она која следи максималној назива се најмањом горњом границом тог чвора. Ако нека вредност упада између те две границе, кажемо да је наведени чвор ограничава.

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

Алгоритми

Претраживање

Претраживање Т-стабла обавља се слично као и код Б-стабла, осим што нема потребе упоређивати сваки податак у чвору са траженом вредношћу, већ само минималну и максималну вредност чвора. То се чини све док се не дође до чвора који ограничава тражену вредност:

• Почети претрагу од корена
• Уколико је тражена вредност мања од минимума тренутног чвора, наставити претрагу у левом сину. Уколико је већа од максимума, у десном сину.
• У супротном, претражити поље података тренутног, ограничавајућег чвора (оног чија је минимална вредност већа, а максимална мања од вредности која се треба уметнути).

Претрага је успела ако и само ако је вредност нађена у ограничавајућем чвору. Ако вредност није нађена у ограничавајућем чвору, или такав не постоји, онда је претрага неуспешна.

Уметање

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

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

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

Брисање

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

• Наћи чвор који ограничава тражену вредност (ако га нема, јавити грешку и завршити).
• Ако је наведени чвор унутрашњи чвор, а број елемената једнак минималном броју, обрисати вредност и затим преместити највећу доњу границу (максималну вредност из левог полу/листа) у тренутни чвор. У супротном (уколико број елемената у чвору није једнак минималном броју или се ради о полу/листу), обрисати вредност и завршити.
• Уколико је чвор полу-лист и може бити спојен са листом, преписати вредности из полу-листа у лист и обрисати сувишан чвор. А уколико је чвор лист, треба стати ако није празан, а ако јесте обрисати га.
• Проверити баланс стабла: Кренути од листа према корену. Уколико се подстабло било ког од чворова на том путу разликује за више од једног нивоа, избалансирати стабло. За разлику од поступка код алгоритма уметања, након балансирања је потребно проверити и први родитељски чвор. Разлог је то што ротација једног чвора може из баланса избацити чвор изнад њега (родитељски чвор), те се балансирање наставља све док се не дође до чвора који јесте у балансу.

Балансирање стабла

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

Ефикасност

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