Arbres Red-Black P13747

[nodes=draw, circle, -, level distance=0.8cm, sibling distance=9.8mm] [dotted,color=blue] (-6.58, -2.28) – (-6.42, -1.8);

[draw=white,fill=white] child[white]node[draw=red,fill=red]child[green]node[draw=black,fill=black] child[green]node[draw=black,fill=black]child[missing] child[sibling distance=4.9mm]node[draw=red,fill=red] child[white,missing] child[white]node[draw=red,fill=red]child[green]node[draw=black,fill=black] child[green]node[draw=black,fill=black]child[sibling distance=4.9mm]node[draw=red,fill=red] child[missing] child[white,missing] child[white]node[draw=red,fill=red]child[green]node[draw=black,fill=black] child[green]node[draw=black,fill=black]child[sibling distance=4.9mm]node[draw=red,fill=red] child[sibling distance=4.9mm]node[draw=red,fill=red] child[white,missing] child[white]node[draw=red,fill=red]child[green]node[draw=black,fill=black]child[missing] child[sibling distance=4.9mm]node[draw=red,fill=red] child[green]node[draw=black,fill=black] child[white,missing] child[white]node[draw=red,fill=red]child[green]node[draw=black,fill=black]child[missing] child[sibling distance=4.9mm]node[draw=red,fill=red] child[green]node[draw=black,fill=black]child[missing] child[sibling distance=4.9mm]node[draw=red,fill=red] child[white,missing] child[white]node[draw=red,fill=red]child[green]node[draw=black,fill=black]child[missing] child[sibling distance=4.9mm]node[draw=red,fill=red] child[green]node[draw=black,fill=black]child[sibling distance=4.9mm]node[draw=red,fill=red] child[missing] child[white,missing] child[white]node[draw=red,fill=red]child[green]node[draw=black,fill=black]child[missing] child[sibling distance=4.9mm]node[draw=red,fill=red] child[green]node[draw=black,fill=black]child[sibling distance=4.9mm]node[draw=red,fill=red] child[sibling distance=4.9mm]node[draw=red,fill=red] child[white,missing] child[white]node[draw=red,fill=red]child[green]node[draw=black,fill=black]child[sibling distance=4.9mm]node[draw=red,fill=red] child[missing] child[green]node[draw=black,fill=black] ;

[nodes=draw, circle, -, level distance=0.8cm, sibling distance=9.8mm] [draw=white,fill=white] child[white]node[draw=red,fill=red]child[green]node[draw=black,fill=black]child[sibling distance=4.9mm]node[draw=red,fill=red] child[missing] child[green]node[draw=black,fill=black]child[missing] child[sibling distance=4.9mm]node[draw=red,fill=red] child[white,missing] child[white]node[draw=red,fill=red]child[green]node[draw=black,fill=black]child[sibling distance=4.9mm]node[draw=red,fill=red] child[missing] child[green]node[draw=black,fill=black]child[sibling distance=4.9mm]node[draw=red,fill=red] child[missing] child[white,missing] child[white]node[draw=red,fill=red]child[green]node[draw=black,fill=black]child[sibling distance=4.9mm]node[draw=red,fill=red] child[missing] child[green]node[draw=black,fill=black]child[sibling distance=4.9mm]node[draw=red,fill=red] child[sibling distance=4.9mm]node[draw=red,fill=red] child[white,missing] child[white]node[draw=red,fill=red]child[green]node[draw=black,fill=black]child[sibling distance=4.9mm]node[draw=red,fill=red] child[sibling distance=4.9mm]node[draw=red,fill=red] child[green]node[draw=black,fill=black] child[white,missing] child[white]node[draw=red,fill=red]child[green]node[draw=black,fill=black]child[sibling distance=4.9mm]node[draw=red,fill=red] child[sibling distance=4.9mm]node[draw=red,fill=red] child[green]node[draw=black,fill=black]child[missing] child[sibling distance=4.9mm]node[draw=red,fill=red] child[white,missing] child[white]node[draw=red,fill=red]child[green]node[draw=black,fill=black]child[sibling distance=4.9mm]node[draw=red,fill=red] child[sibling distance=4.9mm]node[draw=red,fill=red] child[green]node[draw=black,fill=black]child[sibling distance=4.9mm]node[draw=red,fill=red] child[missing] child[white,missing] child[white]node[draw=red,fill=red]child[green]node[draw=black,fill=black]child[sibling distance=4.9mm]node[draw=red,fill=red] child[sibling distance=4.9mm]node[draw=red,fill=red] child[green]node[draw=black,fill=black]child[sibling distance=4.9mm]node[draw=red,fill=red] child[sibling distance=4.9mm]node[draw=red,fill=red] child[white,missing] child[white]node[draw=red,fill=red]child[green]node[draw=black,fill=black]child[sibling distance=4.9mm]node[draw=black,fill=black] child[sibling distance=4.9mm]node[draw=black,fill=black] child[green]node[draw=black,fill=black]child[sibling distance=4.9mm]node[draw=black,fill=black] child[sibling distance=4.9mm]node[draw=black,fill=black] ;

Hi ha diverses maneres de balancejar un arbre binari amb n elements per aconseguir que tingui alçada Θ(logn). Una de popular són els arbres Red-Black, on cada node està pintat de vermell o de negre. Les propietats que han de complir els arbres Red-Black són:

• Cada camí des de l’arrel fins a una fulla buida té el mateix nombre de nodes negres.
• Cap camí des de l’arrel fins a una fulla buida té dos o més nodes vermells seguits.

Per exemple, aquests són els 16 arbres Red-Black d’alçada 3 amb l’arrell vermella:

Per convenció, les fulles buides no es mostren. Per exemple, el fill esquerre del node negre de la dreta del primer arbre és una fulla buida, la qual és l’única que s’ha dibuixat.

Els arbres Red-Black es poden ordenar de diverses maneres. Aquesta n’és una: L’arbre buit és el primer arbre. Donats dos arbres no buits, si tenen les arrels de colors diferents, va abans el que té l’arrel vermella. En cas d’igualtat, es desempata amb el subarbre esquerre. En cas d’un altre empat, es desempata amb el subarbre dret. Els 16 arbres anteriors estan ordenats.

Donats dos nombres h i i, podeu trobar l’i-èsim arbre Red-Black d’alçada h?

Entrada

L’entrada conté diversos casos, cadascun amb l’alçada h i l’índex i. Podeu suposar 0 ≤ h ≤ 6, i que l’índex i es troba entre 1 i el nombre d’arbres Red-Black d’alçada h. (Per a h=6, n’hi ha 3822531721037.)

Sortida

Per a cada cas, escriviu una línia amb el recorregut en preordre de l’arbre resultat: feu servir punts per marcar els arbres buits, ‘R’ per als nodes vermells, i ‘B’ per als nodes negres.

Puntuació

• Cas A:  ‍ Casos amb h ≤ 4, com l’exemple d’entrada 1.  ‍50% Punts ‍

• Cas B:  ‍ Casos de tot tipus.  ‍50% Punts ‍