Date of Award
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.
Deiermann, Joseph, "A Hardware Algorithm for Self-Balancing Binary Search Trees" (2017). Honors Theses. 482.