INNSETTING I ET AVL-TRE

AVL-tre:

AVL-tre er et selvbalanserende binært søketre ( BST ) hvor forskjellen mellom høyder på venstre og høyre undertrær ikke kan være mer enn en for alle noder.

Eksempel på AVL-tre:

Treet ovenfor er AVL fordi forskjellene mellom høydene til venstre og høyre undertrær for hver node er mindre enn eller lik 1.

Eksempel på et tre som IKKE er et AVL-tre:

Treet ovenfor er ikke AVL fordi forskjellene mellom høydene til venstre og høyre undertre for 8 og 12 er større enn 1.

Hvorfor AVL-trær?

De fleste av BST-operasjonene (f.eks. søk, maks, min, sett inn, slett osv.) tar Åh) tid hvor h er høyden på BST. Kostnaden for disse operasjonene kan bli På) for en skjevt Binært tre . Hvis vi sørger for at høyden på treet forblir O(log(n)) etter hver innsetting og sletting, så kan vi garantere en øvre grense for O(log(n)) for alle disse operasjonene. Høyden på et AVL-tre er alltid O(log(n)) hvor n er antall noder i treet.

Innsetting i AVL Tree:

For å sikre at det gitte treet forblir AVL etter hver innsetting, må vi utvide standard BST-innsettingsoperasjonen for å utføre litt rebalansering.
Følgende er to grunnleggende operasjoner som kan utføres for å balansere en BST uten å krenke BST-egenskapen (taster (venstre)

Venstre rotasjon
Høyre rotasjon

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 og / <- - - - - - - /  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.>

Anbefalt praksis AVL-treinnsetting Prøv det!

Trinn som skal følges for innsetting:

La den nylig innsatte noden være I

Utføre standard BST sette inn for I .
Starter fra I , reis opp og finn den første ubalansert node . La Med være den første ubalanserte noden, og vær den barn av Med som kommer på veien fra I til Med og x vær den barnebarn av Med som kommer på veien fra I til Med .
Rebalanser treet ved å utføre passende rotasjoner på undertreet rotfestet med Med. Det kan være 4 mulige saker som må behandles som x,y og Med kan ordnes på 4 måter.
Følgende er de 4 mulige arrangementene:
- y er det venstre barnet til z og x er det venstre barnet til y (venstre venstre boks)
- y er det venstre barnet til z og x er det høyre barnet til y (venstre høyre bokstav)
- y er det riktige barnet til z og x er det riktige barnet til y (Right Right Case)
- y er det høyre barnet til z og x er det venstre barnet til y (Right Left Case)

Følgende er operasjonene som skal utføres i de ovennevnte 4 tilfellene. I alle tilfellene trenger vi bare det balansere på nytt undertreet forankret med Med og hele treet blir balansert som høyden på undertreet (Etter passende rotasjoner) forankret med Med blir det samme som før innsetting.

1. Venstre venstre sak

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. Venstre Høyre 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øyre Høyre Case

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

4. Høyre venstre boks

 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>

Illustrasjon av innsetting ved AVL-tre

avlinsert1

avlinsert2-jpg

avlinsert3

avlinsert4

avlinsert5

Nærme seg:

Tanken er å bruke rekursiv BST-innsetting, etter innsetting får vi pekere til alle forfedre én etter én på en nedenfra-opp-måte. Så vi trenger ikke en foreldrepeker for å reise opp. Selve den rekursive koden reiser opp og besøker alle forfedrene til den nylig innsatte noden.

Følg trinnene nevnt nedenfor for å implementere ideen:

Utfør det normale BST innsetting.
Den nåværende noden må være en av forfedrene til den nylig innsatte noden. Oppdater høyde av gjeldende node.
Få balansefaktoren (høyde venstre undertre – høyde undertre høyre) av gjeldende node.
Hvis balansefaktoren er større enn 1, da er den nåværende noden ubalansert og vi er enten i Venstre Venstre sak eller venstre Høyre sak . For å sjekke om det er det venstre venstre sak eller ikke, sammenligne den nylig innsatte nøkkelen med nøkkelen i venstre undertrerot .
Hvis balansefaktoren er mindre enn -1 , da er den nåværende noden ubalansert og vi er enten i høyre-høyre-tilfelle eller høyre-venstre-tilfelle. For å sjekke om det er riktig høyre tilfelle eller ikke, sammenligne den nylig innsatte nøkkelen med nøkkelen i høyre undertrerot.

Nedenfor er implementeringen av tilnærmingen ovenfor:

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øyde;> }> > // 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->nøkkel = nøkkel;> >node->venstre = NULL;> >node->høyre = NULL;> >node->høyde = 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->venstre;> >Node *T2 = x->Ikke sant;> > >// Perform rotation> >x->høyre = y;> >y->venstre = T2;> > >// Update heights> >y->høyde = maks(høyde(y->venstre),> >height(y->høyre)) + 1;> >x->høyde = maks(høyde(x->venstre),> >height(x->høyre)) + 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->Ikke sant;> >Node *T2 = y->venstre;> > >// Perform rotation> >y->venstre = x;> >x->høyre = T2;> > >// Update heights> >x->høyde = maks(høyde(x->venstre),> >height(x->høyre)) + 1;> >y->høyde = maks(høyde(y->venstre),> >height(y->høyre)) + 1;> > >// Return new root> >return> y;> }> > // Get Balance factor of node N> int> getBalance(Node *N)> {> >if> (N == NULL)> >return> 0;> >return> height(N->venstre) - høyde(N->høyre);> }> > // 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->venstre = insert(node->venstre, nøkkel);> >else> if> (key>node->nøkkel)> >node->høyre = insert(node->høyre, nøkkel);> >else> // Equal keys are not allowed in BST> >return> node;> > >/* 2. Update height of this ancestor node */> >node->høyde = 1 + maks(høyde(node->venstre),> >height(node->Ikke sant));> > >/* 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 &&-tast venstre->tast)> >return> rightRotate(node);> > >// Right Right Case> >if> (balance node->høyre->tast)> >return> leftRotate(node);> > >// Left Right Case> >if> (balance>1 &&-tast> node->venstre->tast)> >{> >node->venstre = venstreRoter(node->venstre);> >return> rightRotate(node);> >}> > >// Right Left Case> >if> (balance <-1 && key right->nøkkel)> >{> >node->høyre = høyreRoter(node->høyre);> >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->venstre);   forhåndsbestilling(root->høyre);   } } // Driverkode int main() { Node *root = NULL;     /* Konstruksjonstre gitt i figuren ovenfor */ 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 konstruerte AVL-treet vil være 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øyde;> }> > // 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->nøkkel = nøkkel;> >node->venstre = NULL;> >node->høyre = NULL;> >node->høyde = 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->venstre;> >struct> Node *T2 = x->Ikke sant;> > >// Perform rotation> >x->høyre = y;> >y->venstre = T2;> > >// Update heights> >y->høyde = maks(høyde(y->venstre),> >height(y->høyre)) + 1;> >x->høyde = maks(høyde(x->venstre),> >height(x->høyre)) + 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->Ikke sant;> >struct> Node *T2 = y->venstre;> > >// Perform rotation> >y->venstre = x;> >x->høyre = T2;> > >// Update heights> >x->høyde = maks(høyde(x->venstre),> >height(x->høyre)) + 1;> >y->høyde = maks(høyde(y->venstre),> >height(y->høyre)) + 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->venstre) - høyde(N->høyre);> }> > // 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->venstre = insert(node->venstre, nøkkel);> >else> if> (key>node->nøkkel)> >node->høyre = insert(node->høyre, nøkkel);> >else> // Equal keys are not allowed in BST> >return> node;> > >/* 2. Update height of this ancestor node */> >node->høyde = 1 + maks(høyde(node->venstre),> >height(node->Ikke sant));> > >/* 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 &&-tast venstre->tast)> >return> rightRotate(node);> > >// Right Right Case> >if> (balance node->høyre->tast)> >return> leftRotate(node);> > >// Left Right Case> >if> (balance>1 &&-tast> node->venstre->tast)> >{> >node->venstre = venstreRoter(node->venstre);> >return> rightRotate(node);> >}> > >// Right Left Case> >if> (balance <-1 && key right->nøkkel)> >{> >node->høyre = høyreRoter(node->høyre);> >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->nøkkel);> >preOrder(root->venstre);> >preOrder(root->Ikke sant);> >}> }> > /* 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(node.right, key);   else // Dupliserte nøkler ikke tillatt returnode;     /* 2. Oppdater høyden til denne stamfarnoden */ node.height = 1 + max(height(node.left), height(node.right));     /* 3. Hent balansefaktoren til denne stamfarnoden for å sjekke om denne noden ble ubalansert */ int balance = getBalance(node);     // Hvis denne noden blir ubalansert, så er det // 4 tilfeller Venstre Venstre Case if (balanse> 1 && tast retur rightRotate(node); // Høyre Høyre Case if (balanse<-1 && key>node.right.key) returner venstreRotate(node);     // Left Right Case if (balanse> 1 &&-tast> node.left.key) { node.left = leftRotate(node.left);   return rightRotate(node);   } // Høyre Venstre Forbokstav if (balanse<-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 og tast returner self.rightRotate(root) # Tilfelle 2 - Høyre Høyre hvis balanse<-1 and key>root.right.val: return self.leftRotate(root) # Tilfelle 3 - Venstre Høyre hvis balanse> 1 og nøkkel> root.left.val: root.left = self.leftRotate(root.left) return self.rightRotate(root ) # Tilfelle 4 - Høyre Venstre hvis balanse<-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(node.right, key);   else // Dupliserte nøkler ikke tillatt returnode;     /* 2. Oppdater høyden til denne stamfarnoden */ node.height = 1 + max(height(node.left), height(node.right));     /* 3. Hent balansefaktoren til denne stamfarnoden for å sjekke om denne noden ble ubalansert */ int balance = getBalance(node);     // Hvis denne noden blir ubalansert, så er det // 4 tilfeller Venstre Venstre Case if (balanse> 1 && tast returner høyreRotate(node); // Høyre Høyre Case if (balanse node.right.key) return leftRotate(node) ; // Left Right Case if (balanse> 1 &&-tast> 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, key);   // Dupliserte nøkler ikke tillatt ellers returnode;     /* 2. Oppdater høyden til denne stamfarnoden */ node.height = 1 + this.max(this.height(node.left), this.height(node.right));     /* 3. Hent balansefaktoren til denne stamfarnoden for å sjekke om denne noden ble ubalansert */ var balance = this.getBalance(node);     // Hvis denne noden blir ubalansert, så er det // 4 tilfeller Venstre Venstre Case if (balanse> 1 && tast returner denne.rightRotate(node); // Høyre Høyre Case if (balanse node.right.key) returner dette. leftRotate(node); // Left Right Case if (balanse> 1 &&-tast> node.left.key) { node.left = this.leftRotate(node.left } // Right Venstre sak hvis (balanse<-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);>

