Show simple item record

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%.
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
html.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%.


This item appears in the following Collection(s)

Show simple item record