Abans d'entendre el Arbre vermell-negre i arbre AVL diferències, hauríem de conèixer l'arbre vermell-negre i l'arbre AVL per separat.
Què és un arbre vermell-negre?
L'arbre vermell-negre és autoequilibrat arbre de cerca binari en què cada node conté un bit addicional d'informació que denota el color del node. El color del node pot ser vermell o negre, depenent de la informació de bits emmagatzemada pel node.
123 pel·lícula
Propietats
Les següents són les propietats associades a un arbre vermell-negre:
- El node arrel de l'arbre ha de ser negre.
- Un node vermell només pot tenir fills negres. O bé, podem dir que dos nodes adjacents no poden ser de color vermell.
- Si el node no té un fill esquerre o dret, es diu que aquest node és un node fulla. Per tant, posem els fills esquerre i dret a sota del node de fulla conegut com nil
La profunditat negra o alçada negra d'un node de fulla es pot definir com el nombre de negre que trobem quan ens movem del node de la fulla al node arrel. Una de les propietats clau de l'arbre vermell-negre és que cada node de fulla hauria de tenir la mateixa profunditat negra.
Entenem aquesta propietat a través d'un exemple.
A l'arbre anterior, hi ha cinc nodes, en els quals un és vermell i els altres quatre nodes són negres. Hi ha tres nodes de fulles a l'arbre anterior. Ara calculem la profunditat negra de cada node de fulla. Com podem observar que la profunditat negra dels tres nodes de la fulla és 2; per tant, és un arbre vermell-negre.
Si l'arbre no obeeix a cap de les tres propietats anteriors, aleshores no és un arbre vermell-negre.
Alçada d'un arbre vermell-negre
Considereu h com l'alçada de l'arbre que té n nodes. Quin seria el valor més petit de n?. El valor de n és el més petit quan tots els nodes són negres. Si l'arbre conté tots els nodes negres, llavors l'arbre seria un arbre binari complet. Si l'alçada d'un arbre binari complet és h, el nombre de nodes d'un arbre és:
n = 2h -1
Quin seria el valor més gran de n?
El valor de n és més gran quan cada node negre té dos fills vermells, però el node vermell no pot tenir fills vermells, de manera que tindrà fills negres. D'aquesta manera, hi ha capes alternes de nens negres i vermells. Així, si el nombre de capes negres és h, llavors el nombre de capes vermelles també és h; per tant, l'alçada total de l'arbre passa a ser de 2h. El nombre total de nodes és:
n = 2*2h-1
Què és l'arbre AVL?
An Arbre AVL és un arbre de cerca binari d'autoequilibri si observem el cas següent, que és un arbre de cerca binari i un arbre equilibrat.
A l'arbre anterior, la complexitat temporal en el pitjor dels casos per cercar un element és O(h), és a dir, l'alçada de l'arbre. En el cas anterior, el nombre de comparacions fetes per cercar 17 elements és 4, i l'alçada de l'arbre també és 4.
Si considerem l'arbre binari esbiaixat, com es mostra a continuació:
A l'arbre esbiaixat de dalt a la dreta, el nombre de comparacions fetes per cercar 17 elements és 5 i el nombre d'elements presents a l'arbre també és 5. Per tant, podem dir que si l'arbre és un arbre binari esbiaixat, la complexitat del temps seria O(n).
Ara, hem d'equilibrar aquests arbres esbiaixats perquè tinguin la complexitat temporal O(h). Hi ha un terme conegut com a factor d'equilibri , que s'utilitza per autoequilibrar l'arbre de cerca binari. El factor d'equilibri es pot calcular com:
Factor d'equilibri = alçada del subarbre esquerre-altura del subarbre dretEl valor del factor d'equilibri pot ser 1, 0 o -1. Si cada node de l'arbre binari té un valor d'1, 0 o -1, es diu que aquest arbre és equilibrat. arbre binari o arbre AVL.
L'arbre es coneix com un arbre perfectament equilibrat si el factor d'equilibri de cada node és 0. L'arbre AVL és un arbre gairebé equilibrat perquè cada node de l'arbre té el valor del factor d'equilibri 1, 0 o -1.
Diferències entre l'arbre vermell-negre i l'arbre AVL.
A continuació es mostren les diferències entre l'arbre vermell-negre i l'arbre AVL:
L'arbre vermell-negre és un arbre de cerca binari, i l'arbre AVL també és un arbre de cerca binari.
Les regles següents s'apliquen en un arbre vermell-negre:
- El node d'un arbre vermell-negre és de color vermell o negre.
- El color del node arrel ha de ser negre.
- Els nodes adjacents no han de ser vermells. En altres paraules, podem dir que el node vermell no pot tenir fills vermells, però el node negre pot tenir fills negres.
- Hi hauria d'haver el mateix nombre de nodes negres a cada camí; llavors, només un arbre es pot considerar un arbre vermell-negre.
- Els nodes externs són els nuls, que sempre són de color negre.
Regla de l'arbre AVL:
Cada node hauria de tenir el factor d'equilibri com a -1, 0 o 1.
A la figura anterior, hem de comprovar si l'arbre és un arbre vermell-negre o no. Per comprovar-ho, primer hem de comprovar si l'arbre és un arbre de cerca binari o no. Com podem observar a la figura anterior que compleix totes les propietats de l'arbre de cerca binari; per tant, és un arbre de cerca binari. En segon lloc, hem de comprovar si compleix o no les normes esmentades anteriorment. L'arbre anterior compleix totes les cinc regles anteriors; per tant, conclou que l'arbre anterior és un arbre vermell-negre.
A la figura anterior, hem de comprovar si l'arbre és un arbre AVL o no. Com que cada node té un valor de factor d'equilibri com a -1, 0 o 1, per tant és un arbre AVL.
En el cas d'un arbre vermell-negre, si es compleixen totes les regles anteriors, sempre que un arbre sigui un arbre de cerca binari, llavors es diu que l'arbre és un arbre vermell-negre.
En el cas de l'arbre AVL, si el factor d'equilibri és -1, 0 o 1, es diu que l'arbre anterior és un arbre AVL.
Si l'arbre no està equilibrat, s'utilitzen dues eines per equilibrar l'arbre en un arbre vermell-negre:
Si l'arbre no està equilibrat, s'utilitza una eina per equilibrar l'arbre a l'arbre AVL:
En el cas de l'arbre vermell-negre, les operacions d'inserció i supressió són eficients. Si l'arbre s'equilibra amb la recoloració, les operacions d'inserció i supressió són eficients a l'arbre vermell-negre.
En el cas de l'arbre AVL, l'operació de cerca és eficient, ja que només requereix una eina per equilibrar l'arbre.
En el cas de l'arbre vermell-negre, la complexitat temporal de totes les operacions, és a dir, la inserció, la supressió i la cerca és O(logn).
En el cas de l'arbre AVL, la complexitat temporal de totes les operacions, és a dir, inserció, supressió i cerca és O(logn).
Entenem les diferències en la forma tabular.
| Paràmetre | Arbre negre vermell | Arbre AVL |
|---|---|---|
| Buscant | L'arbre negre vermell no proporciona una cerca eficient, ja que els arbres negres vermells estan aproximadament equilibrats. | Els arbres AVL proporcionen una cerca eficient, ja que és un arbre estrictament equilibrat. |
| Inserció i eliminació | La inserció i la supressió són més fàcils a l'arbre vermell negre ja que requereix menys rotacions per equilibrar l'arbre. | La inserció i la supressió són complexes a l'arbre AVL, ja que requereixen diverses rotacions per equilibrar l'arbre. |
| Color del node | A l'arbre vermell-negre, el color del node és vermell o negre. | En el cas dels arbres AVL, no hi ha color del node. |
| Factor d'equilibri | No conté cap factor d'equilibri. Emmagatzema només un bit d'informació que denota el color vermell o negre del node. | Cada node té un factor d'equilibri a l'arbre AVL el valor del qual pot ser 1, 0 o -1. Requereix espai addicional per emmagatzemar el factor d'equilibri per node. |
| Estrictament equilibrat | Els arbres vermell-negres no estan estrictament equilibrats. | Els arbres AVL estan estrictament equilibrats, és a dir, l'alçada del subarbre esquerre i l'alçada del subarbre dret difereixen com a màxim en 1. |