A implementation of the Treap data structure in the Lua Programming language.

Download & Installation

Bash

git clone https://github.com/Yonaba/treap.lua

Archive

• zip: 0.1.0 (latest stable) | current | all
• tarball: 0.1.0 (latest stable) | current | all

LuaRocks

luarocks install treap

MoonRocks

moonrocks install treap

Usage

local treap = require "treap"

-- Creates a new treap and store key '0' inside
local root = treap.new(1)

-- Add new keys
root = treap.insert(root, 5)
root = treap.insert(root, 2)
root = treap.insert(root, 4)
root = treap.insert(root, 3)

-- Delete some keys
root = treap.delete(root, 2)
root = treap.delete(root, 3)

-- Search some keys
local node = treap.find(root, 2)
print(node) --> nil, since it was removed!

node = treap.find(root, 1)
print(node.key) --> 1

-- Add some new keys
root = treap.insert(root, 7)
root = treap.insert(root, 6)

-- Get the size
print(treap.size(root)) --> 5

-- Traverse the treap while printing keys
treap.inorder(root, function(node)
  print('Key: '..node.key)
end)
--> Key: 1
--> Key: 4
--> Key: 5
--> Key: 6
--> Key: 7

Documentation

• Available in HTML-format for download : see doc.
• Read it in your browser : see online documentation.

Specification

Spec tests have been included.
Run them using Telescope with the following command from the root folder:

tsc -f spec/*

License

This work is under MIT-LICENSE.
Copyright (c) 2017 Roland Yonaba.
See LICENSE.