triceratops

Timber Ho! : An Examination of the Properties of Special Balanced Search Trees

TriCollege Digital Repository

Title: Timber Ho! : An Examination of the Properties of Special Balanced Search Trees
Author: Barkan, David
Advisor: Wonnacott, David G.
Department: Haverford College. Dept. of Computer Science
Type: Thesis (B.S.)
Running Time: 161065 bytes
Issue Date: 2002
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.
Subject: Data structures (Computer science)
Subject: Recursive functions
Terms of Use: http://creativecommons.org/licenses/by-nc/3.0/us/
Permanent URL: http://hdl.handle.net/10066/1466

Files in this item

Files Description Size Format
2002BarkanD.pdf Thesis (Haverford users only) 157.2Kb PDF
Haverford_departmental_permission.pdf **Archive Staff Only** 30.60Kb PDF

Citation

Barkan, David. "Timber Ho! : An Examination of the Properties of Special Balanced Search Trees". 2002. Available electronically from http://hdl.handle.net/10066/1466.

This item appears in the following Collection(s)

http://creativecommons.org/licenses/by-nc/3.0/us/ Except where otherwise noted, this item's license is described as http://creativecommons.org/licenses/by-nc/3.0/us/

Search


Advanced Search

Browse

My Account