Uravnoteženo drevo

Iz MaFiRaWiki

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

Kaj pomeni to opozorilo?

Uravnoteženo drevo je tako dvojiško drevo, v katerem se globini levega in desnega poddrevesa vsakega vozlišča razlikujeta kvečjemu za 1.

k-uravnoteženo drevo je tako dvojiško drevo, v katerem se globini levega in desnega poddrevesa vsakega vozlišča razlikujeta kvečjemu za k. Seveda je 1-uravnoteženo drevo kar uravnoteženo drevo.

Uravnoteženost korena definiramo kot razliko med globino levega in desnega poddrevesa korena.

Uravnoteženost drevesa definiramo kot maksimalno uravnoteženost njegovih vozlišč.

Dinamično urejeno uravnoteženo drevo (z drugimi besedami: podatkovna struktura, ki vzdržuje urejeno uravnoteženo drevo ob vstavljanjih in brisanjih elementov) je znana pod imenom AVL drevo. Dvojiško drevo je urejeno, če za vsako vozlišče velja, da je vrednost levega sina manjša, vrednost desnega sina pa večja od njegove vrednosti.

Zgled

Spodnje drevo je uravnoteženo:

Slednje drevo pa ni uravnoteženo, saj je globina levega poddrevesa enaka 3, globina desnega pa 1.

Glej tudi

Osebna orodja