Árboles Binarios de Búsqueda en Java

22 11 2007

En estos días he tenido la necesidad de ver ciertas operaciones que se implementan el los árboles binarios de búsqueda (Binary Search Trees), y en este sitio encontré una implementación particularmente interesante, espero que les sea de utilidad.

En ciencias de la computación, un árbol binario de búsqueda es un árbol que tiene las siguientes propiedades:

  • Cada nodo tiene un valor
  • Se define un orden total sobre esos valores
  • El subárbol izquierdo de un nodo contiene valores menores o iguales que el valor de dicho nodo.
  • El subárbol derecho de un nodo contiene valores mayores o iguales que el valor de dicho nodo.

La ventaja más notable de los árboles binarios de búsqueda es que los algoritmos de ordenación y búsqueda relacionados como transversal inorden pueden ser muy eficientes.

Los árboles binarios de búsqueda son una estructura de datos fundamental usada para construir más estructuras de datos abstractas como conjuntos y arrays asociativos.
// BinarySearchTree class
//
// CONSTRUCTION: with no initializer
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// void remove( x ) --> Remove x
// void removeMin( ) --> Remove minimum item
// Comparable find( x ) --> Return item that matches x
// Comparable findMin( ) --> Return smallest item
// Comparable findMax( ) --> Return largest item
// boolean isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// ******************ERRORS********************************
// Exceptions are thrown by insert, remove, and removeMin if warranted

/**
* Implements an unbalanced binary search tree.
* Note that all “matching” is based on the compareTo method.
* @author Mark Allen Weiss
*/


public class BinarySearchTree {
/**
* Construct the tree.
*/
public BinarySearchTree( ) {
root = null;
}

/**
* Insert into the tree.
* @param x the item to insert.
* @throws DuplicateItemException if x is already present.
*/
public void insert( Comparable x ) {
root = insert( x, root );
}

/**
* Remove from the tree..
* @param x the item to remove.
* @throws ItemNotFoundException if x is not found.
*/
public void remove( Comparable x ) {
root = remove( x, root );
}

/**
* Remove minimum item from the tree.
* @throws ItemNotFoundException if tree is empty.
*/
public void removeMin( ) {
root = removeMin( root );
}

/**
* Find the smallest item in the tree.
* @return smallest item or null if empty.
*/
public Comparable findMin( ) {
return elementAt( findMin( root ) );
}

/**
* Find the largest item in the tree.
* @return the largest item or null if empty.
*/

public Comparable findMax( ) {
return elementAt( findMax( root ) );
}

/**
* Find an item in the tree.
* @param x the item to search for.
* @return the matching item or null if not found.
*/
public Comparable find( Comparable x ) {
return elementAt( find( x, root ) );
}

/**
* Make the tree logically empty.
*/
public void makeEmpty( ) {
root = null;
}

/**
* Test if the tree is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( ) {
return root == null;
}

/**
* Internal method to get element field.
* @param t the node.
* @return the element field or null if t is null.
*/
private Comparable elementAt( BinaryNode t ) {
return t == null ? null : t.element;
}

/**
* Internal method to insert into a subtree.
* @param x the item to insert.
* @param t the node that roots the tree.
* @return the new root.
* @throws DuplicateItemException if x is already present.
*/
protected BinaryNode insert( Comparable x, BinaryNode t ) {
if( t == null )
t = new BinaryNode( x );
else if( x.compareTo( t.element ) < 0 )
t.left = insert( x, t.left );
else if( x.compareTo( t.element ) > 0 )
t.right = insert( x, t.right );
else
throw new DuplicateItemException( x.toString( ) ); // Duplicate
return t;
}

/**
* Internal method to remove from a subtree.
* @param x the item to remove.
* @param t the node that roots the tree.
* @return the new root.
* @throws ItemNotFoundException if x is not found.
*/
protected BinaryNode remove( Comparable x, BinaryNode t ) {
if( t == null )
throw new ItemNotFoundException( x.toString( ) );
if( x.compareTo( t.element ) < 0 )
t.left = remove( x, t.left );
else if( x.compareTo( t.element ) > 0 )
t.right = remove( x, t.right );
else if( t.left != null && t.right != null ) // Two children
{
t.element = findMin( t.right ).element;
t.right = removeMin( t.right );
} else
t = ( t.left != null ) ? t.left : t.right;
return t;
}

/**
* Internal method to remove minimum item from a subtree.
* @param t the node that roots the tree.
*@return the new root.
* @throws ItemNotFoundException if x is not found.
*/
protected BinaryNode removeMin( BinaryNode t ) {
if( t == null )
throw new ItemNotFoundException( );
else if( t.left != null ) {
t.left = removeMin( t.left );
return t;
} else
return t.right;
}

/**
* Internal method to find the smallest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the smallest item.
*/
protected BinaryNode findMin( BinaryNode t ) {
if( t != null )
while( t.left != null )
t = t.left;

return t;
}

/**
* Internal method to find the largest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the largest item.
*/
private BinaryNode findMax( BinaryNode t ) {
if( t != null )
while( t.right != null )
t = t.right;

return t;
}

/**
* Internal method to find an item in a subtree.
* @param x is item to search for.
* @param t the node that roots the tree.
* @return node containing the matched item.
*/
private BinaryNode find( Comparable x, BinaryNode t ) {
while( t != null ) {
if( x.compareTo( t.element ) < 0 )
t = t.left;
else if( x.compareTo( t.element ) > 0 )
t = t.right;
else
return t; // Match
}

return null; // Not found
}

/** The tree root. */
protected BinaryNode root;

// Test program
public static void main( String [ ] args ) {
BinarySearchTree t = new BinarySearchTree( );
final int NUMS = 4000;
final int GAP = 37;

System.out.println( “Checking… (no more output means success)” );

for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
t.insert( new Integer( i ) );

for( int i = 1; i < NUMS; i+= 2 )
t.remove( new Integer( i ) );

if( ((Integer)(t.findMin( ))).intValue( ) != 2 ||
((Integer)(t.findMax( ))).intValue( ) != NUMS – 2 )
System.out.println( “FindMin or FindMax error!” );

for( int i = 2; i < NUMS; i+=2 )
if( ((Integer)(t.find( new Integer( i ) ))).intValue( ) != i )
System.out.println( “Find error1!” );

for( int i = 1; i < NUMS; i+=2 ) {
if( t.find( new Integer( i ) ) != null )
System.out.println( “Find error2!” );
}
}
}

