AbstractPage methodsPage added by Emmanuel LécharnyfindPos() methodThis method is used to find the position of a key in the keys. If the key is found, we will return its position as a negative value. Otherwise, we will return the position of the key which is immediately above the key we are looking for, or the latest position in the page if the new key is higher than any existing keys. We try to make the minimal number of comparisons while searching for the key, as it's a costly operation. If we have a tree with 1 million of elements, and pages containing 16 elements, with pages 66% full, then we will have to go down 6 levels, with around 4 comparisons per page, so around 24 comparisons for each find. int findPos(K) Page.findPos(key) : (K) -> int if nbElems == 0 then return 0 min <- 0 max <- nbElems - 1 while max > min do middle <- ( max + min + 1) / 2 if key == keys[middle] then return - (middle + 1) if key > keys[middle] then min <- middle + 1 else max <- middle - 1 done if key < keys[max] then return min else if key == keys[max] then return - (max + 1) else return max + 1 There is a small improvement done in this algorithm : as we may find the keys before we have gone down to atomic elements, we can save some comparaison by excluding the element we just compared.
Change Notification Preferences
View Online
|
Add Comment
|
