Lecture 3 04

put this into a tree{4, 3, 2, 1, 5, 6, 7}

Spindliest tree \(\Theta (N)\) (Height \(N\) in worst case scenario) {1, 2, 3, 4, 5, 6} Bushiest tree \(\Omega (\log N)\) (Height 4 in best case scenario){4, 2, 6, 1, 3, 5, 7}

Splaying tree

              [4]
         [1 3]   [5 7]
           [2]   [6]

      [1]
       |
       |
       V
     [1 2]
       |
       |
       V
     [1 3]
      [2]
       |
       |
       V
     [1 3]
      [2] [4]
       |
       |
       V
     [1 3]
      [2] [4 5 6]
       |
       |
       V