Produksjon

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

Kompleksitetsanalyse

Tidskompleksitet: O(log(n)), for innsetting
Hjelpeplass: O(1)

python rest-operator

Rotasjonsoperasjonene (venstre og høyre rotering) tar konstant tid ettersom bare noen få pekere blir endret der. Å oppdatere høyden og få balansefaktoren tar også konstant tid. Så tidskompleksiteten til AVL-innsatsen forblir den samme som BST-innsatsen som er O(h) hvor h er høyden på treet. Siden AVL-treet er balansert, er høyden O(Logn). Så tidskompleksiteten til AVL-innsettingen er O(Logn).

Sammenligning med Red Black Tree:

AVL-treet og andre selvbalanserende søketrær som Red Black er nyttige for å få alle grunnleggende operasjoner utført på O(log n)-tid. AVL-trærne er mer balanserte sammenlignet med rød-svarte trær, men de kan forårsake flere rotasjoner under innsetting og sletting. Så hvis søknaden din involverer mange hyppige innsettinger og slettinger, bør røde svarte trær foretrekkes. Og hvis innsettingene og slettingene er sjeldnere og søk er den hyppigere operasjonen, bør AVL-treet foretrekkes fremfor Red Black Tree .

Følgende er innlegget for sletting i AVL Tree:
AVL Tree | Sett 2 (sletting)

TechCodeview