Arbre binari

De Viquipèdia
Dreceres ràpides: navegació, cerca

En ciències de la computació, un arbre binari és una estructura de dades en la qual cada node sempre té un fill esquerre i un fill dret. No poden tenir més de dos fills (d'ací el nom "binari"). Si algun fill té com referència a null, és a dir que no emmagatzema cap dada, llavors aquest és dit un node extern. En el cas contrari el fill és dit un node intern.

Usos comuns dels arbres binaris són els arbres binaris de cerca, els monticles binaris i Codificació de Huffman.

Definició de teoria de grafs[modifica | modifica el codi]

Un arbre binari senzill de grandària 9 i altura 3, amb un node arrel el valor de la qual és 2

En la teoria de grafs, s'usa la següent definició: «Un arbre binari és un graf connex, acíclic i no dirigit tal que el grau de cada vèrtex no és major a 3». D'aquesta forma només existeix un camí entre un parell de nodes.

Un arbre binari amb arrelat és com un graf que té un dels seus vèrtex, dit arrel, de grau no major a 2. Amb l'arrel escollida, cada vèrtex tindrà un únic pare, i mai més de dos fills. Si refusem el requeriment de la connectivitat, permetent múltiples components connectats en el graf, anomenarem a aquesta última estructura un bosc.

Tipus d'arbres binaris[modifica | modifica el codi]

  • Un arbre binari és una planta amb arrel en el qual cada node té com a màxim dos fills.
  • Un arbre binari ple és un arbre en el qual cada node té zero o dos fills.
  • Un arbre binari perfecte és un arbre binari ple en el qual totes les fulles (vèrtex amb zero fills) estan a la mateixa profunditat (distància des de l'arrel, també dita altura)
  • De vegades un arbre binari perfecte és denominat arbre binari complet. Uns altres defineixen un arbre binari complet com un arbre binari ple en el qual totes les fulles estan a profunditat n o n-1, per a alguna n.


Un arbre binari és un arbre en el qual cap node pot tenir més de dos subarbres. En un arbre binari cada node pot tenir zero, un o dos fills (subarbres). Es coneix el node de l'esquerra com fill esquerre i el node de la dreta com fill dret.

Implementació en C[modifica | modifica el codi]

Un arbre binari pot declarar-se de diverses maneres. Algunes d'elles són:

Estructura amb maneig de memòria dinàmica, sent PUNTA el punter que apunta a l'arbre de tipus tArbre:


typedef struct tArbol
{
 int clave;
 struct tArbol *hIzquierdo, *hDerecho;
} tArbol;
typedef struct tArbol *puntA;

Estructura amb un vector indexat:

typedef struct tArbol
{
 int clave;
 int hIzquierdo, hDerecho;
};
tArbol árbol[NUMERO_DE_NODOS];

En el cas d'un arbre binari quasi-complet (o un arbre complet), pot utilitzar-se un senzill arranjament d'enters amb tantes posicions com nodes haja de tenir l'arbre. La informació de la ubicació del node en l'arbre és implícita a cada posició de l'arranjament. Així, si un node està en la posició *i, els seus fills es troben en les posicions 2i+1 i 2i+2, mentre que el seu pare (si té), es troba en la posició truncament ((i-1)/2) (suposant que l'arrel està en la posició zero). Aquest mètode es beneficia d'un emmagatzematge més compacte i una millor localitat de referència, particularment durant un recorregut en preordre. L'estructura per a aquest cas seria per tant:

int árbol[NUMERO_DE_NODOS];

Recorreguts sobre arbres binaris[modifica | modifica el codi]

Recorreguts en profunditat[modifica | modifica el codi]

El mètode d'aquest recorregut és tractar de trobar de la capçalera a l'arrel en node d'unitat binària Ara passem a veure la implementació dels diferents recorreguts:

Recorregut en preordre[modifica | modifica el codi]

En aquest tipus de recorregut es realitza certa acció (potser simplement imprimir per pantalla el valor de la clau d'eixe node) sobre el node actual i posteriorment es tracta el subarbre esquerre i quan s'haja conclòs, el subarbre dret. En l'arbre de la figura el recorregut en preordre seria: 2, 7, 2, 6, 5, 11, 5, 9 y 4.

void preorden(tArbol *a)
{
 if (a != NULL) {
 tratar(a); //Realitza una operació en node
 preorden(a->hIzquierdo);
 preorden(a->hDerecho);
 }
}

Implementació en pseudocodi de forma iterativa:

push(s,NULL); //inserim en una pila (stack) el valor NULL, per a assegurar-nos que estiga buida 
push(s,raíz); //inserim el node arrel
MIENTRAS (s <> NULL) HACER
 p = pop(s); //traiem un element de la pila
 tratar(p); //realitzem operacions sobre el node p
 SI (I(p) <> NULL) //preguntem si p té arbre dret
 ENTONCES push(s,D(p));
 FIN-SI
 SI (D(p) <> NULL) //preguntem si p té arbre esquerre 
 ENTONCES push(s,I(p));
 FIN-SI
FIN-MIENTRAS

Recorregut en postordre[modifica | modifica el codi]

En aquest cas es tracta primer el subarbre esquerre, després el dret i finalment el node actual. En l'arbre de la figura el recorregut en postordre seria: 2, 5, 11, 6, 7, 4, 9, 5 i 2.

void postorden(tArbol *a)
{
 if (a != NULL) {
 postorden(a->hIzquiedo);
 postorden(a->hDerecho);
 tratar(a); //Realitza una operació en node
 }
}

Recorrido en inorden[modifica | modifica el codi]

En este caso se trata primero el subarbre esquerre, después el nodo actual y por último el subárbol derecho. En un ABB este recorrido daría los valores de clave ordenados de menor a mayor. En el árbol de la figura el recorrido en inorden sería: 2, 7, 5, 6, 11, 2, 5, 4 y 9.

Pseudocodi:

funcion inorden(nodo)
inicio
 si(existe(nodo))
 inicio
 inorden(hijo_izquierdo(nodo));
 tratar(nodo); //Realitza una operació en node
 inorden(hijo_derecho(nodo));
 fin;
fin;

Implementación en C:

void inorden(tArbol *a)
{
 if (a != NULL) {
 inorden(a->hIzquierdo);
 tratar(a); //Realitza una operació en node
 inorden(a->hDerecho);
 }
}

Recorreguts en amplitud (o per nivells)[modifica | modifica el codi]

En aquest cas el recorregut es realitza en ordre pels diferents nivells de l'arbre. Així, es començaria tractant el nivell 1, que només conté el node arrel, seguidament el nivell 2, el 3 i així successivament. En l'arbre de la figura el recorregut en amplitud seria: 2, 7, 5, 2, 6, 9, 5, 11 i 4.

Al contrari que en els mètodes de recorregut en profunditat, el recorregut per nivells no és de naturalesa recursiva. Per això, s'ha d'utilitzar una cua per a recordar els subarbres esquerres i dret de cada node.

Pseudocódigo:

 encolar(raiz);
 mientras(cola_no_vacia())
 inicio
 nodo=desencolar(); //Trau un node de la cua
 visitar(nodo); //Realitza una operació en node
 encolar_nodos_hijos(nodo); //Fica en la cua els fills del node actual
 fin;

Implementació en C:

void amplitud(tArbol *a)
{
 tCola cola;
 tArbol *aux;
 
 if (a != NULL) {
 crearCola(cola);
 encolar(cola, a);
 while (!colavacia(cola)) {
 desencolar(cola, aux);
 visitar(aux); //Realiza una operación en nodo
 if (aux->hIzquierdo != NULL) encolar(cola, aux->hIzquierdo );
 if (aux->hDerecho!= NULL) encolar(cola, aux->hDerecho);
 }
 }
}

NOTA: Per a fer un recorregut en amplària, la idea és anar guardant en una cua els fills del node que s'estan visitant i el següent a visitar és el pròxim node de la cua.

Mètodes per a emmagatzemar arbres binaris[modifica | modifica el codi]

Els arbres binaris poden ser construïts a partir de llenguatges de programació de diverses formes. En un llenguatge amb registres i referències, els arbres binaris són construïts típicament amb una estructura de nodes i punters en la qual s'emmagatzemen dades, cadascun d'aquests nodes té una referència o punter a un node esquerre i a un node dret denominats fills. A vegades, també conté un punter a un únic node. Si un node té menys de dos fills, alguns dels punters dels fills poden ser definits com a nuls per a indicar que no disposa d'aquest node. En la figura adjunta es pot observar l'estructura d'aquesta implementació.

Arbres binaris

Els arbres binaris també poden ser emmagatzemats com una estructura de dades implícita en vectors, i si l'arbre és un arbre binari complet, aquest mètode no desaprofita l'espai en memòria. Prendrem com notació la següent: si un node té un índex i, els seus fills es troben en índexs 2*i + 1 i 2*i + 2, mentre que els seus pares (si els té) es troba en l'índex \left \lfloor \frac{i-1}{2} \right \rfloor(partint que l'arrel tinga índex zero). Aquest mètode té com avantatges el tenir emmagatzemats les dades de forma més compacta i per tenir una forma més ràpida i eficient de localitzar les dades en particular durant un preordre transversal. No obstant això, balafia molt espai en memòria.

Llista de nodes

Codificació d'arbres n-aris com arbres binaris[modifica | modifica el codi]

Hi ha un mapeig d'un a un entre els arbres generals i arbres binaris, el qual en particular és usat en *Lisp para representar arbres generals com arbres binaris. Cada node N ordenat en l'arbre correspon a un node N 'en l'arbre binari; el fill de l'esquerra de’ N és el node corresponent al primer fill de N, i el fill dret de N' és el node corresponent al següent germà de N, és a dir, el pròxim node en ordre entre els fills dels pares de N.

Aquesta representació com arbre binari d'un arbre general, es coneix de vegades com un arbre binari primer fill germà, o un arbre doblement encadenat.

Una manera de pensar sobre açò és que els fills de cada node estiguen en una llista enllaçada, encadenats juntament amb el camp dret, i el node només té un punter al començament o el cap d'aquesta llista, a través del seu camp esquerre.

Per exemple, en l'arbre de l'esquerra, l'A té 6 fills (B, C, D, E, F, G). Pot ser convertit en l'arbre binari de la dreta.

Un exemple de transformar l'arbre n-ari a un arbre binari Com passar d'arbres n-aris a arbres FLOFO.


L'arbre binari pot ser pensat com l'arbre original inclinat cap als costats, amb les vores negres esquerres representant el primer fill i els blaus representat els següents germans.

Les fulles de l'arbre de l'esquerra serien escrites en Lisp com:

(((M N) H I) C D ((O) (P)) F (L)) 

Que s'executarà en la memòria com l'arbre binari de la dreta, sense cap tipus de lletres en aquells nodes que tenen un fill esquerre.

Vegeu també[modifica | modifica el codi]

Enllaços externs[modifica | modifica el codi]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Arbre binari Modifica l'enllaç a Wikidata