A Hardware Algorithm for Self-Balancing Binary Search Trees

Author

Joseph Deiermann, University of Mississippi. Sally McDonnell Barksdale Honors College

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.

Recommended Citation

Deiermann, Joseph, "A Hardware Algorithm for Self-Balancing Binary Search Trees" (2017). Honors Theses. 482.
https://egrove.olemiss.edu/hon_thesis/482

Accessibility Status

Searchable text