Award Date
1-1-2001
Degree Type
Thesis
Degree Name
Master of Science (MS)
Department
Computer Science
First Committee Member
Ajoy K. Datta
Number of Pages
30
Abstract
Binary search tree is one of the most studied data structures. The main application of the binary search tree is in implementing efficient search operations. A binary search tree is a special binary tree which satisfies the property that for every processor p in the binary tree, the values of all the keys in the left subtree of p are smaller than that of p, and the values of all the keys in the right subtree of p are larger than that of p; We present a self-stabilizing [Dij74] algorithm to maintain a binary search tree given a binary tree structure and a sequence of integers as input. This protocol uses neither the processors identifiers nor the size of the tree but assumes the existence of a distinguished processor (the root). The algorithm is self-stabilizing, meaning that starting from an arbitrary state, it is guaranteed to reach a legitimate state in a finite number of steps. The proposed algorithm assures that the set of integers eventually sent to the output environment is a permutation of the integers received from the input environment. The algorithm stabilizes in 0(hn) time units, where h and n represent the height and size, respectively, of the tree. The proposed algorithm is aimed at the hardwired binary tree structures where the topology of the trees cannot be adaptive to the change of the input values, but the input values are organized within a predefined environment.
Keywords
Algorithms; Binary; Maintenance; Search; Self; Stabilizing; Tree
Controlled Subject
Computer science
File Format
File Size
962.56 KB
Degree Grantor
University of Nevada, Las Vegas
Language
English
Permissions
If you are the rightful copyright holder of this dissertation or thesis and wish to have the full text removed from Digital Scholarship@UNLV, please submit a request to digitalscholarship@unlv.edu and include clear identification of the work, preferably with URL.
Repository Citation
Brigant, Sylvain Ronan, "Self-stabilizing binary search tree maintenance algorithm" (2001). UNLV Retrospective Theses & Dissertations. 1273.
http://dx.doi.org/10.25669/wmvu-j4t6
Rights
IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/
