Arborele AVL:
Arborele AVL este un arbore de căutare binar cu auto-echilibrare ( BST ) unde diferența dintre înălțimile subarborilor din stânga și din dreapta nu poate fi mai mare de unu pentru toate nodurile.
Exemplu de arbore AVL:
Arborele de mai sus este AVL deoarece diferențele dintre înălțimile subarborilor din stânga și din dreapta pentru fiecare nod sunt mai mici sau egale cu 1.
Exemplu de arbore care NU este un arbore AVL:
Arborele de mai sus nu este AVL deoarece diferențele dintre înălțimile subarborilor din stânga și din dreapta pentru 8 și 12 sunt mai mari decât 1.
De ce arbori AVL?
Majoritatea operațiunilor BST (de exemplu, căutare, max, min, inserare, ștergere etc.) iau Oh) timp unde h este înălțimea BST. Costul acestor operațiuni poate deveni Pe) Pentru o Arborele binar înclinat . Dacă ne asigurăm că înălțimea copacului rămâne O(log(n)) după fiecare inserare și ștergere, atunci putem garanta o limită superioară a O(log(n)) pentru toate aceste operațiuni. Înălțimea unui arbore AVL este întotdeauna O(log(n)) Unde n este numărul de noduri din arbore.
Inserare în arborele AVL:
Pentru a ne asigura că arborele dat rămâne AVL după fiecare inserare, trebuie să creștem operația standard de inserare BST pentru a efectua o reechilibrare.
Următoarele sunt două operațiuni de bază care pot fi efectuate pentru a echilibra un BST fără a încălca proprietatea BST (taste (stânga)
- Rotație la stânga
- Rotire dreapta
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 și / <- - - - - - - / 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.>Practică recomandată Inserarea arborelui AVL Încercați!
Pași de urmat pentru inserare:
Fie nodul nou introdus În
- Efectuați standardul BST insert pentru În .
- Începând de la În , călătoriți sus și găsiți-l pe primul nod dezechilibrat . Lăsa Cu fi primul nod dezechilibrat, și fie copil de Cu care vine pe calea de la În la Cu și X fie nepotul de Cu care vine pe calea de la În la Cu .
- Reechilibrați arborele efectuând rotații adecvate pe subarborele înrădăcinat cu Cu. Pot exista 4 cazuri posibile care trebuie tratate ca X y și Cu poate fi aranjat în 4 moduri.
- Iată cele 4 posibile aranjamente:
- y este copilul din stânga al lui z și x este copilul din stânga al lui y (cazul stânga stânga)
- y este copilul din stânga al lui z și x este copilul din dreapta al lui y (cazul stânga dreapta)
- y este copilul drept al lui z și x este copilul drept al lui y (cazul drept dreapta)
- y este copilul din dreapta al lui z și x este copilul din stânga al lui y (cazul din dreapta stânga)
Următoarele sunt operațiunile care trebuie efectuate în cele 4 cazuri menționate mai sus. În toate cazurile, trebuie doar să o facem reechilibrare subarborele înrădăcinat cu Cu iar arborele complet devine echilibrat pe măsură ce înălțimea subarborelui (După rotații corespunzătoare) înrădăcinată cu Cu devine la fel ca înainte de inserare.
1. Stânga Stânga Casă
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. Carcasa stânga dreapta
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. Carcasa dreapta dreapta
z y / / T1 y Left Rotate(z) z x / - - - - - - - ->/ / T2 x T1 T2 T3 T4 / T3 T4>
4. Carcasa Dreapta Stânga
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>
Ilustrație a inserției la arborele AVL
Abordare:
Ideea este să folosim inserția recursivă BST, după inserare, obținem indicii către toți strămoșii unul câte unul într-o manieră de jos în sus. Deci nu avem nevoie de un indicator pentru părinte pentru a călători în sus. Codul recursiv însuși călătorește în sus și vizitează toți strămoșii nodului nou introdus.
Urmați pașii menționați mai jos pentru a implementa ideea:
- Faceți normalul Inserarea BST.
- Nodul curent trebuie să fie unul dintre strămoșii nodului nou introdus. Actualizați înălţime a nodului curent.
- Obțineți factorul de echilibru (înălțimea arborelui din stânga – înălțimea arborelui din dreapta) a nodului curent.
- Dacă factorul de echilibru este mai mare decât 1, atunci nodul curent este dezechilibrat și suntem fie în Stânga Stânga sau stânga Carcasa dreapta . Pentru a verifica dacă este minuscul stânga sau nu, comparați cheia nou introdusă cu cheia din rădăcină subarbore stângă .
- Dacă factorul de echilibru este mai mic decât -1 , atunci nodul curent este dezechilibrat și suntem fie în cazul Dreapta Dreapta, fie în cazul Dreapta-Stânga. Pentru a verifica dacă este cazul sau nu dreapta dreapta, comparați cheia nou introdusă cu cheia din rădăcina subarborescului din dreapta.
Mai jos este implementarea abordării de mai sus:
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->înălţime;>>> // A utility function to get maximum> // of two integers> int> max(>int> a,>int> b)> {> >return> (a>b)? a: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->cheie = cheie;>>> // 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->stânga;>>> // Perform rotation> >x->dreapta = y;>>> // Update heights> >y->înălțime = max(înălțime (y->stânga),> >height(y->dreapta)) + 1;>>> >height(x->dreapta)) + 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->dreapta;>>> // Perform rotation> >y->stânga = x;>>> // Update heights> >x->înălțime = max(înălțime (x->stânga),> >height(x->dreapta)) + 1;>>> >height(y->dreapta)) + 1;>>> // Return new root> >return> y;> }> > // Get Balance factor of node N> int> getBalance(Node *N)> {> >if> (N == NULL)> >return> 0;> >return> height(N->stânga) - înălțime (N->dreapta);>>> // 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->stânga = insert(nod->stânga, cheie);>>> if> (key>nod->cheie)>>> // Equal keys are not allowed in BST> >return> node;> > >/* 2. Update height of this ancestor node */> >node->înălțime = 1 + max(înălțime (nod->stânga),> >height(node->dreapta));>>> /* 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 && tasta stânga->tasta)>>> rightRotate(node);> > >// Right Right Case> >if> (balance node->dreapta->tasta)>>> leftRotate(node);> > >// Left Right Case> >if> (balance>1 && tasta> nod->stânga->tasta)>>> >node->stânga = stângaRotire(nod->stânga);>>> rightRotate(node);> >}> > >// Right Left Case> >if> (balance <-1 && key right->tasta)>>> >node->dreapta = dreaptaRotire(nod->dreapta);>>> 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->stânga); precomandă(rădăcină->dreapta); } } // Cod driver int main() { Nod *root = NULL; /* Construirea arborelui dat în figura de mai sus */ root = insert(root, 10); rădăcină = insert (rădăcină, 20); rădăcină = insert (rădăcină, 30); rădăcină = insert(rădăcină, 40); rădăcină = insert (rădăcină, 50); rădăcină = insert (rădăcină, 25); /* Arborele AVL construit ar fi 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->înălţime;>>> // A utility function to get maximum of two integers> int> max(>int> a,>int> b)> {> >return> (a>b)? a: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->cheie = cheie;>>> 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->stânga;>>> Node *T2 = x->dreapta;>>> // Perform rotation> >x->dreapta = y;>>> // Update heights> >y->înălțime = max(înălțime (y->stânga),> >height(y->dreapta)) + 1;>>> >height(x->dreapta)) + 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->dreapta;>>> Node *T2 = y->stânga;>>> // Perform rotation> >y->stânga = x;>>> // Update heights> >x->înălțime = max(înălțime (x->stânga),> >height(x->dreapta)) + 1;>>> >height(y->dreapta)) + 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->stânga) - înălțime (N->dreapta);>>> // 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->stânga = insert(nod->stânga, cheie);>>> if> (key>nod->cheie)>>> // Equal keys are not allowed in BST> >return> node;> > >/* 2. Update height of this ancestor node */> >node->înălțime = 1 + max(înălțime (nod->stânga),> >height(node->dreapta));>>> /* 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 && tasta stânga->tasta)>>> rightRotate(node);> > >// Right Right Case> >if> (balance node->dreapta->tasta)>>> leftRotate(node);> > >// Left Right Case> >if> (balance>1 && tasta> nod->stânga->tasta)>>> >node->stânga = stângaRotire(nod->stânga);>>> rightRotate(node);> >}> > >// Right Left Case> >if> (balance <-1 && key right->tasta)>>> >node->dreapta = dreaptaRotire(nod->dreapta);>>> 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->cheie);>>> }> > /* 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;> }> |
>
>
Java
// 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) ? a: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>node.key) node.right = insert(nod.right, key); else // Cheile duplicate nu sunt permise returnează nodul; /* 2. Actualizați înălțimea acestui nod strămoș */ node.height = 1 + max(height(node.left), height(node.right)); /* 3. Obțineți factorul de echilibru al acestui nod strămoș pentru a verifica dacă acest nod a devenit dezechilibrat */ int balance = getBalance(node); // Dacă acest nod devine dezechilibrat, atunci există // 4 cazuri Left Left Case if (balance> 1 && tasta return rightRotate(nod); // Right Right Case if (balance)<-1 && key>node.right.key) return leftRotate(nod); // Left Right Case if (balance> 1 && key> node.left.key) { node.left = leftRotate(node.left); returnează dreaptaRotire(nodul); } // Dreapta Stânga Casă dacă (sold<-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 și cheia returnează self.rightRotate (rădăcină) # Cazul 2 - Dreapta Dreapta dacă echilibru<-1 and key>root.right.val: return self.leftRotate(root) # Cazul 3 - Stânga Dreapta dacă echilibru> 1 și cheie> root.left.val: root.left = self.leftRotate(root.left) return self.rightRotate(rădăcină ) # Cazul 4 - Dreapta Stânga dacă este echilibrat<-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) ? a: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>node.key) node.right = insert(nod.right, key); else // Cheile duplicate nu sunt permise returnează nodul; /* 2. Actualizați înălțimea acestui nod strămoș */ node.height = 1 + max(height(node.left), height(node.right)); /* 3. Obțineți factorul de echilibru al acestui nod strămoș pentru a verifica dacă acest nod a devenit dezechilibrat */ int balance = getBalance(node); // Dacă acest nod devine dezechilibrat, atunci există // 4 cazuri Left Left Case if (balance> 1 && tasta return rightRotate(nod); // Right Right Case if (balance node.right.key) return leftRotate(node) ; // Left Right Case if (balance> 1 && key> node.left.left = leftRotate(node.left) // Right Left Case 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? a: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>node.key) node.right = this.insert(node.right, key); // Cheile duplicate nu sunt permise altfel returnează nodul; /* 2. Actualizați înălțimea acestui nod strămoș */ node.height = 1 + this.max(this.height(node.left), this.height(node.right)); /* 3. Obțineți factorul de echilibru al acestui nod strămoș pentru a verifica dacă acest nod a devenit dezechilibrat */ var balance = this.getBalance(node); // Dacă acest nod devine dezechilibrat, atunci există // 4 cazuri Left Left Case if (balance> 1 && key return this.rightRotate(node); // Right Right Case if (balance node.right.key) return this.rightRotate(node); // Right Right Case if (balance node.right.key) return this. leftRotate(node); // Left Right Case if (balance> 1 && key> node.left.key) { node.left = this.leftRotate (node.rightRotate } // Right); Left Case if (sold<-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);> |
>
>Ieșire
Preorder traversal of the constructed AVL tree is 30 20 10 25 40 50>
Analiza complexității
Complexitatea timpului: O(log(n)), pentru inserare
Spațiu auxiliar: O(1)
actor berbec
Operațiile de rotație (rotire la stânga și la dreapta) durează constant, deoarece doar câteva indicatori sunt modificate acolo. Actualizarea înălțimii și obținerea factorului de echilibru necesită, de asemenea, timp constant. Deci, complexitatea de timp a inserției AVL rămâne aceeași cu inserția BST, care este O(h) unde h este înălțimea arborelui. Deoarece arborele AVL este echilibrat, înălțimea este O(Logn). Deci, complexitatea de timp a inserției AVL este O (Logn).
Comparație cu Red Black Tree:
Arborele AVL și alți arbori de căutare cu auto-echilibrare, cum ar fi Red Black, sunt utile pentru a realiza toate operațiunile de bază în timp O(log n). Arborii AVL sunt mai echilibrați în comparație cu arborii roșu-negru, dar pot provoca mai multe rotații în timpul inserării și ștergerii. Deci, dacă aplicația dvs. implică multe inserări și ștergeri frecvente, atunci arborii roșu negru ar trebui să fie preferați. Și dacă inserările și ștergerile sunt mai puțin frecvente și căutarea este operația mai frecventă, atunci arborele AVL ar trebui să fie preferat față de arborele negru roșu.
Mai jos este postarea pentru ștergere în arborele AVL:
Arbore AVL | Setul 2 (Ștergere)