ºÝºÝߣ

ºÝºÝߣShare a Scribd company logo

Avl handout

?
?
M
mrecedu

The document discusses AVL trees and provides examples of inserting nodes into an AVL tree. It shows how single and double rotations are used to rebalance the tree when inserts cause height imbalances. Single rotations involve rotating a node and its child, while double rotations rotate a node and its child and grandchild.

1 of 4
Downloaded 12 times
CS216 Fall 2001 AVL Trees Example Insert 3 Insert 2 Insert 1 (non-AVL) AVL 3 3 3 2 2 2 Single 1 3 rotation 1 Insert 4 Insert 5 (non-AVL) AVL 2 2 2 Single 1 4 3 1 3 1 rotation 3 5 4 4 5 Insert 6 (non-AVL) AVL Insert 7 (non-AVL) 4 4 2 Single 2 5 2 5 1 4 rotation 1 3 6 1 3 6 3 5 7 6 9/27/01 Page 1 of 4
CS216 Fall 2001 AVL Insert 16 Insert 15 (non-AVL) 4 4 4 Single rotation 2 6 2 6 2 6 1 3 5 7 1 3 5 7 1 3 5 7 16 16 15 Step 1: Rotate child and grandchild Step 2: Rotate node and new child (AVL) 4 4 Double 2 6 2 6 rotation 1 3 5 7 1 3 5 15 15 7 16 16 Insert 14 (non-AVL) Step 1: Rotate child and Step 2: Rotate node and grandchild new child (AVL) 4 4 4 Double rotation 2 7 2 6 2 6 1 3 6 15 1 3 5 15 1 3 5 7 16 7 16 15 5 14 14 14 16 9/27/01 Page 2 of 4
CS216 Fall 2001 AVL Tree No longer AVL, must rebalance Insert a node h h +1 h h +2 Two ways to expand subtree of height h+2: h h h h +1 h +1 h h +2 h +2 Apply a Single Rotation Apply a Double Rotation Note: the symmetrical case is handled identically (i.e. mirror image) 9/27/01 Page 3 of 4
CS216 Fall 2001 Single Rotation: B D Single rotation D B A E h h +1 C E A C h h +1 h h h +2 Double Rotation: B D F B F A Double rotation D h G A C E G h h h h -1 h C E OR h-1 h h h -1 OR h h OR h-1 h OR h h h +1 h +2 9/27/01 Page 4 of 4

More Related Content

Avl handout

  • 1. CS216 Fall 2001 AVL Trees Example Insert 3 Insert 2 Insert 1 (non-AVL) AVL 3 3 3 2 2 2 Single 1 3 rotation 1 Insert 4 Insert 5 (non-AVL) AVL 2 2 2 Single 1 4 3 1 3 1 rotation 3 5 4 4 5 Insert 6 (non-AVL) AVL Insert 7 (non-AVL) 4 4 2 Single 2 5 2 5 1 4 rotation 1 3 6 1 3 6 3 5 7 6 9/27/01 Page 1 of 4
  • 2. CS216 Fall 2001 AVL Insert 16 Insert 15 (non-AVL) 4 4 4 Single rotation 2 6 2 6 2 6 1 3 5 7 1 3 5 7 1 3 5 7 16 16 15 Step 1: Rotate child and grandchild Step 2: Rotate node and new child (AVL) 4 4 Double 2 6 2 6 rotation 1 3 5 7 1 3 5 15 15 7 16 16 Insert 14 (non-AVL) Step 1: Rotate child and Step 2: Rotate node and grandchild new child (AVL) 4 4 4 Double rotation 2 7 2 6 2 6 1 3 6 15 1 3 5 15 1 3 5 7 16 7 16 15 5 14 14 14 16 9/27/01 Page 2 of 4
  • 3. CS216 Fall 2001 AVL Tree No longer AVL, must rebalance Insert a node h h +1 h h +2 Two ways to expand subtree of height h+2: h h h h +1 h +1 h h +2 h +2 Apply a Single Rotation Apply a Double Rotation Note: the symmetrical case is handled identically (i.e. mirror image) 9/27/01 Page 3 of 4
  • 4. CS216 Fall 2001 Single Rotation: B D Single rotation D B A E h h +1 C E A C h h +1 h h h +2 Double Rotation: B D F B F A Double rotation D h G A C E G h h h h -1 h C E OR h-1 h h h -1 OR h h OR h-1 h OR h h h +1 h +2 9/27/01 Page 4 of 4