Master of Science (MS)
First Committee Member
Ajoy K. Datta
Number of Pages
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.
Algorithms; Binary; Maintenance; Search; Self; Stabilizing; Tree
University of Nevada, Las Vegas
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 firstname.lastname@example.org and include clear identification of the work, preferably with URL.
Brigant, Sylvain Ronan, "Self-stabilizing binary search tree maintenance algorithm" (2001). UNLV Retrospective Theses & Dissertations. 1273.