Computer Science › Section I · Data abstractions › Topic I.4
A short case study: a binary tree
Suppose a program must keep names in alphabetical order, find any of them fast, and accept new ones at any time. Storing the list as a binary search tree does all three with three short recursive functions, and shows a data structure being built as a complete abstract tool.
In this topic
- The job: a list kept in order
- Turning a sorted list into a tree
- Worked example: building the tree
- Searching the tree
- Worked example: two searches
- Printing in alphabetical order
- Worked example: tracing PrintTree
- Inserting a new entry
- Worked example: inserting K
- When a tree loses its shape
- Common mistakes to avoid
- Key takeaways
This topic is part of Wuanberri Pro. Checking your access…