Algorithm
Development Kit 1.0

algs.model.problems.segmentIntersection
Class AugmentedBalancedTree<K>

java.lang.Object
  extended by algs.model.tree.BalancedTree<K,K>
      extended by algs.model.problems.segmentIntersection.AugmentedBalancedTree<K>
Type Parameters:
K - The key to be used for the nodes in the tree. Note that both the key and the value of the nodes will be of type K for simplicity

public class AugmentedBalancedTree<K>
extends BalancedTree<K,K>

The Balanced Binary Tree for this algorithm required internal nodes to store (min, max) links to the leaf nodes, where actual segments are to be stored.

Since:
1.0
Version:
1.0, 6/15/08
Author:
George Heineman

Field Summary
 
Fields inherited from class algs.model.tree.BalancedTree
allowDuplicates, comparator, root, size
 
Constructor Summary
AugmentedBalancedTree()
          Constructs an empty Balanced Tree.
AugmentedBalancedTree(java.util.Comparator<? super K> c)
          Constructs a new, empty tree sorted according to the given comparator.
 
Method Summary
protected  AugmentedNode<K> construct(K key, K value, AugmentedNode<K> parent)
          Construct a node in the tree.
protected  void deleteEntry(BalancedBinaryNode<K,K> p)
          Because we are using leaf nodes only to store the segments, we can be guaranteed that the node p is going to be a leaf node.
protected  void fixAfterInsertion(BalancedBinaryNode<K,K> p)
          From CLR
 AugmentedNode<K> getEntry(K key)
          Overrides locate by using interior nodes as guides.
 K insert(K key)
          Must make sure that interior nodes contain no segments; rather, only the leaves do.
 K remove(K key)
          Overrides deletion by finding the leaf node for this key.
 AugmentedNode<K> root()
          Helps with type casting
protected  void rotateLeft(BalancedBinaryNode<K,K> p)
          From CLR
protected  void rotateRight(BalancedBinaryNode<K,K> p)
          From CLR
 
Methods inherited from class algs.model.tree.BalancedTree
accept, allowDuplicates, clear, comparator, compare, construct, firstNode, getPrecedingEntry, getSuccessorEntry, insert, iterator, lastNode, minimum, pred, search, setAllowDuplicates, size, successor, toString
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

AugmentedBalancedTree

public AugmentedBalancedTree()
Constructs an empty Balanced Tree.


AugmentedBalancedTree

public AugmentedBalancedTree(java.util.Comparator<? super K> c)
Constructs a new, empty tree sorted according to the given comparator.

Parameters:
c - the comparator that will be used to sort this map. A null value indicates that the keys' natural ordering should be used.
Method Detail

root

public AugmentedNode<K> root()
Helps with type casting

Overrides:
root in class BalancedTree<K,K>

construct

protected AugmentedNode<K> construct(K key,
                                     K value,
                                     AugmentedNode<K> parent)
Construct a node in the tree. Subclass extensions of BalancedTree must override this method to insert the appropriate node of the appropriate subclass.

Parameters:
key -
value -
parent -

getEntry

public AugmentedNode<K> getEntry(K key)
Overrides locate by using interior nodes as guides.

Overrides:
getEntry in class BalancedTree<K,K>
Returns:
this map's entry for the given key, or null if the map does not contain an entry for the key.

remove

public K remove(K key)
Overrides deletion by finding the leaf node for this key.

Overrides:
remove in class BalancedTree<K,K>
Parameters:
key - key for which mapping should be removed
Returns:
previous value associated with specified key, or null if there was no mapping for key. A null return can also indicate that the map previously associated null with the specified key.

insert

public K insert(K key)
Must make sure that interior nodes contain no segments; rather, only the leaves do. Thus we completely override insert.


deleteEntry

protected void deleteEntry(BalancedBinaryNode<K,K> p)
Because we are using leaf nodes only to store the segments, we can be guaranteed that the node p is going to be a leaf node. If this is not the case, then we will encounter problems, naturally! We can casually throw away interior nodes of the tree, since they don't actually store anything, right?

Overrides:
deleteEntry in class BalancedTree<K,K>

fixAfterInsertion

protected void fixAfterInsertion(BalancedBinaryNode<K,K> p)
Description copied from class: BalancedTree
From CLR

Overrides:
fixAfterInsertion in class BalancedTree<K,K>

rotateLeft

protected void rotateLeft(BalancedBinaryNode<K,K> p)
Description copied from class: BalancedTree
From CLR

Overrides:
rotateLeft in class BalancedTree<K,K>

rotateRight

protected void rotateRight(BalancedBinaryNode<K,K> p)
Description copied from class: BalancedTree
From CLR

Overrides:
rotateRight in class BalancedTree<K,K>

Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.