CS 225 Lecture Notes - Lecture 28: Avl Tree, If And Only If, Hard Disk Drive Performance Characteristics

• School: University of Illinois
• Department: Computer Science
• Course: CS 225
• Professor: Heeren Cinda

Document Summary

Avl balance is not based on the number of nodes, but the height of the left/right subtree. Avl trees are balanced trees where the height doesn"t differe by more than 1 with its neighbors. Since running times for insert, remove and find are o(h), we"ll argue that h = Defn of big-o: f(n) = o(g(n)) iff there exists constants c, k so that f(n) <= c*g(n), for all n > k. An upper bound on the height for a tree of n nodes is the same as a lower bound on the number of nodes in a tree of height h. Constant time is not possible for a tree, it"s log(n) Putting an upper bound on the tree of n nodes is the same as putting a lower bound on the number of nodes in a tree of height h. Define n(h): the least # of nodes in an avl tree of height h.