Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
tree balancing in Set and Map
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2006-10-22 (00:03)
From: David Monniaux <David.Monniaux@e...>
Subject: tree balancing in Set and Map
I wonder about something: the first balanced tree data structure 
described in algorithmics courses is generally the AVL tree, where the 
heights of the subtrees differ by at most 1. In Caml's implementation, 
they are allowed to differ by at most 2.

A quick analysis of the functions h1(n) and h2(n) governing the maximal 
height of a tree with n nodes with respectively maximal height 
differences of 1 and 2 shows that asymptotically h2(n) is about 1.25 
times h1(n).

Why this choice then? Was it easier to implement? Is there some hidden 
effect like rotations not being needed as often? How about some 
bibliographic references? :-)

(Yes, you may have guessed, I'm not an algorithmician.)