logo

TechCodeview

Insättning i ett AVL-träd

AVL-träd:

AVL-trädet är ett självbalanserande binärt sökträd ( BST ) där skillnaden mellan höjderna på vänster och höger underträd inte kan vara mer än ett för alla noder.

Exempel på AVL-träd:



Ovanstående träd är AVL eftersom skillnaderna mellan höjderna på vänster och höger underträd för varje nod är mindre än eller lika med 1.

Exempel på ett träd som INTE är ett AVL-träd:

Ovanstående träd är inte AVL eftersom skillnaderna mellan höjderna på vänster och höger underträd för 8 och 12 är större än 1.



Varför AVL-träd?

De flesta av BST-operationerna (t.ex. sökning, max, min, infoga, ta bort... etc) tar Åh) tid var h är höjden på BST. Kostnaden för dessa operationer kan bli På) för en skevt Binärt träd . Om vi ​​ser till att höjden på trädet finns kvar O(log(n)) efter varje infogning och borttagning, då kan vi garantera en övre gräns för O(log(n)) för alla dessa operationer. Höjden på ett AVL-träd är alltid O(log(n)) var n är antalet noder i trädet.

Införande i AVL-trädet:

För att säkerställa att det givna trädet förblir AVL efter varje infogning, måste vi utöka standard BST-insättningsoperationen för att utföra en viss ombalansering.
Följande är två grundläggande operationer som kan utföras för att balansera en BST utan att bryta mot BST-egenskapen (nycklar (vänster)

  • Vänsterrotation
  • Höger rotation
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 och / <- - - - - - - /  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.>
Rekommenderad övning AVL-trädinsättning Prova!

Steg att följa för insättning:

Låt den nyligen infogade noden vara I



  • Utför standard BST infoga för I .
  • Med början från I , resa upp och hitta den första obalanserad nod . Låta Med vara den första obalanserade noden, och bli den barn av Med som kommer på vägen från I till Med och x bli den barnbarn av Med som kommer på vägen från I till Med .
  • Balansera om trädet genom att utföra lämpliga rotationer på underträdet som är rotat med Med. Det kan finnas 4 möjliga ärenden som behöver hanteras som x,y och Med kan ordnas på 4 sätt.
  • Följande är de fyra möjliga arrangemangen:
    • y är det vänstra barnet till z och x är det vänstra barnet till y (vänster vänster skiftläge)
    • y är det vänstra barnet till z och x är det högra barnet till y (vänster höger skiftläge)
    • y är rätt barn till z och x är rätt barn till y (Right Right Case)
    • y är det högra barnet till z och x är det vänstra barnet till y (Right Left Case)

Följande är de operationer som ska utföras i ovan nämnda 4 fall. I alla fall behöver vi bara återbalansera underträdet rotat med Med och hela trädet blir balanserat som höjden på underträdet (Efter lämpliga rotationer) rotat med Med blir samma som det var innan insättningen.

1. Vänster Vänster Fall 

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. Vänster Höger Case 

 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. Höger höger fall 

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

4. Höger Vänster Case 

 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>

Illustration av insättning vid AVL-träd

avlinsad 1

avlinsert2-jpg

avlinsert3

avlinsert4

avlinsert5

Närma sig:

Tanken är att använda rekursiv BST-insättning, efter infogning får vi pekare till alla förfäder en efter en på ett bottom-up-sätt. Så vi behöver ingen föräldrapekare för att resa upp. Själva den rekursiva koden åker upp och besöker alla förfäder till den nyligen infogade noden.

Följ stegen nedan för att implementera idén:

  • Utför det normala BST-insättning.
  • Den aktuella noden måste vara en av förfäderna till den nyligen infogade noden. Uppdatera höjd för den aktuella noden.
  • Få balansfaktorn (vänster underträdshöjd – höger underträdshöjd) för den aktuella noden.
  • Om balansfaktorn är större än 1, då är den nuvarande noden obalanserad och vi är antingen i Vänster Vänster fall eller vänster Höger fall . För att kontrollera om det är det vänster vänster fall eller inte, jämför den nyligen införda nyckeln med nyckeln i vänster underträdsrot .
  • Om balansfaktorn är mindre än -1 , då är den aktuella noden obalanserad och vi är antingen i höger höger-fall eller höger-vänster-fall. För att kontrollera om det är rätt högerfall eller inte, jämför den nyinfogade nyckeln med nyckeln i den högra underträdroten.

Nedan är implementeringen av ovanstående tillvägagångssätt:

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->höjd;> }> > // 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->nyckel = nyckel;> >node->vänster = NULL;> >node->höger = NULL;> >node->höjd = 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->vänster;> >Node *T2 = x->höger;> > >// Perform rotation> >x->höger = y;> >y->vänster = T2;> > >// Update heights> >y->höjd = max(höjd(y->vänster),> >height(y->höger)) + 1;> >x->höjd = max(höjd(x->vänster),> >height(x->höger)) + 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->höger;> >Node *T2 = y->vänster;> > >// Perform rotation> >y->vänster = x;> >x->höger = T2;> > >// Update heights> >x->höjd = max(höjd(x->vänster),> >height(x->höger)) + 1;> >y->höjd = max(höjd(y->vänster),> >height(y->höger)) + 1;> > >// Return new root> >return> y;> }> > // Get Balance factor of node N> int> getBalance(Node *N)> {> >if> (N == NULL)> >return> 0;> >return> height(N->vänster) - höjd(N->höger);> }> > // 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->vänster = infoga(nod->vänster, nyckel);> >else> if> (key>nod->nyckel)> >node->höger = infoga(nod->höger, nyckel);> >else> // Equal keys are not allowed in BST> >return> node;> > >/* 2. Update height of this ancestor node */> >node->höjd = 1 + max(höjd(nod->vänster),> >height(node->höger));> > >/* 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 &&-knapp vänster->knapp)> >return> rightRotate(node);> > >// Right Right Case> >if> (balance node->höger->knapp)> >return> leftRotate(node);> > >// Left Right Case> >if> (balance>1 &&-tangent> nod->vänster->tangent)> >{> >node->vänster = vänsterRotate(nod->vänster);> >return> rightRotate(node);> >}> > >// Right Left Case> >if> (balance <-1 && key right->nyckel)> >{> >node->höger = högerRotate(nod->höger);> >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->vänster); förbeställning(root->höger); } } // Driver Code int main() { Node *root = NULL; /* Konstruktionsträd som anges i figuren ovan */ root = insert(root, 10); root = insert(root, 20); root = insert(root, 30); root = insert(root, 40); root = insert(root, 50); root = insert(root, 25); /* Det konstruerade AVL-trädet skulle vara 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->höjd;> }> > // 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->nyckel = nyckel;> >node->vänster = NULL;> >node->höger = NULL;> >node->höjd = 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->vänster;> >struct> Node *T2 = x->höger;> > >// Perform rotation> >x->höger = y;> >y->vänster = T2;> > >// Update heights> >y->höjd = max(höjd(y->vänster),> >height(y->höger)) + 1;> >x->höjd = max(höjd(x->vänster),> >height(x->höger)) + 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->höger;> >struct> Node *T2 = y->vänster;> > >// Perform rotation> >y->vänster = x;> >x->höger = T2;> > >// Update heights> >x->höjd = max(höjd(x->vänster),> >height(x->höger)) + 1;> >y->höjd = max(höjd(y->vänster),> >height(y->höger)) + 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->vänster) - höjd(N->höger);> }> > // 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->vänster = infoga(nod->vänster, nyckel);> >else> if> (key>nod->nyckel)> >node->höger = infoga(nod->höger, nyckel);> >else> // Equal keys are not allowed in BST> >return> node;> > >/* 2. Update height of this ancestor node */> >node->höjd = 1 + max(höjd(nod->vänster),> >height(node->höger));> > >/* 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 &&-knapp vänster->knapp)> >return> rightRotate(node);> > >// Right Right Case> >if> (balance node->höger->knapp)> >return> leftRotate(node);> > >// Left Right Case> >if> (balance>1 &&-tangent> nod->vänster->tangent)> >{> >node->vänster = vänsterRotate(nod->vänster);> >return> rightRotate(node);> >}> > >// Right Left Case> >if> (balance <-1 && key right->nyckel)> >{> >node->höger = högerRotate(nod->höger);> >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->nyckel);> >preOrder(root->vänster);> >preOrder(root->höger);> >}> }> > /* 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 = infoga(nod.höger, nyckel); else // Duplicerade nycklar inte tillåtna returnod; /* 2. Uppdatera höjden för denna förfadernod */ node.height = 1 + max(height(node.left), height(node.right)); /* 3. Hämta balansfaktorn för denna förfadernod för att kontrollera om denna nod blev obalanserad */ int balance = getBalance(nod); // Om denna nod blir obalanserad, då finns det // 4 fall Vänster Vänster Case if (balans> 1 && nyckel returnera rightRotate(nod); // Höger Höger Case if (balans<-1 && key>node.right.key) returnera vänsterRotate(nod); // Left Right Case if (balans> 1 &&-tangent> node.left.key) { node.left = leftRotate(node.left); return rightRotate(nod); } // Höger Vänster Case if (balans<-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 och nyckel returnerar self.rightRotate(root) # Fall 2 - Höger Höger om balans<-1 and key>root.right.val: return self.leftRotate(root) # Fall 3 - Left Right om balans> 1 och nyckel> root.left.val: root.left = self.leftRotate(root.left) return self.rightRotate(root ) # Fall 4 - Höger Vänster om balans<-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 = infoga(nod.höger, nyckel); else // Duplicerade nycklar inte tillåtna returnod; /* 2. Uppdatera höjden för denna förfadernod */ node.height = 1 + max(height(node.left), height(node.right)); /* 3. Hämta balansfaktorn för denna förfadernod för att kontrollera om denna nod blev obalanserad */ int balance = getBalance(nod); // Om denna nod blir obalanserad, då finns det // 4 fall Vänster Vänster Case if (balans> 1 && tangent retur rightRotate(nod); // Right Right Case if (balans node.right.key) return leftRotate(nod) ; // Left Right Case if (saldo> 1 && nyckel> node.left.key) { node.left = leftRotate(node.left } // Right Left Case;<-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, nyckel); // Duplicerade nycklar inte tillåtna annars returnod; /* 2. Uppdatera höjden på denna förfadernod */ node.height = 1 + this.max(this.height(node.left), this.height(node.right)); /* 3. Hämta balansfaktorn för denna förfadernod för att kontrollera om denna nod blev obalanserad */ var balance = this.getBalance(nod); // Om denna nod blir obalanserad, då finns det // 4 fall Vänster Vänster Case if (balans> 1 && nyckel returnerar this.rightRotate(nod); // Höger Höger Case if (balans node.right.key) returnerar detta. leftRotate(node); // Left Right Case if (balans> 1 && key> node.left.key) { node.left = this.leftRotate(node.left } // Right; Vänster Fall om (balans<-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);> 

>

>

Produktion 

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

Komplexitetsanalys

Tidskomplexitet: O(log(n)), för insättning
Hjälputrymme: O(1)

supw

Rotationsoperationerna (vänster- och högerrotation) tar konstant tid eftersom endast ett fåtal pekare ändras där. Att uppdatera höjden och få balansfaktorn tar också konstant tid. Så tidskomplexiteten för AVL-insatsen förblir densamma som BST-insättningen som är O(h) där h är trädets höjd. Eftersom AVL-trädet är balanserat är höjden O(Logn). Så tidskomplexiteten för AVL-insättningen är O(Logn).

Jämförelse med Red Black Tree:

AVL-trädet och andra självbalanserande sökträd som Red Black är användbara för att få alla grundläggande operationer gjorda på O(log n)-tid. AVL-träden är mer balanserade jämfört med röd-svarta träd, men de kan orsaka fler rotationer under insättning och radering. Så om din applikation innehåller många frekventa insättningar och raderingar, bör rödsvarta träd föredras. Och om infogningar och raderingar är mindre frekventa och sökning är den vanligaste operationen, bör AVL-trädet föredras framför Red Black Tree .

Följande är inlägget för radering i AVL Tree:
AVL-träd | Set 2 (radering)