Random Binary Search Tree with Equal Elements

Show simple item record

dc.contributor.author Pasanen, Tomi en
dc.date.accessioned 2008-04-18T10:19:09Z en
dc.date.accessioned 2009-06-17T13:51:24Z
dc.date.available 2008-04-18T10:19:09Z en
dc.date.available 2009-06-17T13:51:24Z
dc.date.issued 2008-04-18T10:19:09Z en
dc.identifier.uri http://hdl.handle.net/10138/1155
dc.description Computing Reviews (1998) Categories and Subject Descriptors: E.1 Data Structures — trees F.2.2 Analysis of Algorithms and Problem Complexity: Nonnumerical Algorithms and Problems — sorting and searching en
dc.description.abstract We consider random binary search trees when the input consists of a multiset, i.e. a set with multiple occurrences of equal elements, and prove that the randomized insertion and deletion algorithms produce random search trees regardless of multiplicities; even if all the elements are equal during the tree updates, a search tree will maintain its randomness. Thus, equal elements do not degenerate a random search tree and they need not to be handled in any special way. We consider also stability of a search tree with respect to its inorder traversal and prove that the algorithms used produce stable trees. This introduces an implicit indexing of equal elements giving another proof that multiplicities do not pose problems when maintaining random binary search trees. en
dc.language.iso en en
dc.relation.ispartofseries Department of Computer Science Series of Publications C en
dc.relation.ispartofseries C-2008-36 en
dc.subject Binary Search Tree en
dc.subject Equal Elements en
dc.subject Multiset en
dc.subject Monoset en
dc.title Random Binary Search Tree with Equal Elements en
dc.type Technical Report en
dc.identifier.laitoskoodi 523 fi
dc.creator.corporateName Tietojenkäsittelytieteen laitos fi
dc.creator.corporateName Department of Computer Science en
dc.creator.corporateName Datavetenskap, Institutionen för sv

Files in this item

Total number of downloads: Loading...

Files Size Format View
C-2008-36.pdf 108.4Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record