Uravnoteženo dvojiško drevo

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Dvojiško drevo je k-uravnoteženo natanko tedaj, kadar se v vsakem vozlišču globini njegovih poddreves razlikujeta kvečjemu za k in ko sta levo in desno poddrevo k-uravnoteženi. Če je k = 1, rečemo, da je 1-uravnoteženo drevo kar uravnoteženo.

Če so vsi listi drevesa na nivoju d ali d-1, potem je drevo uravnoteženo, obratno pa ne velja.

Drevo je neuravnoteženo, če sta globini levega in desnega poddrevesa bistveno različni. Iskalno drevo postane neuravnoteženo predvsem takrat, ko ga polnimo s podatki, ki so skoraj urejeni po velikosti.

Glej tudi

Osebna orodja