Timber Ho! : An Examination of the Properties of Special Balanced Search Trees
Date
2002
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Producer
Director
Performer
Choreographer
Costume Designer
Music
Videographer
Lighting Designer
Set Designer
Crew Member
Funder
Rehearsal Director
Concert Coordinator
Advisor
Moderator
Panelist
Alternative Title
Department
Haverford College. Department of Computer Science
Type
Thesis
Original Format
Running Time
File Format
Place of Publication
Date Span
Copyright Date
Award
Language
eng
Note
Table of Contents
Terms of Use
Rights Holder
Access Restrictions
Haverford users only
Terms of Use
Tripod URL
Identifier
Abstract
In Computer Science, we are always looking for ways to do things quickly and efficiently. A computer has the ability to solve problems quickly, but as the size of these problems becomes very large, we run the risk of wasting our available computational power on inefficient algorithms. This is especially important when considering data structures that potentially contain millions of bits of information. A binary search tree is a good implementation of such a data structure when considering fast search and insertion operations. With some conditions in place, these operations can be made to run in O(log n) time on a tree with n nodes. The most important condition is that the tree is balanced; without this condition a large tree could simply be a linked list and run in O(n) time, a significant slowdown. My thesis examines three binary (or near-binary) search trees with different properties that fulfill the balance condition. Search and insertion algorithms are given for each, along with analysis and correctness proofs. While these trees are not normally used in practical applications of computers, they demonstrate that the implementation of efficient algorithms and data structures is much more than a trivial matter.