Honors Theses

Date of Award

2017

Document Type

Undergraduate Thesis

Department

Electrical Engineering

First Advisor

Matthew Morrison

Relational Format

Dissertation/Thesis

Abstract

Binary search trees are binary trees with an ordering mechanism that makes the time to search for any given item within the tree is greatly reduced compared to an unordered array of numbers. More specifically, a balanced binary search tree is faster at finding a specific item in the tree than an unbalanced tree. There are several algorithms that can automatically balance a binary search tree. Most of them do this through rotations directly in their respective insert functions. These algorithms are mostly implemented in software. This paper will present a hardware-based algorithm to balance binary search trees. This algorithm manipulates the ordering of a string representing a binary tree through swapping its elements in certain ways. It can then be used in software and hardware applications where sorting is used, such as in transducers, and priority queues are needed, such as in bandwidth management on transmission lines.

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.