Lab 12: Balanced Search Trees | CS 61BL Summer 2024
Each assignment will have an FAQ linked at the top. You can also access it by adding “/faq” to the end of the URL. The FAQ for Lab 12 is located here. As usual, pull the Lab 12 files from the skeleton and open them in in IntelliJ. In this lab, we will: Over the past few labs, we have analyzed the performance of algorithms for access and insertion into binary search trees. However, our analyses often made the assumption that the trees were balanced. Informally, a tree being “balanced” means that the paths from root to every leaf are all roughly the same length. Any algorithm that looks once at each level of the tree – such as searching for a value in a binary search tree – only looks at as many elements as the number of levels in the tree. As we discovered previously, the smallest number of levels we can have is logarithmic with respect to the number of nodes. Balanced trees keep our number of levels in this efficient number of levels and prevents the worst case scenarios where we have
Each assignment will have an FAQ linked at the top. You can also access it by adding “/faq” to the end of the URL. The FAQ for Lab 12 is located here. As usual, pull the Lab 12 files from the skeleton and open them in in IntelliJ. In this lab, we will: Over the past few labs, we have analyzed the performance of algorithms for access and insertion into binary search trees. However, our analyses often made the assumption that the trees were balanced. Informally, a tree being “balanced” means that the paths from root to every leaf are all roughly the same length. Any algorithm that looks once at
Explore this link on the map →