01:198:112 Lecture 12: 3/5 - BSTs and AVLs
1 Apr 2019
School
Department
Course
Professor
Document Summary
E. g. the value of the middle in the data set is the root node. E. g. the value of the first root node is either the smallest or biggest value in the data set. For each item of the array insert into the bst. Use in order traversal to sort back into array. E. g. go all the way left insert that node, then go back up one, insert that node, go right and repeat until you can"t go right anymore. The height of the left and right subtrees differ by at most one node. Left and right subtree same height - Left subtree is one node higher than the right subtree / Right subtree is one node higher than the left subtree \ Search until failure, insert at failure point. If node becomes unbalanced, then we rebalance node (called x) Identify the point of the highest subtree of x(call it r) X and r have the same bf(balance factor) orientation.
