The avl property For every node the left and right side differ in height by less than two



Yüklə 445 b.
tarix24.02.2018
ölçüsü445 b.
#27955


AVL Trees


The AVL Property

  • For every node the left and right side differ in height by less than two.

  • The left and right side are themselves AVL trees.



How Balanced is That?

  • AVL trees might end up kinda 'sparse'.

  • The worst case height of an AVL tree with n nodes is about 1.44log(n).

  • Discussion at http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/AVL.html



Rotations

  • Rotations are to rearrange nodes to maintain AVLness.

  • They are needed on insert and delete.



Names of Rotations

  • There are four of them

    • Single Left (LL) and Single Right (RR)
    • Double Left (LR) and Double Right (RL)
  • The names describe which way the node moves. For example, a left rotation moves the node down and left.

  • Nodes always move down when rotated.



How To Do Single Rotations



A Left Rotation via Pointers

  • temp=p->right ;

  • p->right=temp->left ;

  • temp->left=p ;

  • p=temp ;



Double Rotation

  • A LR double rotation is to rotate something to the left, and then its former parent to the right.

  • A RL double rotation is to rotate something to the right, and then its former parent to the left.



Rotation Examples

  • All the rotations in picture form http://sky.fit.qut.edu.au/~maire/avl/System/AVLTree.html

  • All the rotations in pictures and text http://www.cs.jcu.edu.au/Subjects/cp2001/1997/foils/balancedTrees/balancedTrees.html

  • Sample single and double rotations http://ironbark.bendigo.latrobe.edu.au/courses/subjects/DataStructures/mal/session200/lecture.html



The AVL Insertion Algorithm

  • An Intuitive description can be found at http://www.ucfv.bc.ca/cis/watkissc/200009/200009Comp175/notes/avlTrees.html



The AVL Game

  • Play the game http://www.seanet.com/users/arsen/avltree.html



The Insertion Algorithm

  • Recursively call down to find the insertion point.

  • Insert there (it will always be a leaf node).

  • Call rebalance at the end.

    • Will rebalance from the bottup up.
    • Will rebalance only the path from the change to the root.


Insertion Code

  • insert_node (inData)

  • {

  • if (this == NULL)

  • return new Node (inData);

  • if (inData < data)

  • left = left -> insert_node (inData);

  • else

  • right = right -> insert_node (inData);

  • return balance ();

  • }



Notes About the Code

  • Calls balance on the way up.

  • Only calls balance on the path between the change and the root.

  • Call balance too many times for an insert.

  • In this example .... We never change the parent node (or root). Instead we return what that parent node should be. Neat trick!



The Deletion Algorithm

  • Find the place to delete.

  • Swap with the in order successor.

  • Delete that node

    • Remember, he might have ONE kid.
  • Rebalance on the way up from the node you just deleted.



Balancing

  • Let d = difference in height between kids.

  • If (abs(d) < 2) return;

  • If (d < 0) // Heavy on the left

  • if (right->difference > 0) // kid heavy on right

  • right = right->rotate_right();

  • return rotate_left();

  • .... // same stuff other side

  • recompute my height

  • return



Computing the Height

  • Each node's height is just max(left->height, right->height) + 1;

  • This only changes along the path from insertion/deletion to the root.

  • The obvious recursive code searches the entire tree ... don't do that!



Yüklə 445 b.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2024
rəhbərliyinə müraciət

    Ana səhifə