Llegim les estructures de dades lineals com una matriu, una llista enllaçada, una pila i una cua en què tots els elements estan disposats de manera seqüencial. Les diferents estructures de dades s'utilitzen per a diferents tipus de dades.

Es tenen en compte alguns factors per triar l'estructura de dades:

Quin tipus de dades s'han d'emmagatzemar?: És possible que una determinada estructura de dades sigui la millor per a algun tipus de dades.Cost de les operacions:Si volem minimitzar el cost de les operacions de les operacions més freqüents. Per exemple, tenim una llista senzilla sobre la qual hem de realitzar l'operació de cerca; llavors, podem crear una matriu en la qual s'emmagatzemen els elements en ordre ordenat per dur a terme el cerca binària . La cerca binària funciona molt ràpid per a la llista senzilla, ja que divideix l'espai de cerca a la meitat.Ús de memòria:De vegades, volem una estructura de dades que utilitzi menys memòria.

Un arbre també és una de les estructures de dades que representen dades jeràrquiques. Suposem que volem mostrar els empleats i les seves posicions en forma jeràrquica, llavors es pot representar com es mostra a continuació:

L'arbre de dalt mostra el jerarquia organitzativa d'alguna empresa. En l'estructura anterior, Joan és el CEO de l'empresa, i John té dos subordinats directes anomenats com Steve i Rohan . Steve té tres subordinats directes nomenats Llegeix, Bob, Ella on Steve és un gerent. Bob té dos subordinats directes nomenats Haurà i Emma . Emma té dos subordinats anomenats Tom i Raj . Tom té un nom directe Bill . Aquesta estructura lògica particular es coneix com a Arbre . La seva estructura és semblant a l'arbre real, per això s'anomena a Arbre . En aquesta estructura, el arrel està a la part superior i les seves branques es mouen en direcció cap avall. Per tant, podem dir que l'estructura de dades de l'arbre és una manera eficient d'emmagatzemar les dades de manera jeràrquica.

Entendrem alguns punts clau de l'estructura de dades de l'arbre.

• Una estructura de dades d'arbre es defineix com una col·lecció d'objectes o entitats conegudes com a nodes que s'enllaçen per representar o simular la jerarquia.
• Una estructura de dades en arbre és una estructura de dades no lineal perquè no s'emmagatzema de manera seqüencial. És una estructura jeràrquica ja que els elements d'un arbre estan disposats en diversos nivells.
• A l'estructura de dades de l'arbre, el node superior es coneix com a node arrel. Cada node conté algunes dades, i les dades poden ser de qualsevol tipus. A l'estructura d'arbre anterior, el node conté el nom de l'empleat, de manera que el tipus de dades seria una cadena.
• Cada node conté algunes dades i l'enllaç o referència d'altres nodes que es poden anomenar fills.

Alguns termes bàsics utilitzats a l'estructura de dades de l'arbre.

Considerem l'estructura de l'arbre, que es mostra a continuació:

A l'estructura anterior, cada node està etiquetat amb algun número. Cada fletxa que es mostra a la figura anterior es coneix com a enllaç entre els dos nodes.

Arrel:El node arrel és el node superior de la jerarquia de l'arbre. En altres paraules, el node arrel és el que no té cap pare. A l'estructura anterior, el node numerat 1 és el node arrel de l'arbre. Si un node està directament vinculat a algun altre node, s'anomenaria relació pare-fill.Node fill:Si el node és descendent de qualsevol node, llavors el node es coneix com a node fill.Pare:Si el node conté algun subnode, llavors es diu que aquest node és el pare d'aquest subnode.Germà:Els nodes que tenen el mateix pare es coneixen com a germans.Node de fulla: -El node de l'arbre, que no té cap node fill, s'anomena node fulla. Un node fulla és el node més baix de l'arbre. Hi pot haver qualsevol nombre de nodes de fulla presents en un arbre general. Els nodes de fulla també es poden anomenar nodes externs.Nodes interns:Un node té almenys un node fill conegut com a intern Node ancestre: -Un avantpassat d'un node és qualsevol node predecessor en un camí des de l'arrel fins a aquest node. El node arrel no té cap avantpassat. A l'arbre que es mostra a la imatge anterior, els nodes 1, 2 i 5 són els avantpassats del node 10.Descendent:El successor immediat del node donat es coneix com a descendent d'un node. A la figura anterior, 10 és el descendent del node 5.

