АВЛ-стабло
АВЛ-стабло је структура података која се користи у рачунарству. Ради се о балансираном бинарном стаблу претраге, које гарантује да операције уметања, тражења и брисања елемената из стабла и у најгорем случају могу да се спроведу у броју корака који одговара логаритму броја елемената у стаблу, O(log n). Мотив за коришћење бинарних стабала управо јесте брза претрага стабла, али код уобичајеног, небалансираног бинарног стабла може да дође до дебаланса (нека грана стабла се значајније издужи), и онда претрага која иде кроз ту грану нема логаритамску, већ линеарну сложеност.
АВЛ-стабло је добило име по изумитељима, Аделсон-Велском и Лендису, који су описали ову структуру 1962. у раду Алгоритам за организовање података.
Дефиниција уреди
АВЛ-стабло је бинарно стабло претраге код кога апсолутна разлика висина левог и десног подстабла сваког елемента није већа од један.[1]
Балансирање уреди
Балансираност АВЛ-стабла се одржава тако што се након сваког уметања или брисања проверава да ли је дошло до губитка балансираности на неком делу стабла. Уколико је дошло до дебаланса, идентификује се критични чвор, то јест корен најмањег подстабла које не задовољава дефиницију АВЛ-стабла. Ово подстабло се затим балансира вршењем одговарајућих ротација елемената, тако да се поврати балансираност подстабла.
