The avl property For every node the left and right side differ in height by less than two
And the pain
you must suffer to learn them
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 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.
To Do Single Rotations
A Left Rotation via Pointers
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.
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
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.
if (this == NULL)
return new Node
if (inData < data)
left = left -> insert_node (inData);
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.
Remember, he might have ONE kid.
Rebalance on the way up from the node you just deleted.
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();
.... // same stuff other side
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!
Dostları ilə paylaş:
Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2023