Arborele binomial

Arborii binomiali de grad 0, 1, 2 și respectiv 3. Primul arbore constă dintr-un singur nod, al doilea este unirea arborilor binomiali de grad 0, al treilea constă în unirea a doi arbori de gradul 2. Al treilea arbore este definit recursiv într-un mod similar.

Un arbore binomial este un arbore ordonat definit recursiv după cum urmează:

arborele binomial $B_{0}$ ${\ displaystyle B_ {0}}$ ${\ displaystyle B_ {0}}$ constă dintr-un singur nod,
arborele binomial $B_{k}$ ${\ displaystyle B_ {k}}$ $B_ {k}$ este format din doi arbori binomiali $B_{k-1}$ ${\ displaystyle B_ {k-1}}$ ${\ displaystyle B_ {k-1}}$ legate între ele astfel încât rădăcina unuia dintre cei doi copaci binomiali să fie un copil stâng al rădăcinii celuilalt.

Un arbore binomial generic $B_{k}$ ${\ displaystyle B_ {k}}$ $B_ {k}$ se caracterizează prin unele proprietăți:

nodurile sale sunt exact $2^{k}$ ${\ displaystyle 2 ^ {k}}$ $2 ^ {k}$ ,
înălțimea sa este exact $k$ ${\ displaystyle k}$ $k$ ,
nodurile sale la adâncime $the$ ${\ displaystyle i}$ $the$ sunt exact ${\binom {k}{i}}$ ${\ displaystyle {\ binom {k} {i}}}$ ${\ displaystyle {\ binom {k} {i}}}$ , cu $i=0,1,...,k$ ${\ displaystyle i = 0,1, ..., k}$ ${\ displaystyle i = 0,1, ..., k}$
rădăcina sa are grad $k$ ${\ displaystyle k}$ $k$ și, în plus, acest grad este mai mare decât gradul oricărui alt nod.

Grad maxim

Gradul maxim al fiecărui nod al unui arbore binomial cu $n$ ${\ displaystyle n}$ $n$ noduri este $lg(n)$ ${\ displaystyle lg (n)}$ ${\ displaystyle lg (n)}$ .

Bibliografie

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introducere în algoritmi . Jackson Books, 2003, ISBN 88-256-1421-7 .

Portal IT

Portalul de matematică