Search Trees
Overview
Finite sets and mappings are basic abstract data types with many applications. If the elements of a set, or the keys in a mapping, belong to an ordered set, then additional useful operations can be provided, so that finite ordered sets and dictionaries (ordered mappings) are also heavily used.
Binary trees are extremely useful data structures. If the elements of an ordered set or of a dictionary are stored at nodes, with various ordering properties satisfied,then the resulting binary search trees provide extremely useful implementations.
While binary search trees have very good performance in practice, the worst case running times of operations are not as good. “Height balanced” binary search trees are somewhat more complicated data structures with operations whose worst case performance is within a linear factor of the “expected” performance of the corresponding operations on a regular binary search tree. A red-black tree is one kind of height balanced search tree.
Regular binary search trees and red-black trees will be presented, and their properties will be studied.
Lecture #8: Binary Trees and Binary Search Trees — Definitions and Searches
Required Reading
Lecture Presentation
Code Supplied with This Lecture
- Set.java (Interface for Finite Set) [ Source ] [ Documentation ]
- OrderedSet.java (Interface for Finite Set from an Ordered Universe) [ Source ] [ Documentation ]
- Mapping.java (Interface for Finite Partial Function) [ Source ] [ Documentation ]
- Dictionary.java (Interface for Finite Partial Function with Ordered Domain) [ Source ] [ Documentation ]
- ElementFoundException.java (Exception Used by the Above) [ Source ] [ Documentation [
Additional Material That May Be of Interest
Lecture #9: Binary Trees and Binary Search Trees — Additional Operations
Required Reading
Lecture Presentation
Code Supplied with This Lecture
- BSTDictionary.java (Implemention of Dictionary with BST) [ Source ] [ Documentation ]
- TestBSTDictionary.jva (Tests for This Implementation) [ Source ]
Additional Material That May Be of Interest
Reading Exercise #2: Properties of Randomly Constructed Binary Search Trees
Tutorial #9: Binary Search Trees
Lecture #10: Red-Black Trees — Part One
Required Reading
- Lecture Notes [ PDF ] [ Video ]
- Supplemental Material: Proof that Red-Black Trees are Height-Balanced
Lecture Presentation
Lecture #11: Red-Black Trees — Part Two
Required Reading
Lecture Presentation
Tutorial #10: Red-Black Trees
Tutorial #11: Augmenting Binary Search Trees and Red-Black Trees
Assignment #2: AVL Trees
-
Problems To Be Solved
- Code To Be Used When Completing This Assignment:
- Mapping.java: Interface for a “Mapping” (Not To Be Changed)
- Dictionary.java: Interface for a “Dictionary” (Not To Be Changed)
-
AVLDictionary.java:
Implementation of a “Dictionary”
using an AVL Tree (To Be Completed)
- Code for Testing:
-
Information about Software for Testing
- AVLUtilities.java: Utilities to be used when designing tests for AVL trees
-
RSeq.java:
Generates (pseudo-)random sequences of integers
- AVLTest1.java: First set of tests
- AVLTest2.java: Second set of tests
- AVLTest3.java: Third set of tests
- AVLTest4.java: Fourth set of tests
- AVLTest5.java: Fifth set of tests
- AVLTest6.java: Sixth set of tests
-
Information about Software for Testing
