COMPSCI 61B Lecture Notes - Lecture 22: Consistency, Linear Search, Self-Balancing Binary Search Tree
1 Jun 2017
School
Department
Course
Professor
Document Summary
Optional spoiler videos/slides if you want a faster route to success. Saturday 12-2 pm in the second oor labs of soda. Bsts have potential performance issue if they get spindly . Fundamental issue: too lazy about where to store data. We don"t always know what all the elements are at the start. This is a logically consistent but very weird data structure contains(r): Too many elements stu ed in one node that we still require a linear search. If more than cap, give an item to the parent. Meaning of < [o q] is not clear. Set a cap on the number of items, say 3. If more than cap, give an item to parent. Pulling item out of juicy node splits into left and right (node splitting) Logically consistent and not so weird data structure contains(r): r > m, so go right r > o, so compare vs. q r > q, so go right.