Propietats de l'estructura de dades de l'arbre

Estructura de dades recursives:L'arbre també es coneix com a estructura de dades recursives . Un arbre es pot definir de manera recursiva perquè el node distingit en una estructura de dades d'arbre es coneix com a node arrel . El node arrel de l'arbre conté un enllaç a totes les arrels dels seus subarbres. El subarbre esquerre es mostra en color groc a la figura següent, i el subarbre dret es mostra en color vermell. El subarbre esquerre es pot dividir en subarbres que es mostren en tres colors diferents. Recursió significa reduir alguna cosa d'una manera autosimilar. Per tant, aquesta propietat recursiva de l'estructura de dades de l'arbre s'implementa en diverses aplicacions.
Nombre d'arestes:Si hi ha n nodes, hi hauria n-1 arestes. Cada fletxa de l'estructura representa l'enllaç o camí. Cada node, excepte el node arrel, tindrà almenys un enllaç entrant conegut com a vora. Hi hauria un enllaç per a la relació pares-fills.Profunditat del node x:La profunditat del node x es pot definir com la longitud del camí des de l'arrel fins al node x. Una vora aporta una unitat de longitud al camí. Així, la profunditat del node x també es pot definir com el nombre d'arestes entre el node arrel i el node x. El node arrel té 0 profunditat.Alçada del node x:L'alçada del node x es pot definir com el camí més llarg des del node x fins al node fulla.

A partir de les propietats de l'estructura de dades de l'arbre, els arbres es classifiquen en diverses categories.

Implementació de l'arbre

L'estructura de dades d'arbre es pot crear creant els nodes de manera dinàmica amb l'ajuda dels punters. L'arbre de la memòria es pot representar com es mostra a continuació:

La figura anterior mostra la representació de l'estructura de dades de l'arbre a la memòria. A l'estructura anterior, el node conté tres camps. El segon camp emmagatzema les dades; el primer camp emmagatzema l'adreça del fill esquerre i el tercer camp emmagatzema l'adreça del fill dret.

En programació, l'estructura d'un node es pot definir com:

 struct node { int data; struct node *left; struct node *right; } 

L'estructura anterior només es pot definir per als arbres binaris perquè l'arbre binari pot tenir el màxim de dos fills, i els arbres genèrics poden tenir més de dos fills. L'estructura del node per als arbres genèrics seria diferent en comparació amb l'arbre binari.

Aplicacions dels arbres

Les següents són les aplicacions dels arbres:

Emmagatzematge de dades jeràrquiques de manera natural:Els arbres s'utilitzen per emmagatzemar les dades a l'estructura jeràrquica. Per exemple, el sistema de fitxers. El sistema de fitxers emmagatzemat a la unitat de disc, el fitxer i la carpeta tenen la forma de dades jeràrquiques naturalment i s'emmagatzemen en forma d'arbres.Organitzar dades:S'utilitza per organitzar les dades per a una inserció, supressió i cerca eficients. Per exemple, un arbre binari té un temps logN per cercar un element.Prova:És un tipus especial d'arbre que s'utilitza per emmagatzemar el diccionari. És una manera ràpida i eficaç per a la correcció ortogràfica dinàmica.Munt:També és una estructura de dades en arbre implementada mitjançant matrius. S'utilitza per implementar cues de prioritat.B-Tree i B+Tree:B-Tree i B+Tree són les estructures de dades d'arbre utilitzades per implementar la indexació a les bases de dades.Taula d'encaminament:L'estructura de dades d'arbre també s'utilitza per emmagatzemar les dades a les taules d'encaminament dels encaminadors.

