Module treap
treap.lua, a simple treap data structure implemented in Lua.
Source on Github
Info:
- Copyright: 2017
- License: MIT
- Author: Roland Yonaba
Functions
| node (key[, priority]) | Creates a treap node. |
| find (root, key) | Finds a key in the treap |
| insert (root, key) | Inserts a key in the treap |
| delete (root, key) | Deletes a key in the treap |
| inorder (root, f[, ...]) | In-order traversal. |
| size (root) | Returns the treap size. |
Functions
- node (key[, priority])
-
Creates a treap node.
Parameters:
- key a key
- priority a numeric priority for the given key. Defaults to random value. (optional)
Returns:
-
a node
- find (root, key)
-
Finds a key in the treap
Parameters:
- root a root node in the treap
- key a key
Returns:
-
a node (or nil)
- insert (root, key)
-
Inserts a key in the treap
Parameters:
- root a root node in the treap
- key a key
Returns:
-
the root node
- delete (root, key)
-
Deletes a key in the treap
Parameters:
- root a root node in the treap
- key a key
Returns:
-
the root node
- inorder (root, f[, ...])
-
In-order traversal. It maps
f (node, …)on every node along the traversal.Parameters:
- root a root node in the treap
- f
a function, defined as
f (node, …) - ...
optional arguments to
f(optional)
- size (root)
-
Returns the treap size.
Parameters:
- root a root node in the treap