path: root/set_treaps.c

/*
	Projet d'algorithmique et programmation 2013-2014
	(cours de C.Matthieu et J.Stern)
	Alex AUVOLAT, Mendes OULAMARA

	Implémentation des ensembles d'entiers sous la forme de tarbres.
	Non encore implémenté.
*/

#include "sets.h"

/*
	Étude de complexité :
	- Ajout d'un élément : O(log n)
	- Suppression d'un élément : O(log n)
	- Différence de deux ensembles : O(n)
	- Union de deux ensembles : O(n)
	- Intersection de deux ensembles : O(n)
	- Ensemble vide ? : O(1)
	- Copie d'un ensemble : O(n)
	- Suppression d'un ensemble : O(n)
	- Trouver un élément dans un ensemble non vide : O(1)

	Seul intérêt de cette implémentation utilisant des tarbres : manipuler
	des arbres en C, ce qui est autrement plus difficile à faire qu'en ML.
*/

/*
	TODO
*/