SLOs for Week 11: BSTs¶
At the end of this unit, students will be able to...
articulate the operations one can do on a Binary Search Tree.
understand the implementation of a BST and the algorithms for
insert,contains(),remove(),getHeight(), the destructor, and the various traversals.reason about the complexity of operations on a BST -- for best and worst cases.
describe the algorithm for finding the maximum node in a left subtree and minimum node in a right subtree, for use during the
remove()algorithm.define what makes a BST balanced.
AVL trees:
identify an AVL tree as a self-balancing tree.
articulate the importance of the balance factor in determining when the tree needs to be rebalanced.
compute the balance factor for a node.