CSC263H1 Lecture Notes - Lecture 5: Avl Tree, Longest Path Problem, Binary Search Tree
22 Apr 2014
School
Department
Course
Professor
Document Summary
Height(v): length of longest path from v to a leaf of the tree. Height(t): the height of the root of t. Bf(v) = hr((height of right subtree) - hl(height of left subtree) Avl-tree === bst such that: nodes v, bf(v) = An avl tree of n nodes has height (log n): close to[ 1. 44log2(n+2)] Can do inserts, deletes, while maintaining their balance. Elegant and simple: insert x into t as in any binary search tree. x is now a leaf b)go up from x to the root and: We do a left rotation since there is a bf of 2 on the node 3. After rotation: left subtree of 12: is rebalanced, satisfies the bst property c)its height is as before the insertion of 10. First do a right rotation on node 7. Then we can do a left rotation on node 3.
