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
map implementation question
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2006-08-04 (20:08)
From: Brian Hurt <bhurt@j...>
Subject: map implementation question
I was just looking at the implementation, and noticed that the 
logic for when to do a rotation was:

>       if hl > hr + 2 then begin

Isn't this supposed to be:

    if hl >= hr + 2 then begin

?  The latter will cause more rotations, but keep the tree more 
balanced.  The worst-case access of the >= version is log base 3/2, 
while the > is log base 4/3, which means that the >= will be about 41% 
(log(3/2)/log(4/3) ~ 1.41).  Both are correct in that they return the 
right answer and are still O(log(N)) performance, it's a question of 
performance of looking up an element in the tree vr.s the cost of 
inserting an element into the tree.

Was there a reason it was done this way, or is this a (minor) bug?