Overview
This week we鈥檒l introduce some interesting and useful trees:
- binary search trees,
- AVL trees,
- splay trees, and
- B-trees.
Binary search trees allow us to find values stored within a tree structure. However, given certain values and orders of operations, binary search trees can develop an undesirable, unbalanced structure. AVL trees and splay trees are designed as a remedy. These are self-balancing binary trees, though they accomplish the goal of self-balancing by different means. B-tree is a design that is useful when we want a broad, shallow tree. This comes in handy when we鈥檙e storing data on disk and each operation is expensive.
Learning Objectives
By the end of this module, you will be able to:
- explain what it means for a tree to be balanced or unbalanced, what that means in terms of search performance,
- understand how self-balancing works in the context of AVL and splay trees,
- understand how shallow tree structures like B-tree, improve performance when we need to make access to slower media such as disk.
To achieve this module鈥檚 objectives, complete the following:
Read: Essential Algorithms: Chapter 11 - Balanced Trees.
Read / view the following content and complete any comprehension checks:
- Binary search trees
- AVL trees
- Splay trees
- B-trees
Project
TODO
Copyright 漏 2023鈥�2025 Clayton Cafiero
No generative AI was used in producing this material. This was written the old-fashioned way.