TreeMap / TreeSet

From CS315

Contrary to their name, TreeMap and TreeSet have nothing to in common with the representation of trees. Instead, TreeMap/TreeSet is a collection of nodes, or otherwise known as Entrys that store elements by the ordering of their keys in a parent-child relationship. Part of the Collection class, the TreeMap and TreeSet class keeps the elements within them in order at all times, if not, then it has no right to be called a TreeMap/TreeSet. In addition, TreeMap/TreeSet are kept in order by the natural order of the key, so the key has to be comparable. If the key is not comparable, there will need to be a comparator.

What is a TreeMap?

A Red/Black Tree is used to implement the TreeMap class. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used. K represents the type of key that is maintained, and V represents the type of the mapped value.

The ordering maintained by a sorted map (whether or not an explicit comparator is provided) must be consistent with equals if this sorted map is to correctly implement the Map interface. (See Comparable or Comparator for a precise definition of consistent with equals.) This is so because the Map interface is defined in terms of the equals operation, but a map performs all key comparisons using its compareTo (or compare) method, so two keys that are deemed equal by this method are, from the standpoint of the sorted map, equal. The behavior of a sorted map is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Map interface[1].

What is a TreeSet?

Based of the implementation of a TreeMap, a TreeSet's elements are kept in order by using it's key's natural ordering, or by a comparator if provided. With TreeSet, the key must be embedded in the object that is stored in the collection as the set only passes one parameter E, the type of element maintained by this set.

The ordering that is maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the Set interface. This is so because the Set interface is defined in terms of the equals operation, but a TreeSet instance performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the set, equal. The behavior of a set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface[2].

Tree Terminology

Root 

A special Entry. :]

By the key's natural ordering or a comparator, every Entry to the left is smaller than the root and every Entry to the right is greater than the root.

Parent 

Every Entry different from the root Entry and is not a leaf.

The parent of an Entry is the Entry linked above it.

Child 

Any Entry that the parent points to.

If it is a binary tree, usually there is a Left Child (smaller than the parent) and a Right Child (greater than the parent), if there are any at all.

Sibling 

Usually considered this if two Entrys have the same parent.

Leaf 

An Entry that has no child.

Depth of an Entry 

The number of Entrys between or in the path of the root and the Entry.

Height of a tree 

The maximum depth of a leaf Entry.

Different Types of Trees

Binary Tree

A Binary Tree is where the parent can only have two children. It considered a Complete Binary Tree, if every non-leaf Entry in the tree has exactly two children.
If a Complete Binary Tree has n elements, that also means that half of it's Entrys are Leaves.

Red/Black Tree

Created by Rudolf Bayer in 1972, Red/Black Trees are self-balancing binary search trees that are used in the implementation of the TreeMap class. Each Entry has a color attribute to it that is either red or black. In order to be considered a Red/Black Tree, these rules are applied:

• A node is either red or black.
• The root is black.
• All leaves are black, even when the parent is black (The leaves are the null children.)
• Both children of every red node are black.
• Every simple path from a node to a descendant leaf contains the same number of black nodes, either counting or not counting the null black nodes. (Counting or not counting the null black nodes does not affect the structure as long as the choice is used consistently.)[3].

Operations

TreeMap

containsKey(Key)

 // Guaranteed O(logN) in time
  Using the Binary Search Method, find an entry that is equal to Key.
  {
      if there is one, return true.
      else you haven't looked hard enough, keep trying
  }
  in the end, if Key isn't found, return false.

 // O(N) in time (have to look at every node)
  Go through every single Entry asking the question "Are you the Value I'm looking for?"
  {
      if it says yes, return true.
      else keep looking.
  }
  when all of them rejected you, return a sad false. :[

 // Guaranteed O(logN) in time
  Using the Binary Search Method, find an entry that is equal to Key.
  {  
      if there is one, return true.
      else keep searching.
  }
  and when all else fails, return false.

 // Guaranteed O(logN) in time
  find out which k is smaller, the Current's Key or the Key in the parameter using the comparator given.
  if the Parameter's Key is the smaller of the two {
      if the left node is null {
          add a new Entry with the key, value into this spot.
          return null;
      }
      else recurse through the TreeMap until you find a spot.
  }
  if the Current's Key is the smaller than the two {
      if the right node is null {
          add a new Entry with the key, value into this spot.
          return null;
      }
      else recurse through the TreeMap until you find a spot. 
   }
  if all else fails, that means there's a duplicate key, so set the Parameter's value to that spot.

 // Guaranteed O(logN) in time
  Much like containsKey, put, and get, use the Binary Search method trying to find the key.
  {
     if you found it, remove the Entry, and return true.
     else keep looking.
  }
  in the end, if nothing was removed, return false.

In addition, since TreeMap uses Red/Black Trees, if anything was added or taken away, the Map itself will need to be altered to fit the rules.
For a list of additional methods, check out Sun's TreeMap.

TreeSet

add(Key)

  // Guaranteed O(logN) in time
   Use TreeMap's put(Key, Value) to add Key with value having no particular significance.

  // Guaranteed O(logN) in time
   Use TreeMap's remove(Key) to remove the Key.

  // Guaranteed O(logN) in time
   Use TreeMap's containsKey(Key) to see if this key is in the Set or not.

For a list of additional methods, check out Sun's TreeSet.

Pros and Cons

Pros:

• Basic Operations guarantee a Big-Oh of log(n) in time cost.
  • TreeMap: containsKey, get, put, remove
  • TreeSet: add, remove, contains
• Items are already sorted, so no costly O(n²) sorting algorithms are needed.

• If the height of the tree is large, it can be very space inefficient. (it's just another linked list, minus certain useful methods).
• If the key is mutable, then there is a possibility of the key being messed with.

In Conclusion...

The main difference of TreeMap and TreeSet, is that TreeSet holds no additional value. Therefore, TreeSet's key must act as the value as well as the key, if it were to have any significance. If the Key were to be changed, in TreeMap, the value in turn is out of place, in TreeSet, the key is out of place. In both cases, the Entry is not where it supposedly is supposed to be. Seeing as how the key keeps the order of the elements, it is suggested to create an instance of a TreeMap/TreeSet, where the key is immutable and there are no worries of someone messing with the key. Otherwise,

"Mess with the key, lose the tree."

References

[1] http://java.sun.com/javase/6/docs/api/java/util/TreeMap.html
[2] http://java.sun.com/javase/6/docs/api/java/util/TreeSet.html
[3] http://en.wikipedia.org/wiki/Red_black_tree
[4] http://www.cs.utexas.edu/users/downing/examples/TreeMap.java
[5] http://www.cs.utexas.edu/users/downing/examples/TreeSet.java