Week 8: trees, binary search trees, AVL
----------------------------------------------------------------------------

This week, we continued the introduction to trees began with Carlos last Friday. We presented the traditional vocabulary associated with trees: size, height (of a tree, of a node), depth (of a tree, of a node), root/internal nodes/external nodes (leaves), parents/children/siblings, paths, arity, width, etc. Students were given exercises to work on, and to turn in (as graded hoework assignment).

We discussed the representation of trees: array-based or linked-list-based. As far as general trees, we reviewed the classical transformation of general trees into binary trees, called first child/next sibling. Finding an algorithm for this transformation was also part of the homework assignment.

Then we focused on binary trees, and presented the binary search trees (BST): properties + how to build a BST. We discussed the complexity of the search in a BST, and concluded that it is not satisfactory in most cases. Hence we introduced AVL trees: properties + how to build/rebalance an AVL tree. Students were then asked about a good algorithm/structure to find easily the kth smallest element of a set of data (organized in a binary tree structure).