Package mx.unam.ciencias.edd

Class ArbolBinarioOrdenado<T extends Comparable<T>>

java.lang.Object
mx.unam.ciencias.edd.ArbolBinario<T>
mx.unam.ciencias.edd.ArbolBinarioOrdenado<T>
All Implemented Interfaces:
Iterable<T>, Coleccion<T>
public class ArbolBinarioOrdenado<T extends Comparable<T>> extends ArbolBinario<T>

Clase para árboles binarios ordenados. Los árboles son genéricos, pero acotados a la interfaz Comparable.

Un árbol instancia de esta clase siempre cumple que:

  • Cualquier elemento en el árbol es mayor o igual que todos sus descendientes por la izquierda.
  • Cualquier elemento en el árbol es menor o igual que todos sus descendientes por la derecha.

  • Field Details

    • ultimoAgregado

      protected ArbolBinario<T extends Comparable<T>>.Vertice ultimoAgregado
      El vértice del último elemento agegado. Este vértice sólo se puede garantizar que existe inmediatamente después de haber agregado un elemento al árbol. Si cualquier operación distinta a agregar sobre el árbol se ejecuta después de haber agregado un elemento, el estado de esta variable es indefinido.

  • Constructor Details

    • ArbolBinarioOrdenado

      public ArbolBinarioOrdenado()
      Constructor sin parámetros. Para no perder el constructor sin parámetros de ArbolBinario.

    • ArbolBinarioOrdenado

      public ArbolBinarioOrdenado(Coleccion<T> coleccion)
      Construye un árbol binario ordenado a partir de una colección. El árbol binario ordenado tiene los mismos elementos que la colección recibida.
      Parameters:
      coleccion - la colección a partir de la cual creamos el árbol binario ordenado.

  • Method Details

    • agrega

      public void agrega(T elemento)
      Agrega un nuevo elemento al árbol. El árbol conserva su orden in-order.
      Parameters:
      elemento - el elemento a agregar.

    • elimina

      public void elimina(T elemento)
      Elimina un elemento. Si el elemento no está en el árbol, no hace nada; si está varias veces, elimina el primero que encuentre (in-order). El árbol conserva su orden in-order.
      Parameters:
      elemento - el elemento a eliminar.

    • intercambiaEliminable

      protected ArbolBinario<T>.Vertice intercambiaEliminable(ArbolBinario<T>.Vertice vertice)
      Intercambia el elemento de un vértice con dos hijos distintos de null con el elemento de un descendiente que tenga a lo más un hijo.
      Parameters:
      vertice - un vértice con dos hijos distintos de null.
      Returns:
      el vértice descendiente con el que vértice recibido se intercambió. El vértice regresado tiene a lo más un hijo distinto de null.

    • eliminaVertice

      protected void eliminaVertice(ArbolBinario<T>.Vertice vertice)
      Elimina un vértice que a lo más tiene un hijo distinto de null subiendo ese hijo (si existe).
      Parameters:
      vertice - el vértice a eliminar; debe tener a lo más un hijo distinto de null.

    • busca

      public VerticeArbolBinario<T> busca(T elemento)
      Busca un elemento en el árbol recorriéndolo in-order. Si lo encuentra, regresa el vértice que lo contiene; si no, regresa null.
      Overrides:
      busca in class ArbolBinario<T extends Comparable<T>>
      Parameters:
      elemento - el elemento a buscar.
      Returns:
      un vértice que contiene al elemento buscado si lo encuentra; null en otro caso.

    • getUltimoVerticeAgregado

      public VerticeArbolBinario<T> getUltimoVerticeAgregado()
      Regresa el vértice que contiene el último elemento agregado al árbol. Este método sólo se puede garantizar que funcione inmediatamente después de haber invocado al método agrega(T). Si cualquier operación distinta a agregar sobre el árbol se ejecuta después de haber agregado un elemento, el comportamiento de este método es indefinido.
      Returns:
      el vértice que contiene el último elemento agregado al árbol, si el método es invocado inmediatamente después de agregar un elemento al árbol.

    • giraDerecha

      public void giraDerecha(VerticeArbolBinario<T> vertice)
      Gira el árbol a la derecha sobre el vértice recibido. Si el vértice no tiene hijo izquierdo, el método no hace nada.
      Parameters:
      vertice - el vértice sobre el que vamos a girar.

    • giraIzquierda

      public void giraIzquierda(VerticeArbolBinario<T> vertice)
      Gira el árbol a la izquierda sobre el vértice recibido. Si el vértice no tiene hijo derecho, el método no hace nada.
      Parameters:
      vertice - el vértice sobre el que vamos a girar.

    • dfsPreOrder

      public void dfsPreOrder(AccionVerticeArbolBinario<T> accion)
      Realiza un recorrido DFS pre-order en el árbol, ejecutando la acción recibida en cada elemento del árbol.
      Parameters:
      accion - la acción a realizar en cada elemento del árbol.

    • dfsInOrder

      public void dfsInOrder(AccionVerticeArbolBinario<T> accion)
      Realiza un recorrido DFS in-order en el árbol, ejecutando la acción recibida en cada elemento del árbol.
      Parameters:
      accion - la acción a realizar en cada elemento del árbol.

    • dfsPostOrder

      public void dfsPostOrder(AccionVerticeArbolBinario<T> accion)
      Realiza un recorrido DFS post-order en el árbol, ejecutando la acción recibida en cada elemento del árbol.
      Parameters:
      accion - la acción a realizar en cada elemento del árbol.

    • iterator

      public Iterator<T> iterator()
      Regresa un iterador para iterar el árbol. El árbol se itera en orden.
      Returns:
      un iterador para iterar el árbol.