Scribd
Upload
2K views22 pages

AVL Tree Construction and Examples

1) Inserting the elements 10, 20, 15, 25, 30, 16, 18, 19 builds a balanced AVL tree with 30 at the root 2) Deleting 30 causes the tree to become unbalanced 3) Rotations are performed to rebalance the tree, resulting in 20 becoming the new root

Uploaded by

Rahul Kumar
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2K views22 pages

AVL Tree Construction and Examples

1) Inserting the elements 10, 20, 15, 25, 30, 16, 18, 19 builds a balanced AVL tree with 30 at the root 2) Deleting 30 causes the tree to become unbalanced 3) Rotations are performed to rebalance the tree, resulting in 20 becoming the new root

Uploaded by

Rahul Kumar
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
  • AVL Tree Construction
  • In-Class Exercises
  • Question 2

AVL Tree Example:

• Insert 14, 17, 11, 7, 53, 4, 13 into an empty AVL tree

14

11 17

7 53

4
ΕΠΛ 231 – Δομές Δεδομένων και Αλγόριθμοι

Φροντιστήριο 7

1. Ξεκινώντας με ένα άδειο AVL-δένδρο να εφαρμόσετε διαδοχικά εισαγωγή των στοιχείων


2, 1, 4, 5, 9, 3, 6, 7, 16, 0 δείχνοντας το αποτέλεσμα της κάθε μιας από τις εισαγωγές.
AVL Tree Example:
• Insert 14, 17, 11, 7, 53, 4, 13 into an empty AVL tree

14

7 17

4 11 53

13
AVL Tree Example:
• Now insert 12

14

7 17

4 11 53

13

12
AVL Tree Example:
• Now insert 12

14

7 17

4 11 53

12

13
AVL Tree Example:
• Now the AVL tree is balanced.

14

7 17

4 12 53

11 13
AVL Tree Example:
• Now insert 8

14

7 17

4 12 53

11 13

8
AVL Tree Example:
• Now insert 8

14

7 17

4 11 53

8 12

13
AVL Tree Example:
• Now the AVL tree is balanced.

14

11 17

7 12 53

4 8 13
AVL Tree Example:
• Now remove 53

14

11 17

7 12 53

4 8 13
AVL Tree Example:
• Now remove 53, unbalanced

14

11 17

7 12

4 8 13
AVL Tree Example:
• Balanced! Remove 11

11

7 14

4 8 12 17

13
AVL Tree Example:
• Remove 11, replace it with the largest in its left branch

7 14

4 12 17

13
AVL Tree Example:
• Remove 8, unbalanced

4 14

12 17

13
AVL Tree Example:
• Remove 8, unbalanced

4 12

14

13 17
AVL Tree Example:
• Balanced!!

12

7 14

4 13 17
In Class Exercises
• Build an AVL tree with the following values:
15, 20, 24, 10, 13, 7, 30, 36, 25
15, 20, 24, 10, 13, 7, 30, 36, 25
20

15
15 24
20
10
24

13

20 20

13 24 15 24

10 15 13

10
15, 20, 24, 10, 13, 7, 30, 36, 25

20
13

13 24 10 20

10 15 7 15 24

7 30

13 36

10 20

7 15 30

24 36
15, 20, 24, 10, 13, 7, 30, 36, 25

13 13

10 20 10 20

7 15 30 7 15 24

24 36 30

25 13 25 36

10 24

7 20 30

15 25 36
Remove 24 and 20 from the AVL tree.

13 13

10 24 10 20

7 20 30 7 15 30

15 25 36 25 36

13 13

10 30 10 15

7 15 36 7 30

25 25 36
Question 2
(a) Insert the following sequence of elements into an AVL tree, starting with an empty
tree: 10, 20, 15, 25, 30, 16, 18, 19.
(b) Delete 30 in the AVL tree that you got.

Solution:
(a) Red dashed line signifies first part of double rotate action.

10 15
15
10

10 20 10 25
15
20
25 30
20
20
15 30
16

15 20 20

15 25 15 25
20
10

25 10 16 30 10 18 30
16

30 18 16 19

19

(b).

20
20 18
15 25
18 25
15 20
10 18 30 15 19 10 16 19 25

16 19
10 16

AVL Tree Example: • Insert 14, 17, 11, 7, 53, 4, 13 into an empty AVL tree 14 17 11 7 53 4
ΕΠΛ 231 – Δομές Δεδομένων και Αλγόριθμοι Φροντιστήριο 7 1. Ξεκινώντας με ένα άδειο AVL-δένδρο να εφαρμόσετε διαδοχι
AVL Tree Example: • Insert 14, 17, 11, 7, 53, 4, 13 into an empty AVL tree 14 17 7 4 53 11 13
AVL Tree Example: • Now insert 12 14 17 7 4 53 11 13 12
AVL Tree Example: • Now insert 12 14 17 7 4 53 11 12 13
AVL Tree Example: • Now the AVL tree is balanced. 14 17 7 4 53 12 13 11
AVL Tree Example: • Now insert 8 14 17 7 4 53 12 13 11 8
AVL Tree Example: • Now insert 8 14 17 7 4 53 11 12 8 13
AVL Tree Example: • Now the AVL tree is balanced. 14 17 7 4 53 11 12 8 13
AVL Tree Example: • Now remove 53 14 17 7 4 53 11 12 8 13

You might also like