Tema 4 - Teoria General

ARBOL NORMAL
Creacion de un Arbol normal:
          tree1= Node 1[ Node 2 [ Node 4 [],Node 5[], Node 6[]], Node 3 [ Node 7 [] ] ]
suma de los valores de los nodos
         sumT tree1
altura de un arbol
        heighT tree1

ARBOL BINARIO
creacion de un arbol binario
      tree2 =NodeB 1 (NodeB 2 (NodeB 4 EmptyB EmptyB) (NodeB 5 EmptyB EmptyB))
       (NodeB 3 (NodeB 6 EmptyB EmptyB) EmptyB)  
 Suma:
      sumB tree2 
 saber que hay a que nivel del arbol binario
      atLevelB 0 tree2
caminos hasta cierto nodo desde la raiz
      pathsToB  (nodo) (arbol)
      pathsToB  5  tree2
      preOrderB  tree2
      inOrderB tree2
      postOrderB tree2
construir un arbol binario de altura minima 
minTreeB' :: [a] -> TreeB a
minTreeB' xs = fst (aux (length xs) xs)
 
aux :: Int -> [a] -> (TreeB a, [a])
aux 0 xs = (EmptyB, xs)
aux 1 xs = (NodeB (head xs) EmptyB EmptyB, tail xs)
aux n xs = (NodeB y t1 t2, zs)
   where
      m = div n 2
      (t1, y:ys) = aux m xs
      (t2, zs) = aux (n-m-1) ys
 COLAS CON PRIORIDAD (SIFO)

definir una cola
      cola1 =enqueue 3  (enqueue 1  (enqueue 2 (empty)))
devuelve una cola vacía
      empty :: PQueue a
test para colas vacías
      isEmpty :: PQueue a -> Bool
inserta un elemento en una cola de prioridad
      enqueue :: (Ord a) => a -> PQueue a -> PQueue a
devuelve el elemento de mínima prioridad
      first :: (Ord a) => PQueue a -> a
devuelve la cola obtenida al eliminar el elemento de mínima prioridad
      dequeue :: (Ord a) => PQueue a -> PQueue a

MONTICULO -  HEAP ORDER PROPERTY EN JAVA

public BinaryHeap()
public int size()
public boolean isEmpty()
private boolean lessThan(int idx1, int idx2)
private void swap(int idx1, int idx2)
private boolean isRoot(int idx)
private int parent(int idx)
private int leftChild(int idx)
private int rightChild(int idx)
private boolean isNode(int idx)
private boolean hasLeftChild(int idx)
private boolean isLeaf(int idx)
public void insert(T x)
public T minElem()

ARBOLES BINARIOS DE BUSQUEDA - BINARY SEARCH TREE (BST) HASKELL




busqueda:
    search 5 tree2
es elemento:
    isElem 5 tree2
    isElem x t = isJust (search x t)
existe una funcion llamada Maybe, que si encuentra SOLO algo entonces asigna el valor TRUE
    data Maybe a = Nothing | Just a
    isJust :: Maybe a -> Bool
    -- si contiene algo entonces da true
    isJust (Just _) = True
    --si no contiene nada da false
    isJust Nothing = False  

Minimo elemento
       minim tree2
Maximo elemento
       maxim tree2
Quitar  y  devolver  el  mínimo  elemento  de  un  árbol:
      split tree2
Eliminar
      delete 4 tree2
Unir
      join tree1 tree2

ARBOLES BINARIOS DE BUSQUEDA - BINARY SEARCH TREE (BST) JAVA

public boolean isEmpty();
public int size();
public int height();
public void insert(K k, V v);
public V search(K k);
public boolean isElem(K k);
public void delete(K k);
public Iterable<K> inOrder();
public Iterable<K> postOrder();
public Iterable<K> preOrder();
public Iterable<V> values();
public Iterable<Tuple2<K,V>> keysValues();

ARBOLES AVL

son arboles que como mucho difieren en altura 1

AVL treeAVL = Nodo 9 (Nodo 3 (Nodo 2 Hoja Hoja) (Nodo 4 Hoja Hoja)) (Nodo 7 Hoja Hoja)

height treeAVL
isAVL treeAVL
rotR treeAVL
rotL treeAVL
insert 4 treeAVL
        inclinacion a la izquierda ,derecha y balanceando de nuevo
rightLeaning treeAVL
leftLeaning treeAVL 
balance altura parteIZQ parteDER
        busqueda
search 5 treeAVL
isElem 5 treeAVL
delete 5 treeAVL
join treeAVL1 treeAVL2
        elimina y devuelve el minimo elemento de un arbol
split treeAVL

ARBOLES AVL EN JAVA

public Tree(C key, D value)
isEmpty();
height(Tree<?,?> tree);
rightLeaning();
leftLeaning();
setHeight();
rotR();
rotL();
balanced();
search(K key);
isElem(K key);

DICCIONARIOS HASKELL

diccionario claves valores

diccionario = empty
isEmpty diccionario
insert clave valor diccionario
valueof valor diccionario