GNU Info

(slib.info)Indexing Operations on Weight-Balanced Trees

---

Prev: Advanced Operations on Weight-Balanced Trees Up: Weight-Balanced Trees

---

Enter node , (file) or (file)node

Indexing Operations on Weight-Balanced Trees
--------------------------------------------

  Weight balanced trees support operations that view the tree as sorted
sequence of associations.  Elements of the sequence can be accessed by
position, and the position of an element in the sequence can be
determined, both in logarthmic time.

 - procedure+: wt-tree/index wt-tree index
 - procedure+: wt-tree/index-datum wt-tree index
 - procedure+: wt-tree/index-pair wt-tree index
     Returns the 0-based INDEXth association of WT-TREE in the sorted
     sequence under the tree's ordering relation on the keys.
     `wt-tree/index' returns the INDEXth key, `wt-tree/index-datum'
     returns the datum associated with the INDEXth key and
     `wt-tree/index-pair' returns a new pair `(KEY . DATUM)' which is
     the `cons' of the INDEXth key and its datum.  The average and
     worst-case times required by this operation are proportional to
     the logarithm of the number of associations in the tree.

     These operations signal an error if the tree is empty, if
     INDEX`<0', or if INDEX is greater than or equal to the number of
     associations in the tree.

     Indexing can be used to find the median and maximum keys in the
     tree as follows:

          median:   (wt-tree/index WT-TREE
                                   (quotient (wt-tree/size WT-TREE) 2))
          
          maximum:  (wt-tree/index WT-TREE
                                   (-1+ (wt-tree/size WT-TREE)))

 - procedure+: wt-tree/rank wt-tree key
     Determines the 0-based position of KEY in the sorted sequence of
     the keys under the tree's ordering relation, or `#f' if the tree
     has no association with for KEY.  This procedure returns either an
     exact non-negative integer or `#f'.  The average and worst-case
     times required by this operation are proportional to the logarithm
     of the number of associations in the tree.

 - procedure+: wt-tree/min wt-tree
 - procedure+: wt-tree/min-datum wt-tree
 - procedure+: wt-tree/min-pair wt-tree
     Returns the association of WT-TREE that has the least key under
     the tree's ordering relation.  `wt-tree/min' returns the least key,
     `wt-tree/min-datum' returns the datum associated with the least key
     and `wt-tree/min-pair' returns a new pair `(key . datum)' which is
     the `cons' of the minimum key and its datum.  The average and
     worst-case times required by this operation are proportional to the
     logarithm of the number of associations in the tree.

     These operations signal an error if the tree is empty.  They could
     be written
          (define (wt-tree/min tree)        (wt-tree/index tree 0))
          (define (wt-tree/min-datum tree)  (wt-tree/index-datum tree 0))
          (define (wt-tree/min-pair tree)   (wt-tree/index-pair tree 0))

 - procedure+: wt-tree/delete-min wt-tree
     Returns a new tree containing all of the associations in WT-TREE
     except the association with the least key under the WT-TREE's
     ordering relation.  An error is signalled if the tree is empty.
     The average and worst-case times required by this operation are
     proportional to the logarithm of the number of associations in the
     tree.  This operation is equivalent to

          (wt-tree/delete WT-TREE (wt-tree/min WT-TREE))

 - procedure+: wt-tree/delete-min! wt-tree
     Removes the association with the least key under the WT-TREE's
     ordering relation.  An error is signalled if the tree is empty.
     The average and worst-case times required by this operation are
     proportional to the logarithm of the number of associations in the
     tree.  This operation is equivalent to

          (wt-tree/delete! WT-TREE (wt-tree/min WT-TREE))