Lecture Notes for SE 598, Data Structures and Algorithms

26 July 2000, Implementing Sets and Multisets

1. operations and behavior

   1. create and delete

   2. grow and shrink - insert and erase; sorted

   3. size - return the number of elements in a set

   4. read and write - limited capabilities

2. design

   1. use a vector

      1. create is fast and simple, delete is fast and simple

      2. grow and shrink - the trick is the ordering

         1. maintaining sorted order can be expensive - searching then shifting

         2. is linear search the most efficient way to search

            1. linear search thows away one thing at a time - reduction is slow

            2. what's the fastest possible guarenteed reduction - half at at time

            3. sorting helps - the midpoint divides the data in half

            4. binary search - one comparison can throw away half the data

               1. template <typename RandomIterator, typename T>
                  bool bsearch(RandomIterator l, RandomIterator r, T x) {
                    assert(l < r);
                    while (l + 1 < r) {
                      RandomIterator m = l + (r - l)/2;
                      if (*m <= x)
                        l = m;
                      else
                        r = m;
                      }
                    return *l == x;
                    }
                  

            5. insert() and erase() are reasonably simple and slow

            6. the set operations are essentially merges

   2. use a linked list

      1. linked lists are worse than vectors - no random access

      2. for a linked list of a given size, the mid-point is known

      3. this leads to a binary tree

         1. template <typename T>
            struct bt_node {
              list_element<T> * left, * right;
              T value;
              }
            

         2. root, leaf, parent, child, grandchild, grandparent, ancestors, decendents

      4. but, what about the ordering

         1. the values in a parent's left decendents are no more than the parent's value

         2. the values in a parent's right decendents are no less than the parent's value

         3. a binary search tree

      5. creating is fast and simple, deleting is slow and simple

      6. grow and shrink

         1. insert() and delete() are now fast, but are no longer simple

This page last modified on 25 July 2000.