CS210 · Annotated SlidesTrees — AVL Trees
Trees · Annotated slides

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.

Slide text Study notes Highlight: key words Tips, tricks & traps Seen again elsewhere How it can come up
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
Exam weight Low
    Slide 2: to k
    Exam weight High
    1. AVL property: for every node, the heights of its two children differ by at most 1.
    🎯 How this can come up · 1 question
    MCQ

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

    Slide 3: Slide 3
    Exam weight Low
      Slide 4: Slide 4
      Exam weight Low
        Slide 5: the ofthe
        Exam weight Low
        1. Height of an AVL tree with n nodes is O(log n).
        Slide 6: Beastcasueoctogn
        Exam weight Low
          Slide 7: Slide 7
          Exam weight Low
            Slide 8: Slide 8
            Exam weight Low
              Slide 9: Trinode Restructuring
              Exam weight Low
              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: Insertion Example, continued
              Exam weight Low
                Slide 11: Restructuring (as Single Rotations)
                Exam weight Low
                1. Single rotation when x, y, z are in a straight line (LL or RR).
                Slide 12: Slide 12
                Exam weight Low
                  Slide 13: Slide 13
                  Exam weight Low
                    Slide 14: Slide 14
                    Exam weight Low
                      Slide 15: Restructuring (as Double Rotations)
                      Exam weight High
                      1. Double rotation when they zig-zag (LR or RL).
                      🎯 How this can come up · 1 question
                      MCQ

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

                      Slide 16: Slide 16
                      Exam weight Low
                        Slide 17: Removal
                        Exam weight Low
                          Slide 18: Slide 18
                          Exam weight Low
                            Slide 19: Slide 19
                            Exam weight Low
                              Slide 20: Rebalancing after a Removal
                              Exam weight Low
                                Slide 21: AVL Tree Performance
                                Exam weight High
                                1. Search, insert and remove are all O(log n) in an AVL tree.
                                🎯 How this can come up · 1 question
                                MCQ

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

                                Slide 22: Java Implementation
                                Exam weight Low
                                  Slide 23: Java Implementation, 2
                                  Exam weight Low
                                    Slide 24: Java Implementation, 3
                                    Exam weight Low
                                      Slide 25: Slide 25
                                      Exam weight Low
                                        Slide 26: Slide 26
                                        Exam weight Low
                                          Slide 27: Slide 27
                                          Exam weight Low