NAME
Tree::Treap - randomized binary search trees via the treap structure
SYNOPSIS
use Tree::Treap;
my $T = Tree::Treap->new();DESCRIPTION
A treap is a randomized binary search tree which takes a standard binary search tree and assigns random priorities to each node as they are created/inserted. The inorder property of a binary tree is maintained on the node-keys, and the heap property is also maintained on the node-priorities. It is this second step that randomizes the tree. Tree + Heap = Treap.
The structure is relatively efficient in space and time --- the expected runtime of insertion and deletion is O(log n), with few rotations required.
PUBLIC METHODS
- new()
-
The constructor takes one optional argument to determine the ordering of keys in the tree. This argument can either one of four strings: "str", "rstr", "num", or "rnum" (string, reverse string, numeric, and reverse numeric respectively), or a reference to a custom comparison routine that returns -1,0,1 to determine the relative ordering of keys.
- insert($key, $value)
-
Inserts a node containing the key and value into the treap. The value may be any scalar value (string, number, reference). The key should of course be compatible with the comparison routine. If the key exists, its value is set to the new value.
- delete($key)
-
Deletes the node with the given key from the treap.
- exists($key)
-
Returns true if the key exists in the treap, false otherwise.
- get_val($key)
-
Returns the value for the given key, or undef if the key does not exists in the treap.
- keys()
-
Returns a list of all the keys in the treap (inorder)
- range_keys($lo_key, $hi_key2)
-
Returns the list of keys greater than or equal to $lo_key and less than or equal to $hi_key. If either argument is missing or undefined then the lowest or highest key in the hash is used.
- range_values($lo_key, $hi_key)
-
Returns the list of values corresponding the range of keys given (see range_keys() above).
- minimum()
-
Returns the lowest ordered key in the treap.
- maximum()
-
Returns the highest ordered key in the treap.
- successor($key)
-
Given a key it returns the next ordered key in the treap, or undef.
- predecessor($key)
-
Given a key it returns the previous ordered key in the treap, or undef.
TODO
Implement split() and join() methods. (partially done)
Replace some of the recursive methods with iterative versions.
Currently nodes do not store a reference to their parent node. Storing a weakened ref to a parent would allow efficient tree walking routines (via successor() and predecessor()) for use in scalar context, without any overhead dealing with circular references.
AUTHOR
Copyright 2002-2005 Andrew Johnson (ajohnson@cpan.org). This is free software released under the same terms as Perl itself.