VSTAVLJANJE V DREVO AVL

Drevo AVL:

Drevo AVL je samouravnoteženo binarno iskalno drevo ( BST ), kjer razlika med višino levega in desnega poddrevesa ne sme biti večja od eno za vsa vozlišča.

Primer drevesa AVL:

Zgornje drevo je AVL, ker so razlike med višinami levega in desnega poddrevesa za vsako vozlišče manjše ali enake 1.

Primer drevesa, ki NI drevo AVL:

Zgornje drevo ni AVL, ker so razlike med višino levega in desnega poddrevesa za 8 in 12 večje od 1.

Zakaj AVL Trees?

Večina operacij BST (npr. iskanje, max, min, vstavljanje, brisanje... itd.) traja O(h) čas kje h je višina BST. Stroški teh operacij lahko postanejo O(n) za poševno binarno drevo . Če poskrbimo, da višina drevesa ostane O(log(n)) po vsakem vstavljanju in brisanju lahko zagotovimo zgornjo mejo O(log(n)) za vse te operacije. Višina drevesa AVL je vedno O(log(n)) kje n je število vozlišč v drevesu.

Vstavljanje v drevesu AVL:

Da zagotovimo, da dano drevo ostane AVL po vsakem vstavljanju, moramo povečati standardno operacijo vstavljanja BST, da izvedemo nekaj ponovnega uravnoteženja.
Sledita dve osnovni operaciji, ki ju je mogoče izvesti za uravnoteženje BST, ne da bi kršili lastnost BST (tipke (levo)

Leva rotacija
Desna rotacija

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

Priporočena praksa AVL Tree Insertion Preizkusite!

Koraki za vstavljanje:

Naj bo novo vstavljeno vozlišče noter

Izvedite standard BST vložek za noter .
Začeti od noter , potujte navzgor in poiščite prvo neuravnoteženo vozlišče . Pustiti z biti prvo neuravnoteženo vozlišče, in bodi otrok od z ki prihaja na pot od noter do z in x bodi vnuk od z ki prihaja na pot od noter do z .
Ponovno uravnotežite drevo tako, da izvedete ustrezne rotacije na poddrevesu, ki ima korenine z. Obstajajo lahko 4 možni primeri, ki jih je treba obravnavati kot x, y in z se lahko uredi na 4 načine.
Sledijo 4 možne ureditve:
- y je levi otrok od z in x je levi otrok od y (leva leva črka)
- y je levi otrok od z in x je desni podrejeni od y (Left Right Case)
- y je desni otrok od z in x je desni otrok od y (Right Right Case)
- y je desni otrok od z in x je levi otrok od y (Right Left Case)

Sledijo operacije, ki jih je treba izvesti v zgoraj omenjenih 4 primerih. V vseh primerih moramo le ponovno uravnoteženje poddrevo s koreninami z in celotno drevo postane uravnoteženo kot višina poddrevesa (po ustreznih rotacijah), ukoreninjenega z z postane enak, kot je bil pred vstavitvijo.

1. Levi levi primer

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. Levi desni primer

 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. Desni pravi primer

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

4. Desni levi primer

 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>

Ilustracija vstavljanja v drevo AVL

de-lensed1

avlinsert2-jpg

avlinsert3

avlinsert4

avlinsert5

Pristop:

Ideja je, da uporabimo rekurzivno vstavljanje BST, po vstavitvi dobimo kazalce na vse prednike enega za drugim na način od spodaj navzgor. Torej ne potrebujemo nadrejenega kazalca za potovanje navzgor. Rekurzivna koda sama potuje navzgor in obišče vse prednike na novo vstavljenega vozlišča.

Za uresničitev ideje sledite spodnjim korakom:

Izvedite normalno Vstavljanje BST.
Trenutno vozlišče mora biti eden od prednikov na novo vstavljenega vozlišča. Posodobite višina trenutnega vozlišča.
Pridobite faktor ravnotežja (višina levega poddrevesa – višina desnega poddrevesa) trenutnega vozlišča.
Če je faktor ravnotežja večji od 1, potem je trenutno vozlišče neuravnoteženo in smo bodisi v Levi levi primer oz levi desni primer . Da preverim, ali je levi levi primer ali ne, primerjajte novo vstavljeni ključ s ključem v levi koren poddrevesa .
Če je faktor ravnotežja manjši od -1 , potem je trenutno vozlišče neuravnoteženo in smo bodisi v Desnem Desnem primeru ali Desno-Levem primeru. Če želite preveriti, ali gre za desni desni primer ali ne, primerjajte novo vstavljeni ključ s ključem v desnem korenu poddrevesa.

Spodaj je izvedba zgornjega pristopa:

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->višina;> }> > // 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->ključ = ključ;> >node->levo = NULL;> >node->desno = NULL;> >node->višina = 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->levo;> >Node *T2 = x->prav;> > >// Perform rotation> >x->desno = y;> >y->levo = T2;> > >// Update heights> >y->višina = max(višina(y->levo),> >height(y->desno)) + 1;> >x->višina = max(višina(x->levo),> >height(x->desno)) + 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->prav;> >Node *T2 = y->levo;> > >// Perform rotation> >y->levo = x;> >x->desno = T2;> > >// Update heights> >x->višina = max(višina(x->levo),> >height(x->desno)) + 1;> >y->višina = max(višina(y->levo),> >height(y->desno)) + 1;> > >// Return new root> >return> y;> }> > // Get Balance factor of node N> int> getBalance(Node *N)> {> >if> (N == NULL)> >return> 0;> >return> height(N->levo) - višina (N->desno);> }> > // 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->levo = vstavi (vozlišče->levo, tipka);> >else> if> (key>vozlišče->ključ)> >node->desno = vstavi (vozlišče->desno, ključ);> >else> // Equal keys are not allowed in BST> >return> node;> > >/* 2. Update height of this ancestor node */> >node->višina = 1 + max(višina(vozlišče->levo),> >height(node->prav));> > >/* 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 && tipka levo->tipka)> >return> rightRotate(node);> > >// Right Right Case> >if> (balance node->desno->tipka)> >return> leftRotate(node);> > >// Left Right Case> >if> (balance>1 && tipka> vozlišče->levo->tipka)> >{> >node->levo = levoZavrti(vozlišče->levo);> >return> rightRotate(node);> >}> > >// Right Left Case> >if> (balance <-1 && key right->ključ)> >{> >node->desno = desno Zavrti(vozlišče->desno);> >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->levo);   predNaročilo (koren->desno);   } } // Koda gonilnika int main() { Vozlišče *root = NULL;     /* Izdelava drevesa, podanega na zgornji sliki */ root = insert(root, 10);   koren = vstavi(koren, 20);   koren = vstavi(koren, 30);   koren = vstavi (koren, 40);   koren = vstavi (koren, 50);   koren = vstavi(koren, 25);     /* Konstruirano drevo AVL bi bilo 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->višina;> }> > // 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->ključ = ključ;> >node->levo = NULL;> >node->desno = NULL;> >node->višina = 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->levo;> >struct> Node *T2 = x->prav;> > >// Perform rotation> >x->desno = y;> >y->levo = T2;> > >// Update heights> >y->višina = max(višina(y->levo),> >height(y->desno)) + 1;> >x->višina = max(višina(x->levo),> >height(x->desno)) + 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->prav;> >struct> Node *T2 = y->levo;> > >// Perform rotation> >y->levo = x;> >x->desno = T2;> > >// Update heights> >x->višina = max(višina(x->levo),> >height(x->desno)) + 1;> >y->višina = max(višina(y->levo),> >height(y->desno)) + 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->levo) - višina (N->desno);> }> > // 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->levo = vstavi (vozlišče->levo, tipka);> >else> if> (key>vozlišče->ključ)> >node->desno = vstavi (vozlišče->desno, ključ);> >else> // Equal keys are not allowed in BST> >return> node;> > >/* 2. Update height of this ancestor node */> >node->višina = 1 + max(višina(vozlišče->levo),> >height(node->prav));> > >/* 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 && tipka levo->tipka)> >return> rightRotate(node);> > >// Right Right Case> >if> (balance node->desno->tipka)> >return> leftRotate(node);> > >// Left Right Case> >if> (balance>1 && tipka> vozlišče->levo->tipka)> >{> >node->levo = levoZavrti(vozlišče->levo);> >return> rightRotate(node);> >}> > >// Right Left Case> >if> (balance <-1 && key right->ključ)> >{> >node->desno = desno Zavrti(vozlišče->desno);> >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->ključ);> >preOrder(root->levo);> >preOrder(root->prav);> >}> }> > /* 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>vozlišče.ključ) vozlišče.desno = vstavi(vozlišče.desno, ključ);   else // Podvojeni ključi niso dovoljeni return node;     /* 2. Posodobi višino tega vozlišča prednika */ node.height = 1 + max(height(node.left), height(node.right));     /* 3. Pridobite faktor ravnotežja tega vozlišča prednika, da preverite, ali je to vozlišče postalo neuravnoteženo */ int balance = getBalance(node);     // Če to vozlišče postane neuravnoteženo, potem obstajajo // 4 primeri Levo Levo Veliko male črke, če (ravnovesje> 1 && tipka vrni desno Zavrti(vozlišče); // Desno Desno Veliko male črke, če (ravnovesje<-1 && key>vozlišče.desno.tipka) return leftRotate(node);     // Levo Desno Primer if (ravnovesje> 1 && tipka> vozlišče.levo.ključ) { vozlišče.levo = levoZavrti(vozlišče.levo);   return rightRotate(vozlišče);   } // Desno levo Veliko črko if (ravnotežje<-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 in tipka return self.rightRotate(root) # Primer 2 - Desno Desno, če je ravnovesje<-1 and key>root.right.val: return self.leftRotate(root) # Primer 3 - levo desno, če je ravnotežje> 1 in ključ> root.left.val: root.left = self.leftRotate(root.left) return self.rightRotate(root ) # Primer 4 - desno levo, če je ravnotežje<-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>vozlišče.ključ) vozlišče.desno = vstavi(vozlišče.desno, ključ);   else // Podvojeni ključi niso dovoljeni return node;     /* 2. Posodobi višino tega vozlišča prednika */ node.height = 1 + max(height(node.left), height(node.right));     /* 3. Pridobite faktor ravnotežja tega vozlišča prednika, da preverite, ali je to vozlišče postalo neuravnoteženo */ int balance = getBalance(node);     // Če to vozlišče postane neuravnoteženo, potem obstajajo // 4 primeri Levo Levo Primer če (ravnovesje> 1 && tipka vrni desnoZavrti(vozlišče); // Desno Desno Primer če (ravnotežje vozlišče.right.key) vrne levoZavrti(vozlišče) ; // Left Right Case if (balance> 1 && key> node.left.key) {node.left = leftRotate(node.left); return rightRotate(node); } // 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>vozlišče.ključ) vozlišče.desno = this.insert(vozlišče.desno, ključ);   // Podvojeni ključi niso dovoljeni else return node;     /* 2. Posodobi višino tega vozlišča prednika */ node.height = 1 + this.max(this.height(node.left), this.height(node.right));     /* 3. Pridobite faktor ravnotežja tega vozlišča prednika, da preverite, ali je to vozlišče postalo neuravnoteženo */ var balance = this.getBalance(node);     // Če to vozlišče postane neuravnoteženo, potem obstajajo // 4 primeri Levo Levo Veliko črke, če (ravnovesje> 1 && tipka vrne this.rightRotate(vozlišče); // Desno Desno Veliko črke, če (ravnotežje vozlišče.right.key) vrne to. leftRotate(vozlišče); // Left Right Case if (balance> 1 && key> node.left.key) { node.leftRotate(node.left); return this.rightRotate(node) // Right Leva črka če (ravnotežje<-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);>

