logo

TechCodeview

Inserimento in un albero AVL

Albero AVL:

L'albero AVL è un albero di ricerca binario autobilanciante ( BST ) dove la differenza tra le altezze dei sottoalberi sinistro e destro non può essere maggiore di uno per tutti i nodi.

Esempio di albero AVL:



L'albero sopra è AVL perché le differenze tra le altezze dei sottoalberi sinistro e destro per ogni nodo sono inferiori o uguali a 1.

Esempio di un albero che NON è un albero AVL:

L'albero sopra non è AVL perché le differenze tra le altezze dei sottoalberi sinistro e destro per 8 e 12 sono maggiori di 1.



Perchè gli alberi AVL?

La maggior parte delle operazioni BST (ad esempio ricerca, max, min, inserimento, eliminazione, ecc.) richiedono OH) tempo dove H è l'altezza del BST. Il costo di queste operazioni potrebbe diventare SU) per un Albero binario distorto . Se ci assicuriamo che l'altezza dell'albero rimanga O(log(n)) dopo ogni inserimento ed eliminazione, possiamo garantire un limite superiore di O(log(n)) per tutte queste operazioni. L'altezza di un albero AVL è sempre O(log(n)) Dove N è il numero di nodi nell'albero.

Inserimento nell'albero AVL:

