Tutoring Section 7: Balanced Search Trees

Balanced Search Trees

Now you are experts in Binary Search Trees, we are going to dive into making trees more efficient. The question here is on through what inventions we can create our tree balanced? How do we ensure that O(log(n)) runtime? Well, it’s possible to use Balanced Search Trees, specifically B-Trees such as 2-3-4 trees or 2-3 trees. These trees, while inserting items, will ensure that through a series of rearrangements a tree will remain balanced. B-Trees, however, are not the most efficient when you have to implement them. A bijection (correspondence) can be made from B-Trees to Red Black Trees. In class, we specifically focus on left leaning red black trees which can be mapped back and forth to 2-3 trees. LLRBs can be kept in correspondence through a series of rules and operations.


Walkthrough videos

Note: The tutoring worksheets are property of CS61B(L) and are solely intended for the purpose of personal use.