AVL Tree Data Structure with Insertion, Deletion, Rotations, Balancing Techniques, and Applications in C

Balanced Binaries – AVL Trees

Balanced Binaries – AVL Trees Height of a tree node: 1. The height of a node with no elements is 0 2. The height of a node with 1 element is 1 3. The height of a node with > 1 element is 1 + the height of its tallest subtree

Balanced Binaries – AVL Trees Height of a tree node: 1. The height of a node with no elements is 0 2. The height of a node with 1 element is 1 3. The height of a node with > 1 element is 1 + the height of its tallest subtree AVL tree: A binary tree in which the difference between the height of the right and left subtrees of the root is never more than one.

Balanced Binaries – AVL Trees Height of a tree node: 1. The height of a node with no elements is 0 2. The height of a node with 1 element is 1 3. The height of a node with > 1 element is 1 + the height of its tallest subtree AVL tree: A binary tree in which the difference between the height of the right and left subtrees of the root is never more than one. Each node keeps a balance number which is the difference in heights of its two subtrees. For example, 2 0 -2 1 0 Whenever a balance number is not 0,-1,+1, perform some rotations according to some rules on following pages

Balanced Binaries – AVL Trees Rules for rotation: If: 2 a 1 b c 0 c 0 b a 2 a 0 b c -1 c 1 b a Plus mirror image of these two cases

Balanced Binaries – AVL Trees Rules for rotation: If: 2 a -1 1 d c b 0 -1 0 c d b a 2 a -1 0 d c b 0 0 0 c d b a

Balanced Binaries – AVL Trees Rules for rotation: If: 2 a -1 -1 d c b 0 0 1 c d b a Plus mirror image of these three cases

Balanced Binaries – AVL Trees Example: 46 21 32 49 58 7 -1 37 12 18 28 40 51 61 -1 -1 0 55 0 0 14 0 0 10 1 19 1 4

Balanced Binaries – AVL Trees Example: 21 32 49 58 7 -1 37 12 18 28 40 51 61 -1 -1 0 55 0 0 14 0 0 10 46 Insert 2 1 19 0 4 2 changes

Balanced Binaries – AVL Trees Example: 21 32 49 58 7 -1 37 12 18 28 40 51 61 -1 -1 0 55 0 0 14 0 0 10 46 Insert 11 1 19 1 4 11 changes -1

Balanced Binaries – AVL Trees Example: Insert 9 46 21 32 49 58 7 -1 37 12 18 28 40 51 61 -1 -1 0 55 0 0 14 0 -1 10 0 19 9 2 4 1

Balanced Binaries – AVL Trees Example: Insert 9 46 21 32 49 58 4 -1 37 12 18 28 40 51 61 -1 -1 0 55 0 0 14 0 0 10 1 19 9 0 7 0 Rotation around 7

Balanced Binaries – AVL Trees Example: Insert 6 46 21 32 49 58 7 -1 37 12 18 28 40 51 61 -1 -1 0 55 0 0 14 0 -1 10 0 19 2 4 6 -1

Balanced Binaries – AVL Trees Example: Insert 6 46 7 0 55 0 0 14 -1 37 12 18 28 40 51 61 0 -1 -1 21 32 49 58 -1 10 0 19 2 4 6 1 Double rotation

Balanced Binaries – AVL Trees Example: Insert 6 46 4 7 0 55 0 0 14 -1 37 12 18 28 40 51 61 0 -1 -1 21 32 49 58 0 10 1 19 0 6 0 Double rotation

Balanced Binaries – AVL Trees 21 32 49 58 7 -1 37 12 18 28 40 51 61 -1 -2 1 55 1 0 14 0 0 10 46 Example: Insert 56 2 19 1 4 56 -1

Balanced Binaries – AVL Trees 61 7 -1 37 12 18 28 40 51 58 -1 0 0 55 0 0 14 0 0 10 46 Example: Insert 56 1 19 1 4 21 32 49 56 Single rotation around 58

Balanced Binaries – AVL Trees Example: 46 21 32 49 58 7 -1 37 12 18 28 40 51 61 -1 -1 0 55 0 0 14 0 10 1 19 1 4 0

Balanced Binaries – AVL Trees 21 32 49 58 7 -2 37 12 18 28 40 51 61 -1 -1 0 55 -1 0 14 -1 0 10 46 Example: Insert 20 2 19 1 4 20 -1

Balanced Binaries – AVL Trees 49 58 21 32 7 -2 37 12 18 28 40 51 61 -1 -1 0 55 -1 0 14 -1 0 10 46 Example: Insert 20 2 19 1 4 20 -1 Rotate around 28

