title: Data structure for set operations
body: <p>What data structure supports the following set operations efficiently both in time and space?</p>
  
  <ol>
  <li>union </li>
  <li>difference</li>
  <li>ismemberof </li>
  <li>add</li>
  <li>delete</li>
  </ol>
  
  <p>I can think of 3 different ways to do these operations, suppose that we have two sets, their sizes are both N:</p>
  
  <p><strong>Bit Array:</strong></p>
  
  <pre><code>1. O(N)  2.O(N)  3.O(1)  4.O(1)  5.O(1)
  </code></pre>
  
  <p><strong>HashTable:</strong></p>
  
  <pre><code>1. O(N)  2.O(N)  3.O(1)  4.O(1)  5.O(1)
  </code></pre>
  
  <p><strong>Ordered Tree</strong>:</p>
  
  <pre><code>1. O(NlogN)  2.O(NlogN)  3.O(logN)  4.O(logN)  5.O(logN)
  </code></pre>
  
  <p>Bit Array and HashTable are fast but they use too much memory, Ordered Tree is slow but consumes less memory. </p>
  
  <p>Please note: the set may contain other types except integer, such as float number or string</p>
  
  <p>What other data structures are both fast and general, and space efficient?</p>