2.50
Hdl Handle:
http://hdl.handle.net/10547/270916
Title:
Maintaining a random binary search tree dynamically
Authors:
Vinod, Prasad; Pushpa, Suri; Maple, Carsten
Abstract:
Binary tree is a graph, without cycle, that is frequently used in computer science for fast data access and retrieval. To ensure faster insertion and deletion, the tree height has to be kept to a minimum. A random tree starts losing its randomness after a series of insertions and deletions and, in the worst case, a tree with n nodes, could grow up to the height of n - 1. In this paper, we present modified insertion and deletion algorithms to maintain the tree in better shape dynamically. Without applying any complex rebalancing technique, or using considerable amount of space, both algorithms maintain the tree in such a way that even a series of insertions and asymmetric deletions do not cause the tree to grow beyond n/2. A comparative study of traditional and modified insert algorithms shows that for random input, the modified insert algorithm produces a tree with 20% to 30% reduction in height, forcing the average number of comparisons required for a successful search to go down by 15% to 20%.
Citation:
Vinod, P., Pushpa, S., and Maple, C. “Maintaining a Random Binary Search Tree Dynamically”, in 10th International Conference on Information Visualisation, London (IV06), UK; pp. 483-488
Publisher:
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
Issue Date:
2006
URI:
http://hdl.handle.net/10547/270916
DOI:
10.1109/IV.2006.72
Additional Links:
http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=1648303
Type:
Conference papers, meetings and proceedings
Language:
en
ISSN:
1550-6037
Appears in Collections:
Centre for Research in Distributed Technologies (CREDIT)

Full metadata record

DC FieldValue Language
dc.contributor.authorVinod, Prasaden_GB
dc.contributor.authorPushpa, Surien_GB
dc.contributor.authorMaple, Carstenen_GB
dc.date.accessioned2013-03-04T12:26:03Z-
dc.date.available2013-03-04T12:26:03Z-
dc.date.issued2006-
dc.identifier.citationVinod, P., Pushpa, S., and Maple, C. “Maintaining a Random Binary Search Tree Dynamically”, in 10th International Conference on Information Visualisation, London (IV06), UK; pp. 483-488en_GB
dc.identifier.issn1550-6037-
dc.identifier.doi10.1109/IV.2006.72-
dc.identifier.urihttp://hdl.handle.net/10547/270916-
dc.description.abstractBinary tree is a graph, without cycle, that is frequently used in computer science for fast data access and retrieval. To ensure faster insertion and deletion, the tree height has to be kept to a minimum. A random tree starts losing its randomness after a series of insertions and deletions and, in the worst case, a tree with n nodes, could grow up to the height of n - 1. In this paper, we present modified insertion and deletion algorithms to maintain the tree in better shape dynamically. Without applying any complex rebalancing technique, or using considerable amount of space, both algorithms maintain the tree in such a way that even a series of insertions and asymmetric deletions do not cause the tree to grow beyond n/2. A comparative study of traditional and modified insert algorithms shows that for random input, the modified insert algorithm produces a tree with 20% to 30% reduction in height, forcing the average number of comparisons required for a successful search to go down by 15% to 20%.en_GB
dc.language.isoenen
dc.publisherIEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INCen_GB
dc.relation.urlhttp://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=1648303en_GB
dc.subjectgraph theoryen_GB
dc.titleMaintaining a random binary search tree dynamicallyen
dc.typeConference papers, meetings and proceedingsen
All Items in UOBREP are protected by copyright, with all rights reserved, unless otherwise indicated.