Yliopiston etusivulle Suomeksi På svenska In English Helsingin yliopisto

Random Binary Search Tree with Equal Elements

Show full item record

Avaa tiedosto Vie RefWorksiin
Title: Random Binary Search Tree with Equal Elements
Author: Pasanen, Tomi
Belongs to series: Department of Computer Science Series of Publications C - C-2008-36
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.
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
URI: http://hdl.handle.net/10138/1155
Date: 2008-04-18

Files in this item

Files Description Size Format View/Open
C-2008-36.pdf 111.0Kb PDF View/Open
This item appears in the following Collection(s)

Show full item record

Search Helda

Advanced Search


My Account