Бинарно стабло

Из пројекта Википедија

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

[уреди] Основни појмови

Скица бинарног стабла

Чвор стабла је једна меморијска ћелија стабла. Она може имати нула, једнан или два подчвора. Иста може да носи две различите вредности:
- Кључ. Најчешће нумеричка вредност, по којој се неки елемент распорећује у бинарном стаблу
- Вредност. Податак који треба запамтити. Може се десити да су вредност и кључ једно те исто, тј. да се сортирање бинарног стабла врши по самој вредности.
Корен стабла је чвор стабла који није подчвор ниједног другог чвора у стаблу.
Лист је чвор стабла који нема ни један подчвор
Родитељ неког чвора је чвор који показује на њега
Дете неког чвора је чвор на који неки други чвор показује

У вези са сликом десно: чворови стабла су елементи приказани круговима. Уписани бројеви су вредности кључева по којима се елементи сортирају. Чвор са кључем 8 је корен стабла. Његова деца су чворови са кључевима 3 и 10. Родитељ чворова са вредношћу кључева 3 и 10 је чвор са кључем 8. Листови стабла су чворови са кључевима 1, 4, 7 и 13.

Подстабло или подграна је скуп свих чворова стабла који се налазе лево или десно од неког од чворова стабла

[уреди] Операције

Иако сортирано, бинарно стабло не гарантује брзину извођења операција. Тражење елемента у стаблу нпр. може да варира од O(log n) у најбољем (као код бинарне претраге) до O(n) у најгорем случају (као код линеарне претраге несортираног низа). Слично је и са осталим операцијама.

[уреди] Претрага

Претрага почиње од корена стабла. Следи један од алгоритама:

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

[уреди] Додавање новог елемента

Претрагом (в. горе) се установљава да елемента који треба додати у стаблу нема. Потом се на месту детета које није постојало прави нови елемент са датим кључем и подацима.

[уреди] Брисање елемента

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

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