CS210 · Trees · Annotated SlidesAVL Trees
Original
Overview

AVL Trees

The AVL height-balance property, why it keeps height O(log n), insertion with trinode restructuring (single and double rotations), removal, and performance.

How to read this page

Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.

All 27 slides
  1. 1 Presentation for use with the textbook Data Structures and Algorithms in Java, 6 th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014
  2. 2 to k
  3. 3 Slide 3
  4. 4 Slide 4
  5. 5 the ofthe
  6. 6 Beastcasueoctogn
  7. 7 Iiii
  8. 8 Slide 8
  9. 9 Trinode Restructuring
  10. 10 Insertion Example, continued
  11. 11 Restructuring (as Single Rotations)
  12. 12 Slide 12
  13. 13 some 2
  14. 14 www.n.si
  15. 15 Restructuring (as Double Rotations)
  16. 16 Slide 16
  17. 17 Removal
  18. 18 504 3
  19. 19 Slide 19
  20. 20 Rebalancing after a Removal
  21. 21 AVL Tree Performance
  22. 22 Java Implementation
  23. 23 Java Implementation, 2
  24. 24 Java Implementation, 3
  25. 25 Slide 25
  26. 26 Slide 26
  27. 27 aol.w.im oxides
Slide 1 / 27

Presentation for use with the textbook Data Structures and Algorithms in Java, 6 th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014

Slide 1: Presentation for use with the textbook Data Structures and Algorithms in Java, 6 th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014
Slide 2 / 27

to k

Slide 2: to k

Exam angle

PredictionQ1

An AVL tree requires that for every node, the children’s heights differ by at most:

Slide 3 / 27

Slide 3

Slide 3: Slide 3
Slide 4 / 27

Slide 4

Slide 4: Slide 4
Slide 5 / 27

the ofthe

Slide 5: the ofthe
Slide 6 / 27

Beastcasueoctogn

Slide 6: Beastcasueoctogn
Slide 7 / 27

Iiii

Slide 7: Iiii
Slide 8 / 27

Slide 8

Slide 8: Slide 8
Slide 9 / 27

Trinode Restructuring

Slide 9: Trinode Restructuring

Notes

  1. Trinode restructuring: take the unbalanced node z, its taller child y and grandchild x; make the middle one the root of the subtree.

Slide 10 / 27

Insertion Example, continued

Slide 10: Insertion Example, continued
Slide 11 / 27

Restructuring (as Single Rotations)

Slide 11: Restructuring (as Single Rotations)

Notes

  1. Single rotation when x, y, z are in a straight line (LL or RR).

Slide 12 / 27

Slide 12

Slide 12: Slide 12
Slide 13 / 27

some 2

Slide 13: some 2
Slide 14 / 27

www.n.si

Slide 14: www.n.si
Slide 15 / 27

Restructuring (as Double Rotations)

Slide 15: Restructuring (as Double Rotations)

Notes

  1. Double rotation when they zig-zag (LR or RL).

Exam angle

PredictionQ1

An imbalance caused by inserting into the right subtree of a node’s left child needs a:

Slide 16 / 27

Slide 16

Slide 16: Slide 16
Slide 17 / 27

Removal

Slide 17: Removal
Slide 18 / 27

504 3

Slide 18: 504 3
Slide 19 / 27

Slide 19

Slide 19: Slide 19
Slide 20 / 27

Rebalancing after a Removal

Slide 20: Rebalancing after a Removal
Slide 21 / 27

AVL Tree Performance

Slide 21: AVL Tree Performance

Exam angle

PredictionQ1

Worst-case search in an AVL tree with n nodes:

Slide 22 / 27

Java Implementation

Slide 22: Java Implementation
Slide 23 / 27

Java Implementation, 2

Slide 23: Java Implementation, 2
Slide 24 / 27

Java Implementation, 3

Slide 24: Java Implementation, 3
Slide 25 / 27

Slide 25

Slide 25: Slide 25
Slide 26 / 27

Slide 26

Slide 26: Slide 26
Slide 27 / 27

aol.w.im oxides

Slide 27: aol.w.im oxides