Abans de conèixer les diferències entre l'arbre de cerca binari i l'arbre AVL, hauríem de conèixer l'arbre de cerca binari i l'arbre AVL per separat.
Què és un arbre de cerca binari?
El arbre de cerca binari és un arbre arbre binari. Com sabem, aquest arbre pot tenir 'n' nombre de fills, mentre que; l'arbre binari pot contenir el màxim de dos fills. Per tant, la restricció d'un arbre binari també és seguida per l'arbre de cerca binari. Cada node d'un arbre de cerca binari hauria de tenir el màxim de dos fills; és a dir, podem dir que l'arbre de cerca binari és una variant de l'arbre binari.
L'arbre de cerca binària també segueix les propietats de la cerca binària. En la cerca binària, tots els elements d'una matriu han d'estar ordenats. Calculem l'element central a la cerca binària en què la part esquerra de l'element central conté el valor menor que el valor mitjà i la part dreta de l'element central conté els valors més grans que el valor mitjà.
A l'arbre de cerca binari, l'element central es converteix en el node arrel, la part dreta es converteix en el subarbre dret i la part esquerra es converteix en el subarbre esquerre. Per tant, podem dir que l'arbre de cerca binari és una combinació de a arbre binari i cerca binària .
Nota: l'arbre de cerca binari es pot definir com l'arbre binari en què tots els elements del subarbre esquerre són menors que el node arrel i tots els elements del subarbre dret són més grans que el node arrel.
Complexitat temporal a l'arbre de cerca binari
Si l'arbre de cerca binari és gairebé un arbre equilibrat, llavors totes les operacions tindran una complexitat temporal de O (inici de sessió) perquè la cerca es divideix a l'esquerra o al subarbre dret.
factorial en java
Si l'arbre de cerca binari està inclinat a l'esquerra o a la dreta, llavors totes les operacions tindran la complexitat temporal de O(n) perquè hem de recórrer fins als n elements.
Què és l'arbre AVL?
An Arbre AVL és un arbre de cerca binari d'autoequilibri on la diferència entre les altures dels subarbres esquerre i dret no pot ser més d'un. Aquesta diferència es coneix com a factor d'equilibri. A l'arbre AVL, els valors del factor d'equilibri podrien ser -1, 0 o 1.
Com es produeix l'autoequilibri de l'arbre de cerca binari?
Com sabem, l'arbre AVL és un arbre de cerca binari d'autoequilibri. Si l'arbre de cerca binari no està equilibrat, es pot autoequilibrar amb alguns reordenaments. Aquests reordenaments es poden fer mitjançant algunes rotacions.
Entenem l'autoequilibri a través d'un exemple.
Suposem que volem inserir 10, 20, 30 en un arbre AVL.
Les següents són les maneres d'inserir 10, 20, 30 en un arbre AVL:
Pas 1: Primer, creem un arbre de cerca binari, tal com es mostra a continuació:
Pas 2: A la figura anterior, podem observar que l'arbre està desequilibrat perquè el factor d'equilibri del node 30 és 2. Per tal de convertir-lo en un arbre AVL, hem de fer algunes rotacions. Si fem la rotació correcta al node 20, el node 30 es mourà cap avall, mentre que el node 20 es mourà cap amunt, com es mostra a continuació:
Com podem observar, l'arbre final segueix la propietat de l'arbre de cerca binari i un arbre equilibrat; per tant, és un arbre AVL.
En el cas, l'arbre era arbre deixat desequilibrat, així que fem la rotació correcta al node.
valor de cadena de
Pas 1: Primer creem un arbre de cerca binari tal com es mostra a continuació:
Pas 2: A la figura anterior, podem observar que l'arbre està desequilibrat perquè el factor d'equilibri del node 10 és -2. Per convertir-lo en un arbre AVL, hem de fer algunes rotacions. És un arbre dret desequilibrat, per tant realitzarem la rotació a l'esquerra. Si fem una rotació a l'esquerra al node 20, aleshores el node 20 es mourà cap amunt i el node 10 es mourà cap avall, tal com es mostra a continuació:
Com podem observar, l'arbre final segueix la propietat del Arbre de cerca binària i a arbre equilibrat ; per tant, és un arbre AVL.
Pas 1: Primer creem l'arbre de cerca binària tal com es mostra a continuació:
Pas 2: A la figura anterior, podem observar que l'arbre està desequilibrat perquè el factor d'equilibri del node arrel és 2. Per tal de convertir-lo en un arbre AVL, hem de fer algunes rotacions. L'escenari anterior està desequilibrat esquerra-dreta, ja que un node és l'esquerra del seu node pare i un altre és la dreta del seu node pare. Primer, realitzarem la rotació a l'esquerra, i la rotació passa entre els nodes 10 i 20. Després de la rotació a l'esquerra, 20 es mourà cap amunt i 10 es mourà cap avall, tal com es mostra a continuació:
Tot i així, l'arbre està desequilibrat, així que fem la rotació correcta sobre l'arbre. Un cop realitzada la rotació correcta a l'arbre, l'arbre voldria, tal com es mostra a continuació:
no és igual a mysql
Com podem observar a l'arbre anterior, l'arbre segueix la propietat de l'arbre de cerca binari i un arbre equilibrat; per tant, és un arbre AVL.
Pas 1: Primer, creem l'arbre de cerca binària, tal com es mostra a continuació:
Pas 2: A la figura anterior, podem observar que l'arbre està desequilibrat perquè el factor d'equilibri del node arrel és 2. Per convertir-lo en un arbre AVL, hem de fer algunes rotacions. L'escenari anterior està desequilibrat dreta-esquerra, ja que un node es troba a la dreta del seu node pare i un altre node queda a l'esquerra del seu node pare. Primer, realitzarem la rotació correcta que passa entre els nodes 30 i 20. Després de la rotació dreta, 20 es mourà cap amunt i 30 es mourà cap avall, tal com es mostra a continuació:
Tot i així, l'arbre anterior està desequilibrat, de manera que hem de fer la rotació a l'esquerra al node. Un cop realitzada la rotació a l'esquerra, el node 20 es mourà cap amunt i el node 10 es mourà cap avall com es mostra a continuació:
Com podem observar a l'arbre anterior, l'arbre segueix la propietat de l'arbre de cerca binari i un arbre equilibrat; per tant, és un arbre AVL.
Diferències entre l'arbre de cerca binària i l'arbre AVL
| Arbre de cerca binària | Arbre AVL |
|---|---|
| Cada arbre de cerca binari és un arbre binari perquè tots dos arbres contenen el màxim de dos fills. | Cada arbre AVL també és un arbre binari perquè l'arbre AVL també té el màxim de dos fills. |
| A BST, no hi ha cap terme, com el factor d'equilibri. | A l'arbre AVL, cada node conté un factor d'equilibri i el valor del factor d'equilibri ha de ser -1, 0 o 1. |
| Cada arbre de cerca binària no és un arbre AVL perquè BST podria ser un arbre equilibrat o desequilibrat. | Cada arbre AVL és un arbre de cerca binari perquè l'arbre AVL segueix la propietat del BST. |
| Cada node de l'arbre de cerca binària consta de tres camps, és a dir, el subarbre esquerre, el valor del node i el subarbre dret. | Cada node de l'arbre AVL consta de quatre camps, és a dir, el subarbre esquerre, el valor del node, el subarbre dret i el factor d'equilibri. |
| En el cas de l'arbre de cerca binària, si volem inserir qualsevol node a l'arbre, comparem el valor del node amb el valor arrel; si el valor del node és més gran que el valor del node arrel, el node s'insereix al subarbre dret, en cas contrari, el node s'insereix al subarbre esquerre. Un cop inserit el node, no cal comprovar el factor d'equilibri d'alçada perquè la inserció es completi. | En el cas de l'arbre AVL, primer, trobarem el lloc adequat per inserir el node. Un cop inserit el node, calcularem el factor d'equilibri de cada node. Si es compleix el factor d'equilibri de cada node, la inserció es completa. Si el factor d'equilibri és superior a 1, hem de fer algunes rotacions per equilibrar l'arbre. |
| A l'arbre de cerca binària, l'alçada o la profunditat de l'arbre és O(n) on n és el nombre de nodes de l'arbre de cerca binària. | A l'arbre AVL, l'alçada o la profunditat de l'arbre és O(logn). |
| És senzill d'implementar ja que hem de seguir les propietats de cerca binària per inserir el node. | És complex d'implementar perquè a l'arbre AVL, primer hem de construir l'arbre AVL i després hem de comprovar l'equilibri d'alçada. Si l'alçada és desequilibri, hem de fer algunes rotacions per equilibrar l'arbre. |
| BST no és un arbre equilibrat perquè no segueix el concepte del factor d'equilibri. | L'arbre AVL és un arbre d'alçada equilibrada perquè segueix el concepte del factor d'equilibri. |
| La cerca és ineficient a BST quan hi ha un gran nombre de nodes disponibles a l'arbre perquè l'alçada no està equilibrada. | La cerca és eficient a l'arbre AVL fins i tot quan hi ha un gran nombre de nodes a l'arbre perquè l'alçada està equilibrada. |