Balanced Binaries – AVL Trees 37 12 18 49 58 32 40 7 51 61 -1 -1 0 55 0 0 0 14 28 0 10 46 Example: Insert 20 1 19 1 4 20 -1 21 Rotate around 28 0

Balanced Binaries – AVL Trees 21 32 49 58 7 -2 37 12 18 28 40 51 61 -1 -1 0 55 -1 0 14 0 10 46 Example: Insert 23 2 19 1 4 -1 23 1

Balanced Binaries – AVL Trees 49 58 21 32 7 -2 37 12 18 28 40 51 61 -1 -1 0 55 -1 0 14 0 10 46 Example: Insert 23 2 19 1 4 -1 1 23 Rotation around 28

Balanced Binaries – AVL Trees 37 28 40 12 18 49 58 32 7 0 51 61 -1 -1 0 55 0 0 10 46 Example: Insert 23 1 19 1 4 0 0 14 23 1 21 Rotation around 28

Balanced Binaries – AVL Trees 7 -2 37 12 18 28 40 51 61 -1 -1 0 55 -1 0 14 0 10 46 Example: Insert 34 2 19 1 4 1 21 32 49 58 1 34

Balanced Binaries – AVL Trees 49 58 7 -2 37 12 18 28 40 51 61 -1 -1 0 55 -1 0 14 0 10 46 Example: Insert 34 2 19 1 4 1 21 32 1 34 Double rotation around 32

Balanced Binaries – AVL Trees 55 40 14 12 18 49 58 4 7 -2 37 51 61 -1 -1 0 -1 0 0 10 46 Example: Insert 34 2 19 1 -1 28 34 -1 32 21 Double rotation around 32

Balanced Binaries – AVL Trees 55 37 40 14 49 58 21 4 7 0 51 61 -1 -1 0 0 0 0 10 46 Example: Insert 34 1 19 1 -1 12 18 28 34 0 32 Double rotation around 32

Balanced Binaries – AVL Trees 21 32 49 58 7 -1 37 12 18 28 40 51 61 -1 -1 0 55 0 0 14 0 10 46 Example: Delete 18 1 19 1 4 0

Balanced Binaries – AVL Trees 21 32 49 58 7 -1 37 28 40 51 61 -1 -1 0 55 0 -1 14 12 0 10 46 Example: Delete 18 1 19 1 4 0 No change

Balanced Binaries – AVL Trees 21 32 49 7 -1 37 12 18 28 40 51 61 -1 -1 55 0 0 14 0 10 46 Example: Delete 58 1 19 1 4 0 No change

Balanced Binaries – AVL Trees 32 49 58 7 -1 37 12 18 28 40 51 61 -1 -1 0 55 0 0 14 0 10 46 Example: Delete 19 1 21 1 4 1

Balanced Binaries – AVL Trees 32 49 58 7 -1 37 12 18 28 40 51 61 -1 -1 0 55 0 0 14 0 10 46 Example: Delete 21 1 21 1 4 1

Balanced Binaries – AVL Trees 49 58 7 0 37 12 18 32 40 51 61 -1 -1 0 55 1 0 14 0 10 46 Example: Delete 21 1 28 1 4 No change

Balanced Binaries – AVL Trees 49 58 7 0 37 12 18 32 40 51 61 -1 -1 0 55 1 0 14 0 10 46 Example: Delete 28 1 28 1 4

Balanced Binaries – AVL Trees 12 18 49 58 7 1 37 40 51 61 -1 -1 0 55 1 0 14 0 10 46 Example: Delete 28 1 32 1 4 No change

Balanced Binaries – AVL Trees 12 18 49 58 7 1 37 40 51 61 -1 -1 0 55 1 0 14 0 10 46 Example: Delete 32 1 32 1 4

Balanced Binaries – AVL Trees 40 12 18 49 58 7 51 61 -1 -1 0 55 2 0 14 0 10 46 Example: Delete 32 1 37 1 4 Rotation around 55

Balanced Binaries – AVL Trees 55 40 14 12 18 49 58 4 7 51 -1 61 -1 -1 1 46 0 0 10 Example: Delete 32 1 37 1 Rotation around 55

AVL Tree Data Structure with Insertion, Deletion, Rotations, Balancing Techniques, and Applications in C

More Related Content

Similar to AVL Tree Data Structure with Insertion, Deletion, Rotations, Balancing Techniques, and Applications in C

More from usham61

Recently uploaded

AVL Tree Data Structure with Insertion, Deletion, Rotations, Balancing Techniques, and Applications in C