Tipus d'estructura de dades d'arbre

Els següents són els tipus d'estructura de dades d'arbre:

Arbre general:L'arbre general és un dels tipus d'estructura de dades d'arbre. A l'arbre general, un node pot tenir 0 o n nombre màxim de nodes. No hi ha cap restricció imposada sobre el grau del node (el nombre de nodes que pot contenir un node). El node superior d'un arbre general es coneix com a node arrel. Els fills del node pare es coneixen com subarbres .

Hi pot haver n nombre de subarbres en un arbre general. A l'arbre general, els subarbres no estan ordenats ja que els nodes del subarbre no es poden ordenar.
Cada arbre no buit té una vora descendent, i aquestes vores estan connectades als nodes coneguts com a nodes fills . El node arrel està etiquetat amb el nivell 0. Els nodes que tenen el mateix pare es coneixen com a germans . Arbre binari :Aquí, el propi nom binari suggereix dos nombres, és a dir, 0 i 1. En un arbre binari, cada node d'un arbre pot tenir com a màxim dos nodes fills. Aquí, màxim significa si el node té 0 nodes, 1 node o 2 nodes.

Per saber més sobre l'arbre binari, feu clic a l'enllaç que es mostra a continuació:
https://www.javatpoint.com/binary-tree Arbre de cerca binària :L'arbre de cerca binari és una estructura de dades no lineal a la qual està connectat un node n nombre de nodes. És una estructura de dades basada en nodes. Un node es pot representar en un arbre de cerca binari amb tres camps, és a dir, part de dades, fill esquerre i fill dret. Un node es pot connectar als dos nodes secundaris màxims d'un arbre de cerca binari, de manera que el node conté dos punters (fill esquerre i punter secundari dret).
Cada node del subarbre esquerre ha de contenir un valor inferior al valor del node arrel, i el valor de cada node del subarbre dret ha de ser més gran que el valor del node arrel.

Es pot crear un node amb l'ajuda d'un tipus de dades definit per l'usuari conegut com a estructura, com es mostra a continuació:

 struct node { int data; struct node *left; struct node *right; } 

L'anterior és l'estructura del node amb tres camps: camp de dades, el segon camp és el punter esquerre del tipus de node i el tercer camp és el punter dret del tipus de node.

Per saber més sobre l'arbre de cerca binari, feu clic a l'enllaç següent:

https://www.javatpoint.com/binary-search-tree

Arbre AVL

És un dels tipus de l'arbre binari, o podem dir que és una variant de l'arbre de cerca binari. L'arbre AVL satisfà la propietat del arbre binari així com de la arbre de cerca binari . És un arbre de cerca binari d'autoequilibri que va ser inventat per Adelson Velsky Lindas . Aquí, l'autoequilibri significa que equilibrar les altures del subarbre esquerre i del subarbre dret. Aquest equilibri es mesura en termes de factor d'equilibri .

Podem considerar un arbre com un arbre AVL si l'arbre obeeix l'arbre de cerca binari així com un factor d'equilibri. El factor d'equilibri es pot definir com el diferència entre l'alçada del subarbre esquerre i l'alçada del subarbre dret . El valor del factor d'equilibri ha de ser 0, -1 o 1; per tant, cada node de l'arbre AVL hauria de tenir el valor del factor d'equilibri com a 0, -1 o 1.

Per saber més sobre l'arbre AVL, feu clic a l'enllaç següent:

https://www.javatpoint.com/avl-tree

Arbre vermell-negre

