Week 10: BSTs
SLOs for Week 10
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.