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

Yüklə 445 b.
ölçüsü445 b.

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


  • 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

  • All the rotations in pictures and text

  • Sample single and double rotations

The AVL Insertion Algorithm

  • An Intuitive description can be found at

The AVL Game

  • Play the game

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.


  • 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 © 2023
rəhbərliyinə müraciət

    Ana səhifə