ECE250 Study Guide - Midterm Guide: Binary Search Tree, Avl Tree, Binary Tree

• School: University of Waterloo
• Department: Electrical and Computer Engineering
• Course: ECE250
• Professor: Douglas Harder

Document Summary

Balance is defined by comparing the height of the two sub-trees. A binary search tree is said to be avl balanced if the difference in the heights between the left and right sub- trees is at most 1, and both sub-tress are themselves avl trees. Height of an avl tree: any complete binary search tree is an avl tree, an upper bound on the number of nodes in an avl tree of height h and a perfect binary tree with 2h+1-1 nodes. Left f(h) be the fewest number of nodes in a tree of h. F(0) = 1, f(1) = 2, f(2) = 4. The worst case avl tree can be composed as follows: A worst case avl tree of height h 1 on one, and h 2 on the other. Combining together, we get f(h) = f(h-1) +1 + f(h-2) , where 1. 6180, the golden ratio.