English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
RE: [Caml-list] Efficient and canonical set representation?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2003-11-12 (16:17)
From: Diego Olivier Fernandez Pons <Diego.FERNANDEZ_PONS@e...>
Subject: RE: [Caml-list] Efficient and canonical set representation?

> Is it just a coincidence that the numerous varieties of balanced
> tree (AVL, 2-3-4, red-black, ...) all seem to be non-canonical? Or
> is it essential to their efficiency? (Perhaps this is a question for
> another forum.)

It is not a coincidence. I remember having read somewhere that it
could be proven that if a balanced tree (based on comparisons) did not
have enough different representations of a same set, then the
insertion could not be done in logarithmic time.

        Diego Olivier

To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners