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.
Resources
Walkthrough videos