ftreap

Order statistic tree based on Treap data structure and powerful Implicit Treap for interval operations. Compact ObjectPascal generic class TTreapNode and generic class TImplicitTreapNode. See Wiki for more info.

Motivation

Why another treap implementation? The story begins from the SPOJ problem ALLIN1. All accepted solutions was in C/C++ and one in D-DMD. I asked myself - why not Pascal? My first attempt was based on records (mode DELPHI) - time 2.28s. After reading Michalis Kamburelis excellent Modern Object Pascal Introduction for Programmers I started ftreap. So, here we are.

Benchmarks

Here some testing results on IDEONE.

| Method \ Number of keys | 100000 | 200000 | 400000 | 800000 | 1600000 | | ----------------------- | ------ | ------ | ------ | ------ | ------- | | Insert | 0.08s | 0.19s | 0.42s | 1.06s | 2.58s |

FTREAP vs FCL-STL gset.

Built With

• Lazarus - The professional Free Pascal RAD IDE.
• PasDoc - Documentation tool for ObjectPascal (Free Pascal, Lazarus, Delphi).

License

This project is licensed under the MIT License - see the LICENSE file for details.