Class Notes (808,126)
CSC263H1 (52)
Lecture 5

# Lecture 5 - Binary Search Tree.docx

4 Pages
78 Views

School
University of Toronto St. George
Department
Computer Science
Course
CSC263H1
Professor
Toniann Pitassi
Semester
Winter

Description
Dictionary OPS: - Insert - Ɵ (n) for BST -Delete -Search Data Structures: -Binary Search Trees(BST) -Balanced BSTs -2-3 Trees - Red-Black Trees and more Reminder: Height(v): length of longest path from v to a leaf of the tree Height(T): the height of the root of T Height(.) = 0 Height ( ) = -1 Balance Factor of node V: BF(v) = hR(height of right subtree)L- h (height of left subtree) AVL-TREE === BST such that: −1 0 ∀ nodes v, BF(v) = { +1 - An AVL tree of n nodes has height Ɵ (log n): close to[ ≤ 1.44l2g (n+2)] - Can do inserts, deletes, while maintaining their balance - elegant and simple a) Insert x into T as in any binary search tree. x is now a leaf b)Go up from x to the root and: - adjust the balance factor -rebalance if necessary Example: AVL = {1,3,7,12,14,17,19} Insert (T, 8) 12 -1 3+1 170 0 +1 0 0 1 7 14 19 0 8 Insert(T, 5) 12 -1 +1 0 3 17 0 0 0 0 1 7 14 19 5 8 0 Insert(T, 10) -1 12 3+2 17 0 10 7 +1
More Less

Related notes for CSC263H1

OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.