Teaching Self-Balancing Trees Using a Beauty Contest
Samah Senbel · 2019
Trees data structures and their performance is one of the main topics to teach in a data structures course. Appreciating the importance of tree structure and tree height in software performance is an important concept to teach. In this paper, a simple and amusing activity is presented. It demonstrates to students the importance of a well-balanced tree by comparing the height of a binary search tree to a balanced (AVL) tree build upon some personal data to find the "prettiest" tree (minimum height). The activity highlights the fact that, irrelevant of your data sequence, a balanced tree guarantees a height of O(log n) and everyone "wins" the beauty contest.