// Basic node stored in unbalanced binary search trees
// Note that this class is not accessible outside
// of this package.

class BinaryNode {
// Constructors
BinaryNode( Comparable theElement ) {
element = theElement;
left = right = null;
}

// Friendly data; accessible by other package routines
Comparable element; // The data in the node
BinaryNode left; // Left child
BinaryNode right; // Right child
}

/**
* Exception class for duplicate item errors
* in search tree insertions.
* @author Mark Allen Weiss
*/
public class DuplicateItemException extends RuntimeException {
/**
* Construct this exception object.
*/
public DuplicateItemException( ) {
super( );
}
/**
* Construct this exception object.
* @param message the error message.
*/
public DuplicateItemException( String message ) {
super( message );
}
}

/**
* Exception class for failed finds/removes in search
* trees, hash tables, and list and tree iterators.
* @author Mark Allen Weiss
*/
public class ItemNotFoundException extends RuntimeException {
/**
* Construct this exception object.
*/
public ItemNotFoundException( ) {
super( );
}

/**
* Construct this exception object.
* @param message the error message.
*/
public ItemNotFoundException( String message ) {
super( message );
}
}

Fuente: Java-Tips.org, http://www.java-tips.org/java-se-tips/java.lang/binary-search-tree-implementation-in-java.htm

About these ads

Acciones

Información

2 respuestas

25 11 2007
juan ramón

me parecio interesante los árboles bonarios de busqueda en java ya les dare un buen uso para resolver algun ejercicio de inteligencia atificial

7 09 2008
Juan Pablo Rodriguez

me parece que es un muy buen ejemplo de como se pueden trabajar los arboles en java en este momento me encuentro de desarrollando una aplicacion con arboles pero tengo unas pequenas variaciones ya tengo una interface que declara los comportamientos basicos
aqui los pongo para si alguien le sirve

public interface ADTBinaryTree {

public enum relatives{LEFT,RIGHT};

/**
* retorna el dato del tipo E contenido en la raiz de este arbol
* @return E referencia al dato de tipo E contenido en la raiz
*/
public E get();
/**
* remplaza el valor de tipo E en la raiz
* @param e referencia al nuevo valor que tomara
*/
public void set(E e);

/**
* verifica la existencia de un subarbol izquierdo o derecho
* @param r Enumeracion del identificador del hijo derecho o izquierdo
* @return boolean true si este arbol tiene un subArbol, false en caso contrario
*/
public boolean hasRelative(ADTBinaryTree.relatives r);

/**
* retorna el subArbol izquierdo o derecho
* @param r enumeracion identificadora del hijo a obtener
* @return ADTTree contenido la referencia al subArbol derecho o izquierdo
* @throws NullPointerException cuando this.hasRelative retorna false
*/
public ADTBinaryTree getRelative(ADTBinaryTree.relatives r)throws NullPointerException;

/**
* remplaza el valor actual del subArbol derecho o izquierdo pore el valor que hay en b
* @param b arbol que se convertira en el subArbol izquierdo
* @param r enumeracion identificadora del hijo a remplazar
*/
public void setRelative(ADTBinaryTree b,ADTBinaryTree.relatives r);

/**
* elimina el hijo izquierdo o derecho segun represente r
* @param r enumeracion identificadora del hijo a eliminar
* @throws NullPointerException si el hijo a eliminar no existe
*/
public void clearRelatives(ADTBinaryTree.relatives r)throws NullPointerException;

}

****** y aqui tengo la implementacion

public class BinaryTree implements ADTBinaryTree {

E root;
ADTBinaryTree left;
ADTBinaryTree rigth;
@Override
public void clearRelatives(relatives r) throws NullPointerException {
if(r.equals(relatives.LEFT))
this.left = null;
else
if(r.equals(relatives.RIGHT))
this.rigth = null;
else
throw new NullPointerException();
}

@Override
public E get() {
return this.root;
}

@Override

public ADTBinaryTree getRelative(relatives r)throws NullPointerException{

if(this.root.equals(null))
throw new NullPointerException();

if(r.equals(relatives.LEFT))
return this.left;

return this.rigth;
}

@Override
public boolean hasRelative(relatives r) {
if(r.equals(relatives.RIGHT) && this.rigth.get()!= null)
return true;
if(r.equals(relatives.LEFT) && this.left.get()!= null)
return true;

return false;
}

@Override
public void set(E e) {
this.root = e;

}

@Override
public void setRelative(ADTBinaryTree b, relatives r) {
if(r.equals(relatives.RIGHT))
this.rigth.set(b.get());
if(r.equals(relatives.LEFT))
this.left.set(b.get());
}
}

Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s




Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

%d personas les gusta esto: