Class PRedBlackSortedTree<E>

  extended by org.jcae.mesh.amibe.util.QSortedTree<E>
      extended by org.jcae.mesh.amibe.util.PRedBlackSortedTree<E>
All Implemented Interfaces:

public class PRedBlackSortedTree<E>
extends QSortedTree<E>

Red-black binary trees to store quality factors. Main ideas come from Ben Pfaff's GNU libavl. These trees are used to sort vertices, edges, or triangles according to their quality factors, and to process them in increasing or decreasing order after they have been sorted. See examples in algorithms from org.jcae.mesh.amibe.algos3d. A red-black tree has the following properties:

  1. Null nodes are black.
  2. A red node has no red child.
  3. Paths from any node to external leaves contain the same number of black nodes.
By convention, root node is always black in order to simplify node insertion and removal. Node insertions and removals are explained in detail at wikipedia.

See Also:
Serialized Form

Field Summary
Fields inherited from class org.jcae.mesh.amibe.util.QSortedTree
Constructor Summary
Method Summary
 boolean checkParentPointers()
 boolean debugIsValid()
 boolean insertNode(QSortedTree.Node<E> o)
          Insert a new note into the binary tree.
 QSortedTree.Node<E> newNode(E o, double v)
          Constructor to cast new nodes into subclass type.
 QSortedTree.Node<E> removeNode(QSortedTree.Node<E> o)
          Remove a note from the binary tree.
Methods inherited from class org.jcae.mesh.amibe.util.QSortedTree
backwardIterator, clear, contains, getRootValue, insert, isEmpty, iterator, readObject, remove, show, showValues, size, update
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail


public PRedBlackSortedTree()
Method Detail


public final QSortedTree.Node<E> newNode(E o,
                                         double v)
Description copied from class: QSortedTree
Constructor to cast new nodes into subclass type.

Specified by:
newNode in class QSortedTree<E>


public final boolean insertNode(QSortedTree.Node<E> o)
Description copied from class: QSortedTree
Insert a new note into the binary tree. This method always returns true.

Specified by:
insertNode in class QSortedTree<E>


public final QSortedTree.Node<E> removeNode(QSortedTree.Node<E> o)
Description copied from class: QSortedTree
Remove a note from the binary tree. Some algorithms may remove another node (for instance PRedBlackSortedTree), this method returns the node which has been removed.

Specified by:
removeNode in class QSortedTree<E>


public boolean checkParentPointers()


public boolean debugIsValid()