Per garantire che l'albero dato rimanga AVL dopo ogni inserimento, dobbiamo aumentare l'operazione di inserimento BST standard per eseguire un po' di ribilanciamento.
Di seguito sono riportate due operazioni di base che possono essere eseguite per bilanciare un BST senza violare la proprietà BST (tasti (sinistra)

  • Rotazione a sinistra
  • Rotazione destra
T1, T2 and T3 are subtrees of the tree, rooted with y (on the left side) or x (on the right side) y x /  Right Rotation /  x T3 - - - - - - ->T1 e/<- - - - - - - /  T1 T2 Left Rotation T2 T3 Keys in both of the above trees follow the following order keys(T1) < key(x) < keys(T2) < key(y) < keys(T3) So BST property is not violated anywhere.>
Pratica consigliata per l'inserimento dell'albero AVL Provalo!

Passaggi da seguire per l'inserimento:

Lascia che sia il nodo appena inserito In



  • Esegui la norma BST inserire per In .
  • A partire da In , viaggia verso l'alto e trova il primo nodo sbilanciato . Permettere Con essere il primo nodo sbilanciato, E essere il bambino Di Con che arriva sul sentiero da In A Con E X essere il nipote Di Con che arriva sul sentiero da In A Con .
  • Riequilibrare l'albero eseguendo opportune rotazioni sul sottoalbero con cui è radicata Con. Ci possono essere 4 possibili casi che devono essere gestiti come x,y E Con può essere organizzato in 4 modi.
  • Di seguito le 4 possibili disposizioni:
    • y è il figlio sinistro di z e x è il figlio sinistro di y (Left Left Case)
    • y è il figlio sinistro di z e x è il figlio destro di y (Left Right Case)
    • y è il figlio destro di z e x è il figlio destro di y (Giusto Giusto)
    • y è il figlio destro di z e x è il figlio sinistro di y (Destra Sinistra)

Di seguito sono riportate le operazioni da eseguire nei 4 casi sopra menzionati. In tutti i casi, dobbiamo solo farlo riequilibrare il sottoalbero radicato con Con e l'albero completo diventa equilibrato quanto l'altezza del sottoalbero (dopo opportune rotazioni) con cui radica Con diventa lo stesso di prima dell'inserimento.

1. Custodia sinistra sinistra 

T1, T2, T3 and T4 are subtrees. z y /  /  y T4 Right Rotate (z) x z /  - - - - - - - - ->/  /  x T3 T1 T2 T3 T4 /  T1 T2>

2. Caso Sinistra Destra 

 z z x /  /  /  y T4 Left Rotate (y) x T4 Right Rotate(z) y z /  - - - - - - - - ->/  - - - - - - - -> /  /  T1 x y T3 T1 T2 T3 T4 /  /  T2 T3 T1 T2>

3. Giusto Giusto Caso 

 z y /  /  T1 y Left Rotate(z) z x /  - - - - - - - ->/  /  T2 x T1 T2 T3 T4 /  T3 T4>

4. Caso Destra Sinistra 

 z z x /  /  /  T1 y Right Rotate (y) T1 x Left Rotate(z) z y /  - - - - - - - - ->/  - - - - - - - -> /  /  x T4 T2 y T1 T2 T3 T4 /  /  T2 T3 T3 T4>

Illustrazione dell'inserimento nell'albero AVL

senza lente1

avlinsert2-jpg

avlinsert3

avlinsert4

avlinsert5

Approccio:

L'idea è di utilizzare l'inserimento BST ricorsivo, dopo l'inserimento, otteniamo puntatori a tutti gli antenati uno per uno in modo dal basso verso l'alto. Quindi non abbiamo bisogno di un puntatore genitore per viaggiare verso l'alto. Il codice ricorsivo stesso viaggia verso l'alto e visita tutti gli antenati del nodo appena inserito.

Seguire i passaggi indicati di seguito per implementare l'idea:

  • Esegui la normale Inserimento BST.
  • Il nodo corrente deve essere uno degli antenati del nodo appena inserito. Aggiorna il altezza del nodo corrente.
  • Ottieni il fattore di equilibrio (altezza sottoalbero sinistro – altezza sottoalbero destro) del nodo corrente.
  • Se il fattore di equilibrio è maggiore di 1, allora il nodo corrente è sbilanciato e ci troviamo nel Caso sinistro sinistro O caso sinistro destro . Per verificare se lo è custodia sinistra sinistra o no, confrontare la chiave appena inserita con la chiave nel file radice del sottoalbero sinistro .
  • Se il fattore di equilibrio è inferiore a -1 , allora il nodo corrente è sbilanciato e siamo nel caso Destra Destra o Destra-Sinistra. Per verificare se si tratta del caso Right Right o meno, confrontare la chiave appena inserita con la chiave nella radice del sottoalbero destro.

Di seguito è riportata l’implementazione dell’approccio di cui sopra:

C++14




// C++ program to insert a node in AVL tree> #include> using> namespace> std;> > // An AVL tree node> class> Node> {> >public>:> >int> key;> >Node *left;> >Node *right;> >int> height;> };> > // A utility function to get the> // height of the tree> int> height(Node *N)> {> >if> (N == NULL)> >return> 0;> >return> N->altezza;> }> > // A utility function to get maximum> // of two integers> int> max(>int> a,>int> b)> {> >return> (a>B)? un:b;> }> > /* Helper function that allocates a> >new node with the given key and> >NULL left and right pointers. */> Node* newNode(>int> key)> {> >Node* node =>new> Node();> >node->chiave = chiave;> >node->sinistra = NULL;> >node->destra = NULL;> >node->altezza = 1;>// new node is initially> >// added at leaf> >return>(node);> }> > // A utility function to right> // rotate subtree rooted with y> // See the diagram given above.> Node *rightRotate(Node *y)> {> >Node *x = y->Sinistra;> >Node *T2 = x->Giusto;> > >// Perform rotation> >x->destra = y;> >y->sinistra = T2;> > >// Update heights> >y->altezza = max(altezza(y->sinistra),> >height(y->a destra)) + 1;> >x->altezza = max(altezza(x->sinistra),> >height(x->a destra)) + 1;> > >// Return new root> >return> x;> }> > // A utility function to left> // rotate subtree rooted with x> // See the diagram given above.> Node *leftRotate(Node *x)> {> >Node *y = x->Giusto;> >Node *T2 = y->Sinistra;> > >// Perform rotation> >y->sinistra = x;> >x->destra = T2;> > >// Update heights> >x->altezza = max(altezza(x->sinistra),> >height(x->a destra)) + 1;> >y->altezza = max(altezza(y->sinistra),> >height(y->a destra)) + 1;> > >// Return new root> >return> y;> }> > // Get Balance factor of node N> int> getBalance(Node *N)> {> >if> (N == NULL)> >return> 0;> >return> height(N->sinistra) - altezza(N->destra);> }> > // Recursive function to insert a key> // in the subtree rooted with node and> // returns the new root of the subtree.> Node* insert(Node* node,>int> key)> {> >/* 1. Perform the normal BST insertion */> >if> (node == NULL)> >return>(newNode(key));> > >if> (key key)> >node->sinistra = inserisci(nodo->sinistra, chiave);> >else> if> (key>nodo->chiave)> >node->destra = inserisci(nodo->destra, chiave);> >else> // Equal keys are not allowed in BST> >return> node;> > >/* 2. Update height of this ancestor node */> >node->altezza = 1 + max(altezza(nodo->sinistra),> >height(node->Giusto));> > >/* 3. Get the balance factor of this ancestor> >node to check whether this node became> >unbalanced */> >int> balance = getBalance(node);> > >// If this node becomes unbalanced, then> >// there are 4 cases> > >// Left Left Case> >if> (balance>1 && tasto sinistra->tasto)> >return> rightRotate(node);> > >// Right Right Case> >if> (balance node->tasto destro->)> >return> leftRotate(node);> > >// Left Right Case> >if> (balance>1 && tasto> nodo->sinistra->tasto)> >{> >node->sinistra = ruota a sinistra(nodo->sinistra);> >return> rightRotate(node);> >}> > >// Right Left Case> >if> (balance <-1 && key right->chiave)> >{> >node->destra = destraRuota(nodo->destra);> >return> leftRotate(node);> >}> > >/* return the (unchanged) node pointer */> >return> node;> }> > // A utility function to print preorder> // traversal of the tree.> // The function also prints height> // of every node> void> preOrder(Node *root)> {> >if>(root != NULL)> >{> >cout ' '; preOrder(root->Sinistra); preOrdine(root->destra); } } // Codice driver int main() { Node *root = NULL; /* Costruzione dell'albero indicato nella figura sopra */ root = insert(root, 10); radice = inserisci(radice, 20); radice = inserisci(radice, 30); radice = inserisci(radice, 40); radice = inserisci(radice, 50); radice = inserisci(radice, 25); /* L'albero AVL costruito sarebbe 30 / 20 40 / 10 25 50 */ cout<< 'Preorder traversal of the ' 'constructed AVL tree is '; preOrder(root); return 0; } // This code is contributed by // rathbhupendra> 

>

>

C




// C program to insert a node in AVL tree> #include> #include> > // An AVL tree node> struct> Node> {> >int> key;> >struct> Node *left;> >struct> Node *right;> >int> height;> };> > // A utility function to get the height of the tree> int> height(>struct> Node *N)> {> >if> (N == NULL)> >return> 0;> >return> N->altezza;> }> > // A utility function to get maximum of two integers> int> max(>int> a,>int> b)> {> >return> (a>B)? un: b;> }> > /* Helper function that allocates a new node with the given key and> >NULL left and right pointers. */> struct> Node* newNode(>int> key)> {> >struct> Node* node = (>struct> Node*)> >malloc>(>sizeof>(>struct> Node));> >node->chiave = chiave;> >node->sinistra = NULL;> >node->destra = NULL;> >node->altezza = 1;>// new node is initially added at leaf> >return>(node);> }> > // A utility function to right rotate subtree rooted with y> // See the diagram given above.> struct> Node *rightRotate(>struct> Node *y)> {> >struct> Node *x = y->Sinistra;> >struct> Node *T2 = x->Giusto;> > >// Perform rotation> >x->destra = y;> >y->sinistra = T2;> > >// Update heights> >y->altezza = max(altezza(y->sinistra),> >height(y->a destra)) + 1;> >x->altezza = max(altezza(x->sinistra),> >height(x->a destra)) + 1;> > >// Return new root> >return> x;> }> > // A utility function to left rotate subtree rooted with x> // See the diagram given above.> struct> Node *leftRotate(>struct> Node *x)> {> >struct> Node *y = x->Giusto;> >struct> Node *T2 = y->Sinistra;> > >// Perform rotation> >y->sinistra = x;> >x->destra = T2;> > >// Update heights> >x->altezza = max(altezza(x->sinistra),> >height(x->a destra)) + 1;> >y->altezza = max(altezza(y->sinistra),> >height(y->a destra)) + 1;> > >// Return new root> >return> y;> }> > // Get Balance factor of node N> int> getBalance(>struct> Node *N)> {> >if> (N == NULL)> >return> 0;> >return> height(N->sinistra) - altezza(N->destra);> }> > // Recursive function to insert a key in the subtree rooted> // with node and returns the new root of the subtree.> struct> Node* insert(>struct> Node* node,>int> key)> {> >/* 1. Perform the normal BST insertion */> >if> (node == NULL)> >return>(newNode(key));> > >if> (key key)> >node->sinistra = inserisci(nodo->sinistra, chiave);> >else> if> (key>nodo->chiave)> >node->destra = inserisci(nodo->destra, chiave);> >else> // Equal keys are not allowed in BST> >return> node;> > >/* 2. Update height of this ancestor node */> >node->altezza = 1 + max(altezza(nodo->sinistra),> >height(node->Giusto));> > >/* 3. Get the balance factor of this ancestor> >node to check whether this node became> >unbalanced */> >int> balance = getBalance(node);> > >// If this node becomes unbalanced, then> >// there are 4 cases> > >// Left Left Case> >if> (balance>1 && tasto sinistra->tasto)> >return> rightRotate(node);> > >// Right Right Case> >if> (balance node->tasto destro->)> >return> leftRotate(node);> > >// Left Right Case> >if> (balance>1 && tasto> nodo->sinistra->tasto)> >{> >node->sinistra = ruota a sinistra(nodo->sinistra);> >return> rightRotate(node);> >}> > >// Right Left Case> >if> (balance <-1 && key right->chiave)> >{> >node->destra = destraRuota(nodo->destra);> >return> leftRotate(node);> >}> > >/* return the (unchanged) node pointer */> >return> node;> }> > // A utility function to print preorder traversal> // of the tree.> // The function also prints height of every node> void> preOrder(>struct> Node *root)> {> >if>(root != NULL)> >{> >printf>(>'%d '>, root->chiave);> >preOrder(root->Sinistra);> >preOrder(root->Giusto);> >}> }> > /* Driver program to test above function*/> int> main()> {> >struct> Node *root = NULL;> > >/* Constructing tree given in the above figure */> >root = insert(root, 10);> >root = insert(root, 20);> >root = insert(root, 30);> >root = insert(root, 40);> >root = insert(root, 50);> >root = insert(root, 25);> > >/* The constructed AVL Tree would be> >30> >/> >20 40> >/> >10 25 50> >*/> > >printf>(>'Preorder traversal of the constructed AVL'> >' tree is '>);> >preOrder(root);> > >return> 0;> }> 

>

>

Giava




// Java program for insertion in AVL Tree> class> Node {> >int> key, height;> >Node left, right;> > >Node(>int> d) {> >key = d;> >height =>1>;> >}> }> > class> AVLTree {> > >Node root;> > >// A utility function to get the height of the tree> >int> height(Node N) {> >if> (N ==>null>)> >return> 0>;> > >return> N.height;> >}> > >// A utility function to get maximum of two integers> >int> max(>int> a,>int> b) {> >return> (a>B) ? un:b;> >}> > >// A utility function to right rotate subtree rooted with y> >// See the diagram given above.> >Node rightRotate(Node y) {> >Node x = y.left;> >Node T2 = x.right;> > >// Perform rotation> >x.right = y;> >y.left = T2;> > >// Update heights> >y.height = max(height(y.left), height(y.right)) +>1>;> >x.height = max(height(x.left), height(x.right)) +>1>;> > >// Return new root> >return> x;> >}> > >// A utility function to left rotate subtree rooted with x> >// See the diagram given above.> >Node leftRotate(Node x) {> >Node y = x.right;> >Node T2 = y.left;> > >// Perform rotation> >y.left = x;> >x.right = T2;> > >// Update heights> >x.height = max(height(x.left), height(x.right)) +>1>;> >y.height = max(height(y.left), height(y.right)) +>1>;> > >// Return new root> >return> y;> >}> > >// Get Balance factor of node N> >int> getBalance(Node N) {> >if> (N ==>null>)> >return> 0>;> > >return> height(N.left) - height(N.right);> >}> > >Node insert(Node node,>int> key) {> > >/* 1. Perform the normal BST insertion */> >if> (node ==>null>)> >return> (>new> Node(key));> > >if> (key node.left = insert(node.left, key); else if (key>nodo.chiave) nodo.destra = insert(nodo.destra, chiave); else // Chiavi duplicate non consentite return node; /* 2. Aggiorna l'altezza di questo nodo antenato */ node.height = 1 + max(height(node.left), Height(node.right)); /* 3. Ottieni il fattore di equilibrio di questo nodo antenato per verificare se questo nodo si è sbilanciato */ int balance = getBalance(node); // Se questo nodo diventa sbilanciato, allora // ci sono 4 casi Left Left Case if (balance> 1 && key return rightRotate(node); // Right Right Case if (balance<-1 && key>nodo.destra.chiave) return leftRotate(nodo); // Sinistra Destra Caso if (balance> 1 && key> node.left.key) { node.left = leftRotate(node.left); ritorna a destraRuota(nodo); } // Destra Sinistra Maiuscole/minuscole se (balance<-1 && key node.right = rightRotate(node.right); return leftRotate(node); } /* return the (unchanged) node pointer */ return node; } // A utility function to print preorder traversal // of the tree. // The function also prints height of every node void preOrder(Node node) { if (node != null) { System.out.print(node.key + ' '); preOrder(node.left); preOrder(node.right); } } public static void main(String[] args) { AVLTree tree = new AVLTree(); /* Constructing tree given in the above figure */ tree.root = tree.insert(tree.root, 10); tree.root = tree.insert(tree.root, 20); tree.root = tree.insert(tree.root, 30); tree.root = tree.insert(tree.root, 40); tree.root = tree.insert(tree.root, 50); tree.root = tree.insert(tree.root, 25); /* The constructed AVL Tree would be 30 / 20 40 / 10 25 50 */ System.out.println('Preorder traversal' + ' of constructed tree is : '); tree.preOrder(tree.root); } } // This code has been contributed by Mayank Jaiswal> 

>

>

Python3




# Python code to insert a node in AVL tree> > # Generic tree node class> class> TreeNode(>object>):> >def> __init__(>self>, val):> >self>.val>=> val> >self>.left>=> None> >self>.right>=> None> >self>.height>=> 1> > # AVL tree class which supports the> # Insert operation> class> AVL_Tree(>object>):> > ># Recursive function to insert key in> ># subtree rooted with node and returns> ># new root of subtree.> >def> insert(>self>, root, key):> > ># Step 1 - Perform normal BST> >if> not> root:> >return> TreeNode(key)> >elif> key root.left = self.insert(root.left, key) else: root.right = self.insert(root.right, key) # Step 2 - Update the height of the # ancestor node root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right)) # Step 3 - Get the balance factor balance = self.getBalance(root) # Step 4 - If the node is unbalanced, # then try out the 4 cases # Case 1 - Left Left if balance>1 e il tasto restituiscono self.rightRotate(root) # Caso 2 - Destra Destra se equilibrio<-1 and key>root.right.val: return self.leftRotate(root) # Caso 3 - Sinistra Destra se equilibrio> 1 e chiave> root.left.val: root.left = self.leftRotate(root.left) return self.rightRotate(root ) # Caso 4 - Destra Sinistra in caso di equilibrio<-1 and key root.right = self.rightRotate(root.right) return self.leftRotate(root) return root def leftRotate(self, z): y = z.right T2 = y.left # Perform rotation y.left = z z.right = T2 # Update heights z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right)) y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right)) # Return the new root return y def rightRotate(self, z): y = z.left T3 = y.right # Perform rotation y.right = z z.left = T3 # Update heights z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right)) y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right)) # Return the new root return y def getHeight(self, root): if not root: return 0 return root.height def getBalance(self, root): if not root: return 0 return self.getHeight(root.left) - self.getHeight(root.right) def preOrder(self, root): if not root: return print('{0} '.format(root.val), end='') self.preOrder(root.left) self.preOrder(root.right) # Driver program to test above function myTree = AVL_Tree() root = None root = myTree.insert(root, 10) root = myTree.insert(root, 20) root = myTree.insert(root, 30) root = myTree.insert(root, 40) root = myTree.insert(root, 50) root = myTree.insert(root, 25) '''The constructed AVL Tree would be 30 / 20 40 / 10 25 50''' # Preorder Traversal print('Preorder traversal of the', 'constructed AVL tree is') myTree.preOrder(root) print() # This code is contributed by Ajitesh Pathak> 

>

>

C#




// C# program for insertion in AVL Tree> using> System;> > class> Node> {> >public> int> key, height;> >public> Node left, right;> > >public> Node(>int> d)> >{> >key = d;> >height = 1;> >}> }> > public> class> AVLTree> {> > >Node root;> > >// A utility function to get> >// the height of the tree> >int> height(Node N)> >{> >if> (N ==>null>)> >return> 0;> > >return> N.height;> >}> > >// A utility function to get> >// maximum of two integers> >int> max(>int> a,>int> b)> >{> >return> (a>B) ? un: b;> >}> > >// A utility function to right> >// rotate subtree rooted with y> >// See the diagram given above.> >Node rightRotate(Node y)> >{> >Node x = y.left;> >Node T2 = x.right;> > >// Perform rotation> >x.right = y;> >y.left = T2;> > >// Update heights> >y.height = max(height(y.left),> >height(y.right)) + 1;> >x.height = max(height(x.left),> >height(x.right)) + 1;> > >// Return new root> >return> x;> >}> > >// A utility function to left> >// rotate subtree rooted with x> >// See the diagram given above.> >Node leftRotate(Node x)> >{> >Node y = x.right;> >Node T2 = y.left;> > >// Perform rotation> >y.left = x;> >x.right = T2;> > >// Update heights> >x.height = max(height(x.left),> >height(x.right)) + 1;> >y.height = max(height(y.left),> >height(y.right)) + 1;> > >// Return new root> >return> y;> >}> > >// Get Balance factor of node N> >int> getBalance(Node N)> >{> >if> (N ==>null>)> >return> 0;> > >return> height(N.left) - height(N.right);> >}> > >Node insert(Node node,>int> key)> >{> > >/* 1. Perform the normal BST insertion */> >if> (node ==>null>)> >return> (>new> Node(key));> > >if> (key node.left = insert(node.left, key); else if (key>nodo.chiave) nodo.destra = insert(nodo.destra, chiave); else // Chiavi duplicate non consentite return node; /* 2. Aggiorna l'altezza di questo nodo antenato */ node.height = 1 + max(height(node.left), Height(node.right)); /* 3. Ottieni il fattore di equilibrio di questo nodo antenato per verificare se questo nodo si è sbilanciato */ int balance = getBalance(node); // Se questo nodo diventa sbilanciato, allora // ci sono 4 casi Left Left Case if (balance> 1 && key return rightRotate(node); // Right Right Case if (balance node.right.key) return leftRotate(node) ; // Sinistra Destra Maiuscola if (balance> 1 && key> node.left.key) { node.left = leftRotate(node.left); return rightRotate(node ​​} // Destra Sinistra Maiuscola if (balance<-1 && key < node.right.key) { node.right = rightRotate(node.right); return leftRotate(node); } /* return the (unchanged) node pointer */ return node; } // A utility function to print preorder traversal // of the tree. // The function also prints height of every node void preOrder(Node node) { if (node != null) { Console.Write(node.key + ' '); preOrder(node.left); preOrder(node.right); } } // Driver code public static void Main(String[] args) { AVLTree tree = new AVLTree(); /* Constructing tree given in the above figure */ tree.root = tree.insert(tree.root, 10); tree.root = tree.insert(tree.root, 20); tree.root = tree.insert(tree.root, 30); tree.root = tree.insert(tree.root, 40); tree.root = tree.insert(tree.root, 50); tree.root = tree.insert(tree.root, 25); /* The constructed AVL Tree would be 30 / 20 40 / 10 25 50 */ Console.Write('Preorder traversal' + ' of constructed tree is : '); tree.preOrder(tree.root); } } // This code has been contributed // by PrinciRaj1992> 

>

>

Javascript




> > >// JavaScript program for insertion in AVL Tree> >class Node {> >constructor(d) {> >this>.key = d;> >this>.height = 1;> >this>.left =>null>;> >this>.right =>null>;> >}> >}> > >class AVLTree {> >constructor() {> >this>.root =>null>;> >}> > >// A utility function to get> >// the height of the tree> >height(N) {> >if> (N ==>null>)>return> 0;> > >return> N.height;> >}> > >// A utility function to get> >// maximum of two integers> >max(a, b) {> >return> a>B ? un: b;> >}> > >// A utility function to right> >// rotate subtree rooted with y> >// See the diagram given above.> >rightRotate(y) {> >var> x = y.left;> >var> T2 = x.right;> > >// Perform rotation> >x.right = y;> >y.left = T2;> > >// Update heights> >y.height =>this>.max(>this>.height(y.left),> >this>.height(y.right)) + 1;> >x.height =>this>.max(>this>.height(x.left),> >this>.height(x.right)) + 1;> > >// Return new root> >return> x;> >}> > >// A utility function to left> >// rotate subtree rooted with x> >// See the diagram given above.> >leftRotate(x) {> >var> y = x.right;> >var> T2 = y.left;> > >// Perform rotation> >y.left = x;> >x.right = T2;> > >// Update heights> >x.height =>this>.max(>this>.height(x.left),> >this>.height(x.right)) + 1;> >y.height =>this>.max(>this>.height(y.left),> >this>.height(y.right)) + 1;> > >// Return new root> >return> y;> >}> > >// Get Balance factor of node N> >getBalance(N) {> >if> (N ==>null>)>return> 0;> > >return> this>.height(N.left) ->this>.height(N.right);> >}> > >insert(node, key) {> >/* 1. Perform the normal BST insertion */> >if> (node ==>null>)>return> new> Node(key);> > >if> (key node.left = this.insert(node.left, key); else if (key>nodo.chiave) nodo.destra = this.insert(nodo.destra, chiave); // Chiavi duplicate non consentite altrimenti return node; /* 2. Aggiorna l'altezza di questo nodo antenato */ node.height = 1 + this.max(this.height(node.left), this.height(node.right)); /* 3. Ottieni il fattore di equilibrio di questo nodo antenato per verificare se questo nodo si è sbilanciato */ var balance = this.getBalance(node); // Se questo nodo diventa sbilanciato, allora // ci sono 4 casi Left Left Case if (balance> 1 && key return this.rightRotate(node); // Right Right Case if (balance node.right.key) restituisce questo. leftRotate(node); // Sinistra Destra Case if (balance> 1 && key> node.left.key) { node.left = this.leftRotate(node.left); return this.rightRotate(node); Caso a sinistra se (balance<-1 && key < node.right.key) { node.right = this.rightRotate(node.right); return this.leftRotate(node); } /* return the (unchanged) node pointer */ return node; } // A utility function to print preorder traversal // of the tree. // The function also prints height of every node preOrder(node) { if (node != null) { document.write(node.key + ' '); this.preOrder(node.left); this.preOrder(node.right); } } } // Driver code var tree = new AVLTree(); /* Constructing tree given in the above figure */ tree.root = tree.insert(tree.root, 10); tree.root = tree.insert(tree.root, 20); tree.root = tree.insert(tree.root, 30); tree.root = tree.insert(tree.root, 40); tree.root = tree.insert(tree.root, 50); tree.root = tree.insert(tree.root, 25); /* The constructed AVL Tree would be 30 / 20 40 / 10 25 50 */ document.write( 'Preorder traversal of the ' + 'constructed AVL tree is ' ); tree.preOrder(tree.root);> 

>

>

Produzione 

Preorder traversal of the constructed AVL tree is 30 20 10 25 40 50>

Analisi della complessità

Complessità temporale: O(log(n)), per l'inserimento
Spazio ausiliario: O(1)

rinominare nella directory Linux

Le operazioni di rotazione (rotazione a sinistra e a destra) richiedono un tempo costante poiché lì vengono modificati solo pochi puntatori. Anche l'aggiornamento dell'altezza e l'ottenimento del fattore di equilibrio richiedono tempo costante. Quindi la complessità temporale dell'inserto AVL rimane la stessa dell'inserto BST che è O(h) dove h è l'altezza dell'albero. Poiché l'albero AVL è bilanciato, l'altezza è O(Logn). Quindi la complessità temporale dell'inserimento AVL è O(Logn).

Confronto con l'albero rosso nero:

L'albero AVL e altri alberi di ricerca autobilanciati come Red Black sono utili per eseguire tutte le operazioni di base in tempo O(log n). Gli alberi AVL sono più bilanciati rispetto agli alberi Rosso-Nero, ma possono causare più rotazioni durante l'inserimento e la cancellazione. Quindi, se la tua applicazione prevede molti inserimenti ed eliminazioni frequenti, allora dovrebbero essere preferiti gli alberi Rosso Nero. E se gli inserimenti e le cancellazioni sono meno frequenti e la ricerca è l'operazione più frequente, allora l'albero AVL dovrebbe essere preferito a Red Black Tree.

Di seguito è riportato il post per l'eliminazione in AVL Tree:
Albero AVL | Imposta 2 (Cancellazione)