L'arbre vermell-negre és l'arbre de cerca binari. El requisit previ de l'arbre vermell-negre és que hem de conèixer l'arbre de cerca binari. En un arbre de cerca binari, el valor del subarbre esquerre hauria de ser inferior al valor d'aquest node i el valor del subarbre dret hauria de ser més gran que el valor d'aquest node. Com sabem que la complexitat temporal de la cerca binària en el cas mitjà és log₂n, el millor cas és O(1) i el pitjor és O(n).

Quan es realitza qualsevol operació a l'arbre, volem que el nostre arbre estigui equilibrat perquè totes les operacions com la cerca, la inserció, la supressió, etc., triguin menys temps, i totes aquestes operacions tindran la complexitat temporal de registre₂n.

L'arbre vermell-negre és un arbre de cerca binari d'autoequilibri. L'arbre AVL també és un arbre de cerca binari que equilibra l'alçada per què necessitem un arbre vermell-negre? . A l'arbre AVL, no sabem quantes rotacions caldrien per equilibrar l'arbre, però a l'arbre vermell-negre calen un màxim de 2 rotacions per equilibrar l'arbre. Conté un bit addicional que representa el color vermell o negre d'un node per garantir l'equilibri de l'arbre.

llarg per encadenar java

Splay arbre

L'estructura de dades de l'arbre splay també és un arbre de cerca binari en el qual l'element accedit recentment es col·loca a la posició arrel de l'arbre realitzant algunes operacions de rotació. Aquí, desplegant significa el node accedit recentment. És un autoequilibri arbre de cerca binari que no té cap condició d'equilibri explícita com AVL arbre.

Podria ser una possibilitat que l'alçada de l'arbre de desplegament no estigui equilibrada, és a dir, l'alçada dels subarbres esquerre i dret pot ser diferent, però les operacions a l'arbre de desplegament tenen l'ordre de calma temps on n és el nombre de nodes.

Splay tree és un arbre equilibrat però no es pot considerar com un arbre d'altura equilibrada perquè després de cada operació es realitza una rotació que condueix a un arbre equilibrat.

Trep

L'estructura de dades Treap prové de l'estructura de dades Tree and Heap. Per tant, inclou les propietats de les estructures de dades d'arbre i heap. A l'arbre de cerca binari, cada node del subarbre esquerre ha de ser igual o menor que el valor del node arrel i cada node del subarbre dret ha de ser igual o més gran que el valor del node arrel. A l'estructura de dades de pila, tant els subarbres dret com esquerre contenen claus més grans que l'arrel; per tant, podem dir que el node arrel conté el valor més baix.

A l'estructura de dades treap, cada node té tots dos clau i prioritat on la clau es deriva de l'arbre de cerca binari i la prioritat es deriva de l'estructura de dades de pila.

El Trep L'estructura de dades té dues propietats que es donen a continuació:

• Fill dret d'un node>=node actual i fill esquerre d'un node<=current node (binary tree)< li>
• Els fills de qualsevol subarbre han de ser més grans que el node (munt)

B-arbre

B-tree és equilibrat m-camí arbre on m defineix l'ordre de l'arbre. Fins ara, hem llegit que el node només conté una clau, però b-tree pot tenir més d'una clau i més de 2 fills. Manté sempre les dades ordenades. A l'arbre binari, és possible que els nodes fulla puguin estar a diferents nivells, però a l'arbre b, tots els nodes fulla han d'estar al mateix nivell.

Si l'ordre és m, el node té les propietats següents:

• Cada node d'un arbre b pot tenir el màxim m nens
• Per als fills mínims, un node fulla té 0 fills, el node arrel té com a mínim 2 fills i el node intern té un sostre mínim de m/2 fills. Per exemple, el valor de m és 5, el que significa que un node pot tenir 5 fills i els nodes interns poden contenir un màxim de 3 fills.
• Cada node té claus màximes (m-1).

El node arrel ha de contenir com a mínim 1 clau i tots els altres nodes han de contenir almenys sostre de m/2 menys 1 claus.