Source of 28.12.java

Structures and functions

  1: /** @author Frank M. Carrano, Timothy M. Henry
  2:     @version 5.0 */
  3: public T add(T newEntry)
  4: {
  5:    T result = null;

  7:    if (isEmpty())
  8:       setRootNode(new BinaryNode<>(newEntry));
  9:    else
 10:    {
 11:       BinaryNode<T> rootNode = getRootNode();
 12:       result = addEntry(rootNode, newEntry);
 13:       setRootNode(rebalance(rootNode));
 14:    } // end if

 16:    return result;
 17: } // end add

 19: private T addEntry(BinaryNode<T> rootNode, T newEntry)
 20: {
 21:    // Assertion: rootNode != null
 22:    T result = null;
 23:    int comparison = newEntry.compareTo(rootNode.getData());

 25:    if (comparison == 0)
 26:    {
 27:       result = rootNode.getData();
 28:       rootNode.setData(newEntry);
 29:    }
 30:    else if (comparison < 0)
 31:    {
 32:       if (rootNode.hasLeftChild())
 33:       {
 34:          BinaryNode<T> leftChild = rootNode.getLeftChild();
 35:          result = addEntry(leftChild, newEntry);
 36:          rootNode.setLeftChild(rebalance(leftChild));
 37:       }
 38:       else
 39:          rootNode.setLeftChild(new BinaryNode<>(newEntry));
 40:    }
 41:    else
 42:    {
 43:       // Assertion: comparison > 0

 45:       if (rootNode.hasRightChild())
 46:       {
 47:          BinaryNode<T> rightChild = rootNode.getRightChild();
 48:          result = addEntry(rightChild, newEntry);
 49:          rootNode.setRightChild(rebalance(rightChild));
 50:       }
 51:       else
 52:          rootNode.setRightChild(new BinaryNode<>(newEntry));
 53:    } // end if

 55:    return result;
 56: } // end addEntry