Izhod

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

Analiza kompleksnosti

Časovna zapletenost: O(log(n)), za vstavljanje
Pomožni prostor: O(1)

naključno število c koda

Operacije vrtenja (levo in desno vrtenje) zahtevajo konstanten čas, saj se tam spremeni le nekaj kazalcev. Posodabljanje višine in pridobivanje faktorja ravnotežja prav tako zahteva stalen čas. Torej časovna zapletenost vstavka AVL ostaja enaka kot pri vstavku BST, ki je O(h), kjer je h višina drevesa. Ker je drevo AVL uravnoteženo, je višina O(Logn). Časovna kompleksnost vložka AVL je torej O(Logn).

Primerjava z Red Black Tree:

Drevo AVL in druga iskalna drevesa s samouravnoteženjem, kot je Red Black, so uporabna za izvedbo vseh osnovnih operacij v O(log n) času. Drevesa AVL so bolj uravnotežena v primerjavi z rdeče-črnimi drevesi, vendar lahko povzročijo več vrtenja med vstavljanjem in brisanjem. Torej, če vaša aplikacija vključuje veliko pogostih vstavljanj in izbrisov, bi morali imeti prednost rdeče črna drevesa. In če so vstavljanja in brisanja manj pogosta in je iskanje pogostejša operacija, potem je treba dati prednost drevesu AVL pred Red Black Tree.

Sledi objava za brisanje v drevesu AVL:
Drevo AVL | 2. sklop (izbris)

TechCodeview