org.jcae.mesh.amibe.util
Class PRedBlackSortedTree<E>

java.lang.Object
  org.jcae.mesh.amibe.util.QSortedTree<E>
      org.jcae.mesh.amibe.util.PRedBlackSortedTree<E>

All Implemented Interfaces:

java.io.Serializable

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

root

Constructor Summary

PRedBlackSortedTree()

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

PRedBlackSortedTree

public PRedBlackSortedTree()

Method Detail

newNode

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>

insertNode

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>

removeNode

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>

checkParentPointers

public boolean checkParentPointers()

debugIsValid

public boolean debugIsValid()