## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

#include #include #include #include "TreapNode.h" #include "TreapSkeleton.h" int main() { std::srand(42); // initialize rand Treap t; for (int i=0; i<10; ++i) { t.insert(i); assert (t.is_valid()); std::cout << t << std::endl; } std::cout << "The height of the tree is " << t.height() << std::endl; std::cout << "The size of the tree is " << t.size() << std::endl; for (int i=0; i<10; ++i) { t.remove(i); assert (t.is_valid()); std::cout << t << std::endl; } } // g++ -Wall -pedantic-errors TreapNode.cpp TreapSkeleton.cpp treapSkeletonTest.cpp -o treapSkeletonTest // Expected to provide this output: // 0 // 0 1 // 0 1 2 // 0 1 2 3 // 0 1 2 3 4 // 0 1 2 3 4 5 // 0 1 2 3 4 5 6 // 0 1 2 3 4 5 6 7 // 0 1 2 3 4 5 6 7 8 // 0 1 2 3 4 5 6 7 8 9 // The height of the tree is 3 // The size of the tree is 10 // 1 2 3 4 5 6 7 8 9 // 2 3 4 5 6 7 8 9 // 3 4 5 6 7 8 9 // 4 5 6 7 8 9 // 5 6 7 8 9 // 6 7 8 9 // 7 8 9 // 8 9 // 9 //