Lecture Preview: Balanced Binary Search Trees

(Suggested book reading: Programming Abstractions in C++, Chapter 16, sections 16.3 - 16.4)

Today we'll learn about several new varieties of trees. First, we'll talk about subspecies of BSTs in the category of balanced binary search trees. Trees that are balanced have a wide appearance and a similar amount of nodes on the left and right, as in the left diagram below. Unbalanced trees tend to be tall and long, with significantly more nodes on one side than the other, as in the right diagram below. Today we will talk about how some variations of trees add measures to ensure that they will always remain balanced.

balanced tree example

Then we'll look some trees that aren't binary search trees, and in some cases aren't even binary trees. One of these is the "prefix tree" or "trie". After tries, I'll introduce your next homework assignment, Huffman encoding trees, and give you a walkthrough of the algorithms you'll need to complete the assignment.

This document and its content are copyright © Marty Stepp, 2014. All rights reserved. Any redistribution, reproduction, transmission, or storage of part or all of the contents in any form is prohibited without the authors' expressed written permission.