Тежински-балансирано стабло
 | Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=. |
Тежински-балансирано бинарно стабло је бинарно стабло које је балансирано на основу информација које указују на вероватноћу тражења одређеног чвора. Унутар сваког подстабла, чвор са највећом тежином се приказује као корен. Ово може резултирати ефикаснијим примењивањем претраге.
Особине[уреди | уреди извор]
Лема[уреди | уреди извор]
У тежински-балансираном стаблу за сваки произвољан чвор П важи да је |Тлп|≤3|Тдп|+1, и |Тдп|≤3|Тлп|+1, где је |Тдп| кардиналност десног подстабла чвора П, а |Тлп| кардиналност левог подстабла чвора П.
Доказ леме[уреди | уреди извор]
Врши се индукцијом по броју чворова у стаблу.
Теорема[уреди | уреди извор]
Максимална висина тежински-балансираног стабла је О(лог н), где је н број чворова у стаблу.
Доказ теореме[уреди | уреди извор]
Изводи се из леме.
Дијаграм[уреди | уреди извор]
На дијаграму 1 који приказује тежински-балансирано стабло, слова представљају вредности чворова, а бројеви тежине чворова. Вредности се користе како би се уредило стабло, по истом принципу као и бинарно стабло претраге. На тежину се може гледати као на вероватноћу или број активности везаних за одређени чвор. На дијаграму, корен је Г зато што је његова тежина највећа од свих чворова у стаблу. Лево подстабло чвора Г почиње са А зато што А има највећу тежину од чворова у том подстаблу. Исто важи и за десно подстабло чвора Г, Н је чвор са највећом тежином од свих чворова који долазе после Г.
Сложеност[уреди | уреди извор]
Просечно време претраге[уреди | уреди извор]
Као и за све алгоритме засноване на бинарном стаблу претраге, тако и тежински-балансирано стабло има просечно време претраге О(лог н). На дијаграму 2 се може видети поређење ефикасности претраге над различитим структурама података.
Просторна сложеност[уреди | уреди извор]
Количина простора која је неопходна је еквивалентна као и код АВЛ стабла и већине стабала бинарне претраге односно О(н).
Види још[уреди | уреди извор]
Референце[уреди | уреди извор]
- Јеан-Паул Тремблаy анд Грант А. Цхестон. Дата Струцтурес анд Софтwаре Девелопмент ин ан објецт-ориентед домаин, Еиффел Едитион. Прентице Халл, (2001) ISBN 978-0-13-787946-5.
- J. L. Baer. Weight-balanced trees, University of Washington,1975.