A Hardware Algorithm for Self-Balancing Binary Search Trees

Deiermann, Joseph (2017) A Hardware Algorithm for Self-Balancing Binary Search Trees. Undergraduate thesis, under the direction of Matthew Morrison from Electrical Engineering, University of Mississippi.


Download (1MB) | Preview


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.

Item Type: Thesis (Undergraduate)
Creators: Deiermann, Joseph
Student's Degree Program(s): B.S. in Electrical Engineering
Thesis Advisor: Matthew Morrison
Thesis Advisor's Department: Electrical Engineering
Institution: University of Mississippi
Subjects: T Technology > TK Electrical engineering. Electronics Nuclear engineering
Depositing User: Joseph Deiermann
Date Deposited: 07 Dec 2017 21:05
Last Modified: 07 Dec 2017 21:05
URI: http://thesis.honors.olemiss.edu/id/eprint/996

Actions (login required)

View Item View Item